{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:26Z","timestamp":1740109586140,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T00:00:00Z","timestamp":1697587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T00:00:00Z","timestamp":1697587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008769","name":"Julius-Maximilians-Universit\u00e4t W\u00fcrzburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,6]]},"abstract":"Abstract<\/jats:title>We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in\u00a0$${\\mathbb {R}}^3$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 3<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains $$K_5$$<\/jats:tex-math>\n \n K<\/mml:mi>\n 5<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $$K_{5,81}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \n 5<\/mml:mn>\n ,<\/mml:mo>\n 81<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, $$K_{4,4}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \n 4<\/mml:mn>\n ,<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and $$K_{3,5}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \n 3<\/mml:mn>\n ,<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al.\u00a0(Isr. J. Math. 46<\/jats:bold>(1\u20132), 127\u2013144 (1983)), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n<\/jats:italic>-vertex graphs is in $$\\Omega (n\\log n)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. From the non-realizability of $$K_{5,81}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \n 5<\/mml:mn>\n ,<\/mml:mo>\n 81<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we obtain that any realizable n<\/jats:italic>-vertex graph has $${\\mathcal {O}}(n^{9\/5})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 9<\/mml:mn>\n \/<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.<\/jats:p>","DOI":"10.1007\/s00454-023-00537-6","type":"journal-article","created":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T14:02:35Z","timestamp":1697637755000},"page":"1429-1455","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Adjacency Graphs of Polyhedral Surfaces"],"prefix":"10.1007","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5267-4512","authenticated-orcid":false,"given":"Elena","family":"Arseneva","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4532-3765","authenticated-orcid":false,"given":"Boris","family":"Klemz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2134-4852","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7166-4467","authenticated-orcid":false,"given":"Birgit","family":"Vogtenhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5872-718X","authenticated-orcid":false,"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,18]]},"reference":[{"key":"537_CR1","unstructured":"Abrahamsen, M., Kleist, L., Miltzow, T.: Geometric embeddability of complexes is $$\\exists {\\mathbb{R}}$$-complete. In: 39th International Symposium on Computational Geometry (Dallas 2023). Leibniz International Proceedings in Informatics, vol. 258, # 1. Leibniz-Zent. Inform., Wadern (2023)"},{"issue":"3","key":"537_CR2","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/s00454-013-9521-1","volume":"50","author":"MdJ Alam","year":"2013","unstructured":"Alam, Md.J., Biedl, Th., Felsner, S., Kaufmann, M., Kobourov, S.G., Ueckerdt, T.: Computing cartograms with optimal complexity. Discrete Comput. Geom. 50(3), 784\u2013810 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"537_CR3","unstructured":"Andreev, E.M.: Convex polyhedra in Lobachevskii spaces. Mat. Sb. 81(123)(3), 445\u2013478 (1970). (in Russian)"},{"key":"537_CR4","doi-asserted-by":"crossref","unstructured":"Aronov, B., van Kreveld, M., van Oostrum, R., Varadarajan, K.: Facility location on a polyhedral surface. Discrete Comput. Geom. 30(3), 357\u2013372 (2003)","DOI":"10.1007\/s00454-003-2769-0"},{"key":"537_CR5","unstructured":"Arseneva, E., Kleist, L., Klemz, B., L\u00f6ffler,\u00a0M., Schulz,\u00a0A., Vogtenhuber,\u00a0B., Wolff,\u00a0A.: Adjacency graphs of polyhedral surfaces. In: 37th International Symposium on Computational Geometry (2021). Leibniz International Proceedings in Informatics, vol. 189, #\u00a011. Leibniz-Zent. Inform., Wadern (2021)"},{"key":"537_CR6","unstructured":"Arseneva, E., Kleist, L., Klemz, B., L\u00f6ffler, M., Schulz,\u00a0A., Vogtenhuber,\u00a0B., Wolff,\u00a0A.: Adjacency graphs of polyhedral surfaces (2021). arXiv:2103.09803v1"},{"key":"537_CR7","doi-asserted-by":"crossref","unstructured":"B\u00e1r\u00e1ny, I., Rote, G.: Strictly convex drawings of planar graphs. Doc. Math. 11, 369\u2013391 (2006)","DOI":"10.4171\/dm\/214"},{"key":"537_CR8","doi-asserted-by":"crossref","unstructured":"Barnette, D.W., Gr\u00fcnbaum, B.: On Steinitz\u2019s theorem concerning convex 3-polytopes and on some properties of planar graphs. In: The Many Facets of Graph Theory (Kalamazoo 1968), pp. 27\u201340. Springer, Berlin (1969)","DOI":"10.1007\/BFb0060102"},{"key":"537_CR9","doi-asserted-by":"crossref","unstructured":"Bowen, C., Durocher, S., L\u00f6ffler, M., Rounds, A., Schulz, A., T\u00f3th, Cs.D.: Realization of simply connected polygonal linkages and recognition of unit disk contact trees. In: 23rd International Symposium on Graph Drawing and Network Visualization (Los Angeles 2015). Lecture Notes in Computer Science, vol. 9411, pp. 447\u2013459. Springer, Cham (2015)","DOI":"10.1007\/978-3-319-27261-0_37"},{"key":"537_CR10","doi-asserted-by":"crossref","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1\u20132), 3\u201324 (1998)","DOI":"10.1016\/S0925-7721(97)00014-X"},{"issue":"4","key":"537_CR11","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/s00454-016-9855-6","volume":"57","author":"M \u010cadek","year":"2017","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Vok\u0159\u00ednek, L.: Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom. 57(4), 915\u2013965 (2017)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"537_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0747-7171(89)80003-3","volume":"7","author":"R Cole","year":"1989","unstructured":"Cole, R., Sharir, M.: Visibility problems for polyhedral terrains. J. Symb. Comput. 7(1), 11\u201330 (1989)","journal-title":"J. Symb. Comput."},{"key":"537_CR13","doi-asserted-by":"crossref","unstructured":"de Floriani, L., Magillo, P., Puppo, E.: Applications of computational geometry in geographic information systems. In: Handbook of Computational Geometry, pp. 333\u2013388 (Chapter\u00a07). Elsevier, Amsterdam (1997)","DOI":"10.1016\/B978-044482537-7\/50008-5"},{"key":"537_CR14","unstructured":"de Fraysseix, H., Ossona de Mendez, P., Pach, J.: Representation of planar graphs by segments. In: Intuitive Geometry (Szeged 1991). Colloquia Mathematica Societatis J\u00e1nos Bolyai, vol. 63, pp. 109\u2013117. North-Holland, Amsterdam (1994)"},{"key":"537_CR15","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Ossona de Mendez, P., Rosenstiehl, P.: On triangle contact graphs. Comb. Probab. Comput. 3(2), 233\u2013246 (1994)","DOI":"10.1017\/S0963548300001139"},{"key":"537_CR16","doi-asserted-by":"crossref","unstructured":"Dobkin, D.P.: Computational geometry and computer graphics. Proc. IEEE 80(9), 1400\u20131411 (1992)","DOI":"10.1109\/5.163408"},{"key":"537_CR17","doi-asserted-by":"crossref","unstructured":"Duncan, C.A., Gansner, E.R., Hu, Y.F., Kaufmann, M., Kobourov, S.G.: Optimal polygonal representation of planar graphs. Algorithmica 63(3), 672\u2013691 (2012)","DOI":"10.1007\/s00453-011-9525-2"},{"key":"537_CR18","unstructured":"Eppstein, D., Mumford, E.: Steinitz theorems for simple orthogonal polyhedra. J. Comput. Geom. 5(1), 179\u2013244 (2014)"},{"key":"537_CR19","doi-asserted-by":"crossref","unstructured":"Evans, W., Rz\u0105\u017cewski, P., Saeedi, N., Shin, Ch.-S., Wolff, A.: Representing graphs and hypergraphs by touching polygons in 3D. In: 27th International Symposium on Graph Drawing and Network Visualization (Prague 2019). Lecture Notes in Computer Science, vol. 11904, pp. 18\u201332. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-35802-0_2"},{"key":"537_CR20","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Thirty Essays on Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-0110-0_12"},{"key":"537_CR21","doi-asserted-by":"crossref","unstructured":"Felsner, S., Francis, M.C.: Contact representations of planar graphs with cubes. In: 27th Annual Symposium on Computational Geometry (Paris 2011), pp. 315\u2013320. ACM, New York (2011)","DOI":"10.1145\/1998196.1998250"},{"key":"537_CR22","doi-asserted-by":"crossref","unstructured":"Filakovsk\u00fd, M., Wagner, U., Zhechev, S.: Embeddability of simplicial complexes is undecidable. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (Salt Lake City 2020), pp. 767\u2013785. SIAM, Philadelphia (2020)","DOI":"10.1137\/1.9781611975994.47"},{"key":"537_CR23","doi-asserted-by":"crossref","unstructured":"Gansner, E.R., Hu, Y., Kobourov, S.G.: On touching triangle graphs. In: 18th International Symposium on Graph Drawing (Konstanz 2010). Lecture Notes in Computer Science, vol. 6502, pp. 250\u2013261. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-18469-7_23"},{"key":"537_CR24","doi-asserted-by":"crossref","unstructured":"Gon\u00e7alves, D., L\u00e9veque, B., Pinlou, A.: Homothetic triangle representations of planar graphs. J. Graph Algorithms Appl. 23(4), 745\u2013753 (2019)","DOI":"10.7155\/jgaa.00509"},{"key":"537_CR25","doi-asserted-by":"crossref","unstructured":"He, X.: On floor-plan of plane graphs. SIAM J. Comput. 28(6), 2150\u20132167 (1999)","DOI":"10.1137\/S0097539796308874"},{"key":"537_CR26","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P.: Classes and recognition of curve contact graphs. J. Comb. Theory Ser. B 74(1), 87\u2013103 (1998)","DOI":"10.1006\/jctb.1998.1846"},{"key":"537_CR27","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P.: Contact graphs of line segments are NP-complete. Discrete Math. 235(1\u20133), 95\u2013106 (2001)","DOI":"10.1016\/S0012-365X(00)00263-6"},{"key":"537_CR28","doi-asserted-by":"crossref","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)","DOI":"10.1016\/S0012-365X(00)00204-1"},{"key":"537_CR29","doi-asserted-by":"crossref","unstructured":"Hong, S.-H., Nagamochi, H.: Extending Steinitz\u2019s theorem to upward star-shaped polyhedra and spherical polyhedra. Algorithmica 61(4), 1022\u20131076 (2011)","DOI":"10.1007\/s00453-011-9570-x"},{"key":"537_CR30","doi-asserted-by":"crossref","unstructured":"Kettner, L.: Designing a data structure for polyhedral surfaces. In: 14th Annual Symposium on Computational Geometry (Minneapolis 1998), pp. 146\u2013154. ACM, New York (1998)","DOI":"10.1145\/276884.276901"},{"key":"537_CR31","doi-asserted-by":"crossref","unstructured":"K\u00f6vari, T., S\u00f3s, V.T., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloq. Math. 3, 50\u201357 (1954)","DOI":"10.4064\/cm-3-1-50-57"},{"key":"537_CR32","doi-asserted-by":"crossref","unstructured":"Kleist, L., Rahman, B.: Unit contact representations of grid subgraphs with regular polytopes in 2D and 3D. In: 22nd International Symposium on Graph Drawing (W\u00fcrzburg 2014). Lecture Notes in Computer Science, vol. 8871, pp. 137\u2013148. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-45803-7_12"},{"key":"537_CR33","unstructured":"Klemz, B., N\u00f6llenburg, M., Prutkin, R.: Recognizing weighted and seeded disk graphs. J. Comput. Geom. 13(1), 327\u2013376 (2022)"},{"key":"537_CR34","doi-asserted-by":"crossref","unstructured":"Kobourov, S.G., Mondal, D., Nishat, R.I.: Touching triangle representations for 3-connected planar graphs. In: 20th International Symposium on Graph Drawing (Redmond 2012). Lecture Notes in Computer Science, vol. 7704, pp. 199\u2013210. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-36763-2_18"},{"key":"537_CR35","first-page":"141","volume":"88","author":"P Koebe","year":"1936","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. S\u00e4chs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88, 141\u2013164 (1936)","journal-title":"Ber. S\u00e4chs. Akad. Wiss. Leipzig, Math.-Phys. Kl."},{"key":"537_CR36","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Sedgwick, E., Tancer, M., Wagner, U.: Embeddability in the 3-sphere is decidable. J. ACM 65(1), #\u00a05 (2018)","DOI":"10.1145\/3078632"},{"key":"537_CR37","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J., Tancer, M., Wagner, U.: Hardness of embedding simplicial complexes in $${\\mathbb{R} }^d$$. J. Eur. Math. Soc. 13(2), 259\u2013295 (2011)","DOI":"10.4171\/jems\/252"},{"key":"537_CR38","doi-asserted-by":"crossref","unstructured":"McMullen, P., Schulz, Ch., Wills, J.M.: Polyhedral 2-manifolds in $$E^{3}$$ with unusually large genus. Isr. J. Math. 46(1\u20132), 127\u2013144 (1983)","DOI":"10.1007\/BF02760627"},{"key":"537_CR39","doi-asserted-by":"crossref","unstructured":"de Mesmay, A., Rieck, Y., Sedgwick, E., Tancer, M.: Embeddability in $$\\mathbb{R}^3$$ is NP-hard. J. ACM 67(4), #\u00a020 (2020)","DOI":"10.1145\/3396593"},{"key":"537_CR40","doi-asserted-by":"crossref","unstructured":"Novik, I.: A note on geometric embeddings of simplicial complexes in a Euclidean space. Discrete Comput. Geom. 23(2), 293\u2013302 (2000)","DOI":"10.1007\/PL00009501"},{"key":"537_CR41","first-page":"31","volume":"56","author":"RC Read","year":"1987","unstructured":"Read, R.C.: A new method for drawing a planar graph given the cyclic order of the edges at each vertex. Congr. Numer. 56, 31\u201344 (1987)","journal-title":"Congr. Numer."},{"key":"537_CR42","doi-asserted-by":"crossref","unstructured":"Richter-Gebert, J.: Realization Spaces of Polytopes. Lecture Notes in Mathematics, vol. 1643. Springer, Berlin (1996)","DOI":"10.1007\/BFb0093761"},{"key":"537_CR43","doi-asserted-by":"crossref","unstructured":"Schramm, O.: Square tilings with prescribed combinatorics. Isr. J. Math. 84(1\u20132), 97\u2013118 (1993)","DOI":"10.1007\/BF02761693"},{"key":"537_CR44","unstructured":"Schramm, O.: Combinatorically prescribed packings and applications to conformal and quasiconformal maps (2010). arXiv:0709.0710"},{"key":"537_CR45","doi-asserted-by":"crossref","unstructured":"Skopenkov, A.: Invariants of graph drawings in the plane. Arnold Math. J. 6(1), 21\u201355 (2020)","DOI":"10.1007\/s40598-019-00128-5"},{"key":"537_CR46","doi-asserted-by":"crossref","unstructured":"Skopenkov, A.: Extendability of simplicial maps is undecidable. Discrete Comput. Geom. 69(1), 250\u2013259 (2023)","DOI":"10.1007\/s00454-022-00454-0"},{"key":"537_CR47","unstructured":"Steinitz, E.: Polyeder und Raumeinteilungen. In: Encyklop\u00e4die der Mathematischen Wissenschaften, vol. 3-1-2, #\u00a012 (1922)"},{"key":"537_CR48","doi-asserted-by":"crossref","unstructured":"Thomassen, C.: Color-critical graphs on a fixed surface. J. Comb. Theory Ser. B 70(1), 67\u2013100 (1997)","DOI":"10.1006\/jctb.1996.1722"},{"key":"537_CR49","doi-asserted-by":"crossref","unstructured":"Tietze, H.: \u00dcber das Problem der Nachbargebiete im Raum. Monatsh. Math. Phys. 16(1), 211\u2013216 (1905)","DOI":"10.1007\/BF01693778"},{"key":"537_CR50","doi-asserted-by":"crossref","unstructured":"Timmreck, D.: Necessary conditions for geometric realizability of simplicial complexes. In: Discrete Differential Geometry. Oberwolfach Seminars, vol. 38, pp. 215\u2013233. Birkh\u00e4user, Basel (2008)","DOI":"10.1007\/978-3-7643-8621-4_11"},{"key":"537_CR51","doi-asserted-by":"crossref","unstructured":"Yeap, K.-H., Sarrafzadeh, M.: Floor-planning by graph dualization: 2-concave rectilinear modules. SIAM J. Comput. 22(3), 500\u2013526 (1993)","DOI":"10.1137\/0222035"},{"key":"537_CR52","doi-asserted-by":"crossref","unstructured":"Ziegler, G.M.: Polyhedral surfaces of high genus. In: Discrete Differential Geometry. Oberwolfach Seminars, vol. 38, pp. 191\u2013213. Birkh\u00e4user, Basel (2008)","DOI":"10.1007\/978-3-7643-8621-4_10"},{"key":"537_CR53","unstructured":"Szilassi polyhedron. https:\/\/en.wikipedia.org\/wiki\/Szilassi_polyhedron"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00537-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00537-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00537-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T20:20:44Z","timestamp":1715026844000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00537-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,18]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["537"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00537-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,10,18]]},"assertion":[{"value":"22 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"A preliminary version of this article appeared in the proceedings of the International Symposium on Computational Geometry<\/i> (SoCG) 2021 [].","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Related Version"}}]}}