{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T12:04:33Z","timestamp":1773230673243,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642192210","type":"print"},{"value":"9783642192227","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_28","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T04:03:12Z","timestamp":1300075392000},"page":"274-285","source":"Crossref","is-referenced-by-count":5,"title":["On the Computational Complexity of Degenerate Unit Distance Representations of Graphs"],"prefix":"10.1007","author":[{"given":"Boris","family":"Horvat","sequence":"first","affiliation":[]},{"given":"Jan","family":"Kratochv\u00edl","sequence":"additional","affiliation":[]},{"given":"Toma\u017e","family":"Pisanski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"28_CR1","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/S0195-6698(03)00031-3","volume":"24","author":"M. Boben","year":"2003","unstructured":"Boben, M., Pisanski, T.: Polycyclic configurations. European J. Combin.\u00a024(4), 431\u2013457 (2003)","journal-title":"European J. Combin."},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01864150","volume":"4","author":"F. Buckley","year":"1988","unstructured":"Buckley, F., Harary, F.: On the Euclidean dimension of a Wheel. Graphs Combin.\u00a04, 23\u201330 (1988)","journal-title":"Graphs Combin."},{"key":"28_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-540-24595-7_26","volume-title":"Graph Drawing","author":"S. Cabello","year":"2004","unstructured":"Cabello, S., Demaine, E., Rote, G.: Planar embeddings of graphs with specified edge lengths. In: Liotta, G. (ed.) GD 2003. LNCS, vol.\u00a02912, pp. 283\u2013294. Springer, Heidelberg (2004)"},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0304-3975(97)84223-5","volume":"169","author":"P. Eades","year":"1996","unstructured":"Eades, P., Whitesides, S.: The logic engine and the realization problem for nearest neighbor graphs. Theor. Comput. Sc.\u00a0169(1), 23\u201337 (1996)","journal-title":"Theor. Comput. Sc."},{"issue":"2","key":"28_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0166-218X(90)90110-X","volume":"28","author":"P. Eades","year":"1990","unstructured":"Eades, P., Wormald, N.C.: Fixed edge-length graph drawing is NP-hard. Discrete Appl. Math.\u00a028(2), 111\u2013134 (1990)","journal-title":"Discrete Appl. Math."},{"key":"28_CR6","unstructured":"Eppstein, D.: Blog entry (January 2010), \n                  \n                    http:\/\/11011110.livejournal.com\/188807.html"},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1112\/S0025579300005222","volume":"12","author":"P. Erd\u00f6s","year":"1965","unstructured":"Erd\u00f6s, P., Harary, F., Tutte, W.T.: On the dimension of a graph. Mathematika\u00a012, 118\u2013122 (1965)","journal-title":"Mathematika"},{"issue":"1","key":"28_CR8","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/0221008","volume":"21","author":"B. Hendrickson","year":"1992","unstructured":"Hendrickson, B.: Conditions For Unique Graph Realizations. SIAM J. Comput.\u00a021(1), 65\u201384 (1992)","journal-title":"SIAM J. Comput."},{"key":"28_CR9","unstructured":"Horvat, B., Pisanski, T.: Unit distance representations of the Petersen graph in the plane. Ars Combin. (to appear)"},{"key":"28_CR10","unstructured":"\u017ditnik, A., Horvat, B., Pisanski, T.: All generalized Petersen graphs are unit-distance graphs (submitted)"},{"issue":"1-4","key":"28_CR11","first-page":"317","volume":"45","author":"L. Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Self-dual polytopes and the chromatic number of distance graphs on the sphere. Acta Sci. Math. (Szeged)\u00a045(1-4), 317\u2013323 (1983)","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0012-365X(88)90217-8","volume":"72","author":"H. Maehara","year":"1988","unstructured":"Maehara, H.: On the Euclidean dimension of a complete multipartite graph. Discrete Math.\u00a072, 285\u2013289 (1988)","journal-title":"Discrete Math."},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02187712","volume":"4","author":"H. Maehara","year":"1989","unstructured":"Maehara, H.: Note on Induced Subgraphs of the Unit Distance Graph. Discrete Comput. Geom.\u00a04, 15\u201318 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/BF01787703","volume":"6","author":"H. Maehara","year":"1990","unstructured":"Maehara, H., R\u00f6dl, V.: On the Dimension to Represent a Graph by a Unit Distance Graph. Graphs Combin.\u00a06, 365\u2013367 (1990)","journal-title":"Graphs Combin."},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals, part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the exitential theory of the reals. J. Symb. Comput.\u00a013, 255\u2013300 (1992)","journal-title":"J. Symb. Comput."},{"key":"28_CR16","volume-title":"The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators","author":"A. Soifer","year":"2008","unstructured":"Soifer, A.: The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T06:35:00Z","timestamp":1558420500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}