{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:21:27Z","timestamp":1778498487845,"version":"3.51.4"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00454-012-9394-8","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T11:29:21Z","timestamp":1327404561000},"page":"548-568","source":"Crossref","is-referenced-by-count":45,"title":["Sphere and Dot Product Representations of Graphs"],"prefix":"10.1007","volume":"47","author":[{"given":"Ross J.","family":"Kang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tobias","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,1,25]]},"reference":[{"issue":"6","key":"9394_CR1","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S. Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002\u20131045 (1996)","journal-title":"J. ACM"},{"key":"9394_CR2","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S. Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"9394_CR3","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511586507","volume-title":"Oriented Matroids","author":"A. Bj\u00f6rner","year":"1999","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and Its Applications, vol. 46, 2nd edn. Cambridge University Press, Cambridge (1999)","edition":"2"},{"issue":"1\u20132","key":"9394_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom."},{"key":"9394_CR5","series-title":"Advanced Lectures in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-80303-0","volume-title":"Geometric Graphs and Arrangements","author":"S. Felsner","year":"2004","unstructured":"Felsner, S.: In: Geometric Graphs and Arrangements. Advanced Lectures in Mathematics. Friedr. Vieweg, Wiesbaden (2004). Some chapters from combinatorial geometry"},{"issue":"1\u20133","key":"9394_CR6","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0012-365X(97)00049-6","volume":"181","author":"C.M. Fiduccia","year":"1998","unstructured":"Fiduccia, C.M., Scheinerman, E.R., Trenk, A., Zito, J.S.: Dot product representations of graphs. Discrete Math. 181(1\u20133), 113\u2013138 (1998)","journal-title":"Discrete Math."},{"key":"9394_CR7","unstructured":"Havel, T.F.: The combinatorial distance geometry approach to the calculation of molecular conformation. Ph.D. thesis, University of California, Berkeley (1982)"},{"issue":"4","key":"9394_CR8","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S. Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"7","key":"9394_CR9","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"P.J. Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15\u201325 (1993)","journal-title":"Comput. Math. Appl."},{"issue":"1","key":"9394_CR10","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0166-218X(84)90113-6","volume":"7","author":"H. Maehara","year":"1984","unstructured":"Maehara, H.: Space graphs and sphericity. Discrete Appl. Math. 7(1), 55\u201364 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9394_CR11","series-title":"Annals of Discrete Mathematics","volume-title":"Threshold Graphs and Related Topics","author":"N.V.R. Mahadev","year":"1995","unstructured":"Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics. Annals of Discrete Mathematics, vol. 56. North-Holland, Amsterdam (1995)"},{"key":"9394_CR12","unstructured":"McDiarmid, C.J.H., M\u00fcller, T.: Integer representation of disk and segment graphs (2011, submitted). arXiv: 1111.2931"},{"key":"9394_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/978-3-642-16926-7_29","volume-title":"Proceedings of 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010)","author":"C.J.H. McDiarmid","year":"2010","unstructured":"McDiarmid, C.J.H., M\u00fcller, T.: The number of bits needed to represent a unit disk graph. In: Proceedings of 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). Lecture Notes in Computer Science, vol.\u00a06410, pp.\u00a0315\u2013323 (2010)"},{"key":"9394_CR14","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/BF02104991","volume":"28","author":"N.E. Mn\u00ebv","year":"1985","unstructured":"Mn\u00ebv, N.E.: Realizability of combinatorial types of convex polyhedra over fields. J. Sov. Math. 28, 606\u2013609 (1985) (in Russian)","journal-title":"J. Sov. Math."},{"key":"9394_CR15","series-title":"Lecture Notes in Math.","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/BFb0082792","volume-title":"Topology and Geometry\u2014Rohlin Seminar","author":"N.E. Mn\u00ebv","year":"1988","unstructured":"Mn\u00ebv, N.E.: The universality theorems on the classification problem of configuration varieties and convex polytopes varieties. In: Topology and Geometry\u2014Rohlin Seminar. Lecture Notes in Math., vol.\u00a01346, pp. 527\u2013543. Springer, Berlin (1988)"},{"issue":"4","key":"9394_CR16","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02187736","volume":"4","author":"J. Reiterman","year":"1989","unstructured":"Reiterman, J., R\u00f6dl, V., \u0160i\u0148ajov\u00e1, E.: Embeddings of graphs in Euclidean spaces. Discrete Comput. Geom. 4(4), 349\u2013364 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9394_CR17","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(89)90142-8","volume":"74","author":"J. Reiterman","year":"1989","unstructured":"Reiterman, J., R\u00f6dl, V., \u0160i\u0148ajov\u00e1, E.: Geometrical embeddings of graphs. Discrete Math. 74(3), 291\u2013319 (1989)","journal-title":"Discrete Math."},{"issue":"1","key":"9394_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(92)90002-F","volume":"56","author":"J. Reiterman","year":"1992","unstructured":"Reiterman, J., R\u00f6dl, V., \u0160i\u0148ajov\u00e1, E.: On embedding of graphs into Euclidean spaces of small dimension. J. Comb. Theory, Ser. B 56(1), 1\u20138 (1992)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9394_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/978-3-642-11805-0_32","volume-title":"Graph Drawing, 17th International Symposium (GD 2009)","author":"M. Schaefer","year":"2010","unstructured":"Schaefer, M.: Complexity of some geometric and topological problems. In: Graph Drawing, 17th International Symposium (GD 2009), Chicago, 22\u201325 September 2009. Lecture Notes in Computer Science, vol. 5849, pp. 334\u2013344 (2010)"},{"key":"9394_CR20","series-title":"Wiley-Interscience Series in Discrete Mathematics","volume-title":"Theory of Linear and Integer Programming","author":"A. Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)"},{"key":"9394_CR21","series-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci.","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1090\/dimacs\/004\/41","volume-title":"Applied Geometry and Discrete Mathematics","author":"P.W. Shor","year":"1991","unstructured":"Shor, P.W.: Stretchability of pseudolines is NP-hard. In: Applied Geometry and Discrete Mathematics. DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 4, pp.\u00a0531\u2013554. Am. Math. Soc., Providence (1991)"},{"key":"9394_CR22","series-title":"Fields Institute Monographs","doi-asserted-by":"crossref","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, vol. 19. Am. Math. Soc., Providence (2003)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00454-012-9394-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,22]],"date-time":"2019-06-22T17:27:52Z","timestamp":1561224472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-012-9394-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,25]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9394"],"URL":"https:\/\/doi.org\/10.1007\/s00454-012-9394-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,25]]}}}