{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:07Z","timestamp":1780783147507,"version":"3.54.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_18","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:15:19Z","timestamp":1780780519000},"page":"251-265","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Realizing Planar Linkages in\u00a0Polygonal Domains"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-7498-6271","authenticated-orcid":false,"given":"Thomas","family":"Depian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6696-074X","authenticated-orcid":false,"given":"Carolina","family":"Haase","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2134-4852","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","unstructured":"Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B.: Who needs crossings? Hardness of plane graph rigidity. In: Fekete, S.P., Lubiw, A. (eds.) Symposium on Computational Geometry (SoCG\u201916). LIPIcs, vol.\u00a051, pp. 3:1\u20133:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPICS.SOCG.2016.3","DOI":"10.4230\/LIPICS.SOCG.2016.3"},{"key":"18_CR2","doi-asserted-by":"publisher","unstructured":"Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B.: Who needs crossings?: noncrossing linkages are universal, and deciding (global) rigidity is hard. J. Comput. Geometry 16 (2025). https:\/\/doi.org\/10.20382\/JOCG.V16I1A12","DOI":"10.20382\/JOCG.V16I1A12"},{"key":"18_CR3","doi-asserted-by":"publisher","unstructured":"Abrahamsen, M., Miltzow, T., Seiferth, N.: Framework for $$\\exists ~\\mathbb{r}$$ -completeness of two-dimensional packing problems. TheoretiCS 3 (2024). https:\/\/doi.org\/10.46298\/THEORETICS.24.11","DOI":"10.46298\/THEORETICS.24.11"},{"key":"18_CR4","doi-asserted-by":"publisher","unstructured":"Alt, H., Knauer, C., Rote, G., Whitesides, S.: The complexity of (un)folding. In: Fortune, S. (ed.) Symposium on Computational Geometry (SoCG\u201903), pp. 164\u2013170. ACM (2003). https:\/\/doi.org\/10.1145\/777792.777818","DOI":"10.1145\/777792.777818"},{"key":"18_CR5","doi-asserted-by":"publisher","unstructured":"Angelini, P., et al.: Geometric realizations of dichotomous ordinal graphs. In: Aichholzer, O., Wang, H. (eds.) Symposium on Computational Geometry (SoCG\u201925). LIPIcs, vol.\u00a0332, pp. 9:1\u20139:16. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPICS.SOCG.2025.9","DOI":"10.4230\/LIPICS.SOCG.2025.9"},{"key":"18_CR6","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer (2008). https:\/\/doi.org\/10.1007\/978-3-540-77974-2","DOI":"10.1007\/978-3-540-77974-2"},{"issue":"03","key":"18_CR7","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/s0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geometry Appl. 22(03), 187\u2013205 (2012). https:\/\/doi.org\/10.1142\/s0218195912500045","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"1\u20133","key":"18_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/s0166-218x(01)00229-3","volume":"117","author":"T Biedl","year":"2002","unstructured":"Biedl, T., et al.: A note on reconfiguring tree linkages: trees can lock. Discret. Appl. Math. 117(1\u20133), 293\u2013297 (2002). https:\/\/doi.org\/10.1016\/s0166-218x(01)00229-3","journal-title":"Discret. Appl. Math."},{"key":"18_CR9","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.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 283\u2013294. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24595-7_26"},{"issue":"1","key":"18_CR10","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 Algorithms Appl. 11(1), 259\u2013276 (2007). https:\/\/doi.org\/10.7155\/jgaa.00145","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"18_CR11","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. Geometry 30(2), 205\u2013239 (2003). https:\/\/doi.org\/10.1007\/S00454-003-0006-7","journal-title":"Discrete Comput. Geometry"},{"key":"18_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"18_CR13","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Geometric Folding Algorithms: Linkages, Origami. Polyhedra. Cambridge University Press (2007). https:\/\/doi.org\/10.1017\/cbo9780511735172","DOI":"10.1017\/cbo9780511735172"},{"key":"18_CR14","doi-asserted-by":"publisher","unstructured":"Depian, T., Haase, C., N\u00f6llenburg, M., Schulz, A.: Realizing planar linkages in polygonal domains (2026). https:\/\/doi.org\/10.48550\/ARXIV.2604.05786","DOI":"10.48550\/ARXIV.2604.05786"},{"issue":"2","key":"18_CR15","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. Discret. Appl. Math. 28(2), 111\u2013134 (1990). https:\/\/doi.org\/10.1016\/0166-218x(90)90110-x","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"18_CR16","doi-asserted-by":"publisher","first-page":"S20","DOI":"10.1137\/20M1385287","volume":"53","author":"J Erickson","year":"2024","unstructured":"Erickson, J., van der Hoog, I., Miltzow, T.: Smoothing the gap between NP and ER. SIAM J. Comput. 53(6), S20-102 (2024). https:\/\/doi.org\/10.1137\/20M1385287","journal-title":"SIAM J. Comput."},{"key":"18_CR17","doi-asserted-by":"publisher","unstructured":"Grigoriev, D., Jr., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Comput. 5(1\u20132), 37\u201364 (1988). https:\/\/doi.org\/10.1016\/s0747-7171(88)80005-1","DOI":"10.1016\/s0747-7171(88)80005-1"},{"issue":"3","key":"18_CR18","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1137\/0213038","volume":"13","author":"J Hopcroft","year":"1984","unstructured":"Hopcroft, J., Joseph, D., Whitesides, S.: Movement problems for 2-dimensional linkages. SIAM J. Comput. 13(3), 610\u2013629 (1984). https:\/\/doi.org\/10.1137\/0213038","journal-title":"SIAM J. Comput."},{"issue":"2","key":"18_CR19","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1137\/0214025","volume":"14","author":"J Hopcroft","year":"1985","unstructured":"Hopcroft, J., Joseph, D., Whitesides, S.: On the movement of robot arms in 2-dimensional bounded regions. SIAM J. Comput. 14(2), 315\u2013333 (1985). https:\/\/doi.org\/10.1137\/0214025","journal-title":"SIAM J. Comput."},{"key":"18_CR20","doi-asserted-by":"publisher","unstructured":"Joseph, D.A., Plantings, W.H.: On the complexity of reachability and motion planning questions (extended abstract). In: Symposium on Computational Geometry (SoCG), pp. 62\u201366. ACM (1985). https:\/\/doi.org\/10.1145\/323233.323242","DOI":"10.1145\/323233.323242"},{"issue":"1","key":"18_CR21","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/bf02187825","volume":"7","author":"V Kantabutra","year":"1992","unstructured":"Kantabutra, V.: Motions of a short-linked robot arm in a square. Discrete Comput. Geometry 7(1), 69\u201376 (1992). https:\/\/doi.org\/10.1007\/bf02187825","journal-title":"Discrete Comput. Geometry"},{"issue":"6","key":"18_CR22","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1016\/s0040-9383(01)00034-9","volume":"41","author":"M Kapovich","year":"2002","unstructured":"Kapovich, M., Millson, J.J.: Universality theorems for configuration spaces of planar linkages. Topology 41(6), 1051\u20131107 (2002). https:\/\/doi.org\/10.1016\/s0040-9383(01)00034-9","journal-title":"Topology"},{"issue":"1","key":"18_CR23","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1112\/plms\/s1-7.1.213","volume":"1","author":"AB Kempe","year":"1875","unstructured":"Kempe, A.B.: On a general method of describing plane curves of the nth degree by linkwork. Proc. Lond. Math. Soc. 1(1), 213\u2013216 (1875). https:\/\/doi.org\/10.1112\/plms\/s1-7.1.213","journal-title":"Proc. Lond. Math. Soc."},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-030-04414-5_28","volume-title":"Graph Drawing and Network Visualization","author":"A Lubiw","year":"2018","unstructured":"Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polygonal region. In: Biedl, T., Kerren, A. (eds.) GD 2018. LNCS, vol. 11282, pp. 387\u2013401. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04414-5_28"},{"issue":"4","key":"18_CR25","doi-asserted-by":"publisher","first-page":"421","DOI":"10.7155\/jgaa.00602","volume":"26","author":"A Lubiw","year":"2022","unstructured":"Lubiw, A., Miltzow, T., Mondal, D.: The complexity of drawing a graph in a polygonal region. J. Graph Algorithms Appl. 26(4), 421\u2013446 (2022). https:\/\/doi.org\/10.7155\/jgaa.00602","journal-title":"J. Graph Algorithms Appl."},{"key":"18_CR26","doi-asserted-by":"publisher","unstructured":"Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J., Urrutia, J. (eds.) Handbook of Computational Geometry, chap.\u00a015, pp. 633\u2013701. Elsevier (2000). https:\/\/doi.org\/10.1016\/b978-044482537-7\/50016-4","DOI":"10.1016\/b978-044482537-7\/50016-4"},{"key":"18_CR27","doi-asserted-by":"publisher","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry - An Introduction. Springer (1985). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"18_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/3-540-61332-3_172","volume-title":"Computing and Combinatorics","author":"S Whitesides","year":"1996","unstructured":"Whitesides, S., Pei, N.: On the reconfiguration of chains. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol. 1090, pp. 381\u2013390. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61332-3_172"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:15:20Z","timestamp":1780780520000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}