{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T04:38:22Z","timestamp":1766378302996,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319272603"},{"type":"electronic","value":"9783319272610"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-27261-0_37","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T01:24:59Z","timestamp":1448501099000},"page":"447-459","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees"],"prefix":"10.1007","author":[{"given":"Clinton","family":"Bowen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephane","family":"Durocher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anika","family":"Rounds","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Alt, H., Knauer, C., Rote, G., Whitesides, S.: On the complexity of the linkage reconfiguration problem. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs, vol. 342, Contemporary Mathematics, pp. 1\u201314. AMS, Providence (2004)","DOI":"10.1090\/conm\/342\/06126"},{"key":"37_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-03367-4_6","volume-title":"Algorithms and Data Structures","author":"B Ballinger","year":"2009","unstructured":"Ballinger, B., Charlton, D., Demaine, E.D., Demaine, M.L., Iacono, J., Liu, C.-H., Poon, S.-H.: Minimal locked trees. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 61\u201373. Springer, Heidelberg (2009)"},{"issue":"3","key":"37_CR3","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0925-7721(97)00026-6","volume":"9","author":"T Biedl","year":"1998","unstructured":"Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Comput. Geom. 9(3), 159\u2013180 (1998)","journal-title":"Comput. Geom."},{"issue":"4","key":"37_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0020-0190(87)90173-6","volume":"25","author":"SN Bhatt","year":"1987","unstructured":"Bhatt, S.N., Cosmadakis, S.S.: The complexity of minimizing wire lengths in VLSI layouts. Inform. Process. Lett. 25(4), 263\u2013267 (1987)","journal-title":"Inform. Process. Lett."},{"key":"37_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BFb0021793","volume-title":"GD 1995","author":"H Breu","year":"1996","unstructured":"Breu, H., Kirkpatrick, D.G.: On the complexity of recognizing intersection and touching graphs of discs. In: Brandenburd, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 88\u201398. Spinger, Heidelberg (1996)"},{"key":"37_CR6","doi-asserted-by":"publisher","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, 3\u201324 (1998)","journal-title":"Comput. Geom."},{"issue":"1","key":"37_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.7155\/jgaa.00145","volume":"11","author":"S Cabello","year":"2007","unstructured":"Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Alg. Appl. 11(1), 259\u2013276 (2007)","journal-title":"J. Graph Alg. Appl."},{"issue":"1","key":"37_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1142\/S0218195907002240","volume":"17","author":"J-S Cheong","year":"2007","unstructured":"Cheong, J.-S., van der Stappen, A.F., Goldberg, K., Overmars, M.H., Rimon, E.: Immobilizing hinged polygons. Int. J. Comput. Geom. Appl. 17(1), 45\u201370 (2007)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Connelly, R., Demaine, E.D.: Geometry and topology of polygonal linkages. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 9, pp. 197\u2013218. CRC, Boca Raton (2004)","DOI":"10.1201\/9781420035315.ch9"},{"issue":"2","key":"37_CR10","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00454-003-0006-7","volume":"30","author":"R Connelly","year":"2003","unstructured":"Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete Comput. Geom. 30(2), 205\u2013239 (2003)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"37_CR11","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00454-010-9262-3","volume":"44","author":"R Connelly","year":"2010","unstructured":"Connelly, R., Demaine, E.D., Demaine, M.L., Fekete, S.P., Langerman, S., Mitchell, J.S.B., Rib\u00f3, A., Rote, G.: Locked and unlocked chains of planar shapes. Discrete Comput. Geom. 44(2), 439\u2013462 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"37_CR12","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Eppstein, D., Erickson, J., Hart, G.W., O\u2019Rourke, J.: Vertex-unfoldings of simplicial manifolds. In: 18th Sympos. on Comput. Geom., pp. 237\u2013243. ACM Press, New York (2002)","DOI":"10.1145\/513400.513429"},{"issue":"3","key":"37_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/S0895480194264010","volume":"9","author":"G Battista Di","year":"1996","unstructured":"Di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math. 9(3), 349\u2013359 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"37_CR14","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Upper Saddle River (1999)"},{"issue":"1","key":"37_CR15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF02086608","volume":"16","author":"P Eades","year":"1996","unstructured":"Eades, P., Whitesides, S.: The realization problem for Euclidean minimum spanning trees is NP-hard. Algorithmica 16(1), 60\u201382 (1996)","journal-title":"Algorithmica"},{"key":"37_CR16","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. 28, 111\u2013134 (1990)","journal-title":"Discrete Appl. Math."},{"key":"37_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/3-540-63938-1_69","volume-title":"GD 1997","author":"SP Fekete","year":"1997","unstructured":"Fekete, S.P., Houle, M.E., Whitesides, S.: The wobbly logic engine: Proving hardness of non-rigid geometric graph representation problems. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 272\u2013283. Springer, Heidelberg (1997)"},{"key":"37_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(89)90118-X","volume":"31","author":"A Gregori","year":"1989","unstructured":"Gregori, A.: Unit-length embedding of binary trees on a square grid. Inform. Process. Lett. 31, 167\u2013173 (1989)","journal-title":"Inform. Process. Lett."},{"key":"37_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/3-540-63938-1_80","volume-title":"GD 1997","author":"P Hlin\u011bn\u00fd","year":"1997","unstructured":"Hlin\u011bn\u00fd, P.: Touching graphs of unit balls. In: Di Battista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 350\u2013358. Springer, Heidelberg (1997)"},{"issue":"1\u20133","key":"37_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0012-365X(00)00204-1","volume":"229","author":"P Hlin\u011bn\u00fd","year":"2001","unstructured":"Hlin\u011bn\u00fd, P., Kratochv\u00edl, J.: Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Math. 229(1\u20133), 101\u2013124 (2001)","journal-title":"Discrete Math."},{"key":"37_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/978-3-319-27261-0_36","volume-title":"GD 2015","author":"B Klemz","year":"2015","unstructured":"Klemz, B., N\u00f6llenburg, M., Prutkin, R.: Recognizing weighted disk contact graphs. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 433\u2013446. LNCS, Spinger, Heidelberg (2015)"},{"key":"37_CR22","doi-asserted-by":"crossref","unstructured":"Reif, J.H.: Complexity of the mover\u2019s problem and generalizations. In: 20th FoCS, pp. 421\u2013427. IEEE, New York (1979)","DOI":"10.1109\/SFCS.1979.10"},{"key":"37_CR23","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-1-4614-0110-0_24","volume-title":"Thirty Essays on Geometric Graph Theory","author":"M Schaefer","year":"2013","unstructured":"Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461\u2013482. Springer, Heidelberg (2013)"},{"issue":"4","key":"37_CR24","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00454-005-1184-0","volume":"34","author":"I Streinu","year":"2005","unstructured":"Streinu, I.: Pseudo-triangulations, rigidity and motion planning. Discrete Comput. Geom. 34(4), 587\u2013635 (2005)","journal-title":"Discrete Comput. Geom."},{"key":"37_CR25","doi-asserted-by":"publisher","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Congruent graphs and the connectivity of graphs. Amer. J. Math. 54, 150\u2013168 (1932)","journal-title":"Amer. J. Math."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-27261-0_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T20:13:07Z","timestamp":1569269587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-27261-0_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319272603","9783319272610"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-27261-0_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 November 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}