Every simple finite graph G has an associated Lovász-Saks-Schrijver ring R_G(d) that is related to the d-dimensional orthogonal representations of G. The study of R_G(d) lies at the intersection between algebraic geometry, commutative algebra and combinatorics. We find a link between algebraic properties, such as normality, factoriality, and strong F-regularity, of R_G(d) and combinatorial invariants of the graph G. In particular we prove that if d ≥ pmd(G)+k(G)+1 then R_G(d) is UFD. Here pmd(G) is the positive matching decomposition number of G and k(G) is its degeneracy number.