{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:17Z","timestamp":1740109577287,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T00:00:00Z","timestamp":1678838400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T00:00:00Z","timestamp":1678838400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"deutsche forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WO 758\/11-1","Project-ID 50974019 - TRR 161 (B06)"],"award-info":[{"award-number":["WO 758\/11-1","Project-ID 50974019 - TRR 161 (B06)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"ministero dell\u2019istruzione, dell\u2019universit\u00e0 e della ricerca","doi-asserted-by":"publisher","award":["PRIN 20174LF3T8"],"award-info":[{"award-number":["PRIN 20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"horizon 2020 framework programme","doi-asserted-by":"publisher","award":["734922"],"award-info":[{"award-number":["734922"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A <jats:italic>morph<\/jats:italic> is a continuous transformation between two representations of a graph. We consider the problem of morphing between contact representations of a plane graph. In an <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {F}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-<jats:italic>contact representation<\/jats:italic> of a plane graph <jats:italic>G<\/jats:italic>, vertices are realized by internally disjoint elements from a family <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {F}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of connected geometric objects. Two such elements touch if and only if their corresponding vertices are adjacent. These touchings also induce the same embedding as in\u00a0<jats:italic>G<\/jats:italic>. In a morph between two <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {F}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-contact representations we insist that at each time step (continuously throughout the morph) we have an <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {F}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-contact representation. We focus on the case when <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {F}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the family of triangles in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}^2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>R<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that are the lower-right half of axis-parallel rectangles. Such <jats:italic>RT-representations<\/jats:italic> exist for every plane graph and right triangles are one of the simplest families of shapes supporting this property. Moreover, they naturally correspond to 3-orientations. Thus, they provide a natural case to study regarding morphs of contact representations of plane graphs. We characterize the pairs of RT-representations admitting a morph between each other via the respective 3-orientations. Our characterization leads to a polynomial-time algorithm to decide whether there is a morph between two RT-representations of an <jats:italic>n<\/jats:italic>-vertex plane triangulation, and, if so, computes a morph with <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> steps. Each of these steps is a <jats:italic>linear morph<\/jats:italic> moving the endpoints of each triangle at constant speed along straight-line trajectories. Our characterization also implies that for 4-connected plane triangulations there is a morph between every pair of RT-representations where the \u201ctop-most\u201d triangle in both representations corresponds to the same vertex.<\/jats:p>","DOI":"10.1007\/s00454-022-00475-9","type":"journal-article","created":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T18:02:38Z","timestamp":1678903358000},"page":"991-1024","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Morphing Triangle Contact Representations of Triangulations"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7602-1524","authenticated-orcid":false,"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3501-4608","authenticated-orcid":false,"given":"Steven","family":"Chaplick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1688-394X","authenticated-orcid":false,"given":"Sabine","family":"Cornelsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-5174","authenticated-orcid":false,"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5412-8136","authenticated-orcid":false,"given":"Vincenzo","family":"Roselli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,15]]},"reference":[{"issue":"2","key":"475_CR1","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1137\/16M1069171","volume":"46","author":"S Alamdari","year":"2017","unstructured":"Alamdari, S., Angelini, P., Barrera-Cruz, F., Chan, T.M., Da Lozzo, G., Di Battista, G., Frati, F., Haxell, P., Lubiw, A., Patrignani, M., Roselli, V., Singla, S., Wilkinson, B.T.: How to morph planar graph drawings. SIAM J. Comput. 46(2), 824\u2013852 (2017)","journal-title":"SIAM J. Comput."},{"key":"475_CR2","doi-asserted-by":"crossref","unstructured":"Alamdari, S., Angelini, P., Chan, T.M., Di Battista, G., Frati,\u00a0F., Lubiw,\u00a0A., Patrignani,\u00a0M., Roselli,\u00a0V., Singla,\u00a0S., Wilkinson,\u00a0B.T.: Morphing planar graph drawings with a polynomial number of steps. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 1656\u20131667. SIAM, Philadelphia (2012)","DOI":"10.1137\/1.9781611973105.119"},{"key":"475_CR3","doi-asserted-by":"crossref","unstructured":"Alt, H., Guibas, L.J.: Discrete geometric shapes: matching, interpolation, and approximation. In: Handbook of Computational Geometry, pp. 121\u2013153. North-Holland, Amsterdam (2000)","DOI":"10.1016\/B978-044482537-7\/50004-8"},{"issue":"3","key":"475_CR4","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1070\/SM1970v010n03ABEH001677","volume":"10","author":"EM Andreev","year":"1970","unstructured":"Andreev, E.M.: Convex polyhedra in Loba\u010devski\u012d spaces. Sbornik Math. 10(3), 413\u2013440 (1970)","journal-title":"Sbornik Math."},{"key":"475_CR5","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ipl.2016.12.004","volume":"120","author":"P Angelini","year":"2017","unstructured":"Angelini, P.: Monotone drawings of graphs with few directions. Inform. Process. Lett. 120, 16\u201322 (2017)","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"475_CR6","first-page":"244","volume":"13","author":"P Angelini","year":"2022","unstructured":"Angelini, P., Bekos, M.A., Montecchiani, F., Pfister, M.: On morphs of $$1$$-plane graphs. J. Comput. Geom. 13(1), 244\u2013262 (2022)","journal-title":"J. Comput. Geom."},{"key":"475_CR7","doi-asserted-by":"crossref","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani,\u00a0M., Roselli,\u00a0V.: Morphing planar graph drawings optimally. In: 41st International Colloquium on Automata, Languages, and Programming (Copenhagen 2014). Part\u00a0I. Lecture Notes in Comput. Sci., vol. 8572, pp. 126\u2013137. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-43948-7_11"},{"key":"475_CR8","unstructured":"Angelini, P., Da Lozzo, G., Frati, F., Lubiw, A., Patrignani,\u00a0M., Roselli,\u00a0V.: Optimal morphs of convex drawings. In: 31st International Symposium on Computational Geometry (Eindhoven 2015). Leibniz Int. Proc. Inform., vol. 34, pp. 126\u2013140. Leibniz-Zent. Inform., Wadern (2015)"},{"key":"475_CR9","doi-asserted-by":"crossref","unstructured":"Angelini, P., Frati, F., Patrignani, M., Roselli, V.: Morphing planar graph drawings efficiently. In: 21st International Symposium on Graph Drawing (Bordeaux 2013). Lecture Notes in Comput. Sci., vol. 8242, pp. 49\u201360. Springer, Cham (2013)","DOI":"10.1007\/978-3-319-03841-4_5"},{"issue":"10","key":"475_CR10","first-page":"1226","volume":"55","author":"DN Arnold","year":"2008","unstructured":"Arnold, D.N., Rogness, J.: M\u00f6bius transformations revealed. Not. Am. Math. Soc. 55(10), 1226\u20131231 (2008)","journal-title":"Not. Am. Math. Soc."},{"issue":"1","key":"475_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0925-7721(93)90028-5","volume":"3","author":"B Aronov","year":"1993","unstructured":"Aronov, B., Seidel, R., Souvaine, D.: On compatible triangulations of simple polygons. Comput. Geom. 3(1), 27\u201335 (1993)","journal-title":"Comput. Geom."},{"issue":"3","key":"475_CR12","doi-asserted-by":"publisher","first-page":"579","DOI":"10.7155\/jgaa.00503","volume":"23","author":"E Arseneva","year":"2019","unstructured":"Arseneva, E., Bose, P., Cano, P., D\u2019Angelo, A., Dujmovi\u0107, V., Frati, F., Langerman, S., Tappini, A.: Pole dancing: 3D morphs for tree drawings. J. Graph Algorithms Appl. 23(3), 579\u2013602 (2019)","journal-title":"J. Graph Algorithms Appl."},{"key":"475_CR13","doi-asserted-by":"crossref","unstructured":"Barrera-Cruz, F., Borrazzo, M., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani,\u00a0M., Roselli,\u00a0V.: How to morph a tree on a small grid. In: 16th International Algorithms and Data Structures Symposium (Edmonton 2019). Lecture Notes in Comput. Sci., vol. 11646, pp. 57\u201370. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-24766-9_5"},{"issue":"1","key":"475_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00454-018-0018-9","volume":"61","author":"F Barrera-Cruz","year":"2019","unstructured":"Barrera-Cruz, F., Haxell, P., Lubiw, A.: Morphing Schnyder drawings of planar triangulations. Discrete Comput. Geom. 61(1), 161\u2013184 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"475_CR15","doi-asserted-by":"crossref","unstructured":"Biedl, Th., Lubiw, A., Petrick, M., Spriggs, M.: Morphing orthogonal planar graph drawings. ACM Trans. Algorithms 9(4), # 29 (2013)","DOI":"10.1145\/2500118"},{"key":"475_CR16","doi-asserted-by":"crossref","unstructured":"Bowen, C., Durocher, S., L\u00f6ffler, M., Rounds, A., Schulz,\u00a0A., 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 Comput. Sci., vol. 9411, pp. 447\u2013459. Springer, Cham (2015)","DOI":"10.1007\/978-3-319-27261-0_37"},{"key":"475_CR17","unstructured":"Brehm, E.: $$3$$-Orientations and Schnyder $$3$$-Tree-Decompositions. MSc thesis, Freie Universit\u00e4t Berlin (2000). https:\/\/page.math.tu-berlin.de\/~felsner\/Diplomarbeiten\/brehm.ps.gz"},{"issue":"2","key":"475_CR18","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0406017","volume":"6","author":"GR Brightwell","year":"1993","unstructured":"Brightwell, G.R., Scheinerman, E.R.: Representations of planar graphs. SIAM J. Discrete Math. 6(2), 214\u2013229 (1993)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"475_CR19","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1080\/00029890.1944.11999082","volume":"51","author":"SS Cairns","year":"1944","unstructured":"Cairns, S.S.: Deformations of plane rectilinear complexes. Am. Math. Mon. 51(5), 247\u2013252 (1944)","journal-title":"Am. Math. Mon."},{"key":"475_CR20","doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Erickson, J., Lin, P., Parsa, S.: How to morph graphs on the torus. In: 2021 ACM-SIAM Symposium on Discrete Algorithms, pp. 2759\u20132778. SIAM, Philadelphia (2021)","DOI":"10.1137\/1.9781611976465.164"},{"key":"475_CR21","unstructured":"Chaplick, S., Kindermann, Ph., Klawitter, J., Rutter, I., Wolff, A.: Morphing rectangular duals (2021). arXiv:2112.03040"},{"key":"475_CR22","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Kobourov, S.G., Ueckerdt, T.: Equilateral L-contact graphs. In: 39th International Workshop on Graph-Theoretic Concepts in Computer Science (L\u00fcbeck 2013). Lecture Notes in Comput. Sci., vol. 8165, pp. 139\u2013151. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-642-45043-3_13"},{"issue":"2","key":"475_CR23","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":"475_CR24","unstructured":"Da Lozzo, G., Devanny, W.E., Eppstein, D., Johnson, T.: Square-contact representations of partial 2-trees and triconnected simply-nested graphs. In: 28th International Symposium on Algorithms and Computation (Phuket 2017). Leibniz Int. Proc. Inform., vol. 92, #\u00a024. Leibniz-Zent. Inform., Wadern (2017)"},{"issue":"10","key":"475_CR25","doi-asserted-by":"publisher","first-page":"2985","DOI":"10.1007\/s00453-020-00714-6","volume":"82","author":"G Da Lozzo","year":"2020","unstructured":"Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V.: Upward planar morphs. Algorithmica 82(10), 2985\u20133017 (2020)","journal-title":"Algorithmica"},{"key":"475_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735172","volume-title":"Geometric Folding Algorithms: Linkages","author":"ED Demaine","year":"2007","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Geometric Folding Algorithms: Linkages. Cambridge University Press, Cambridge, Origami. Polyhedra (2007)"},{"key":"475_CR27","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2016.04.034","volume":"636","author":"E Di Giacomo","year":"2016","unstructured":"Di Giacomo, E., Liotta, G., Mchedlidze, T.: Lower and upper bounds for long induced paths in 3-connected planar graphs. Theoret. Comput. Sci. 636, 47\u201355 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"475_CR28","doi-asserted-by":"crossref","unstructured":"Erickson, J., Lin, P.: Planar and toroidal morphs made easier. In: 29th International Symposium on Graph Drawing and Network Visualization (T\u00fcbingen 2021). Lecture Notes in Comput. Sci., vol. 12868, pp. 123\u2013137. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-92931-2_9"},{"key":"475_CR29","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11(1), # R15 (2004)","DOI":"10.37236\/1768"},{"key":"475_CR30","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":"475_CR31","unstructured":"Felsner, S., Rote, G.: On primal-dual circle representations. In: 2nd Symposium on Simplicity in Algorithms (San Diego 2019). OASIcs OpenAccess Ser. Inform., vol. 69, #\u00a08. Leibniz-Zent. Inform., Wadern (2019)"},{"key":"475_CR32","doi-asserted-by":"crossref","unstructured":"Felsner, S., Schrezenmaier, H., Steiner, R.: Equiangular polygon contact representations. In: 44th International Workshop on Graph-Theoretic Concepts in Computer Science (Cottbus 2018). Lecture Notes in Comput. Sci., vol. 11159, pp. 203\u2013215. Springer, Cham (2018)","DOI":"10.1007\/978-3-030-00256-5_17"},{"issue":"1\u20132","key":"475_CR33","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0377-0427(98)00202-7","volume":"101","author":"MS Floater","year":"1999","unstructured":"Floater, M.S., Gotsman, C.: How to morph tilings injectively. J. Comput. Appl. Math. 101(1\u20132), 117\u2013129 (1999)","journal-title":"J. Comput. Appl. Math."},{"key":"475_CR34","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Ossona de Mendez, P.: Representations by contact and intersection of segments. Algorithmica 47(4), 453\u2013463 (2007)","DOI":"10.1007\/s00453-006-0157-x"},{"key":"475_CR35","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":"475_CR36","unstructured":"van Goethem, A., Verbeek, K.: Optimal morphs of planar orthogonal drawings. In: 34th International Symposium on Computational Geometry (Budapest 2018). Leibniz Int. Proc. Inform., vol. 99, #\u00a042. Leibniz-Zent. Inform., Wadern (2018)"},{"key":"475_CR37","doi-asserted-by":"crossref","unstructured":"van Goethem, A., Speckmann, B., Verbeek, K.: Optimal morphs of planar orthogonal drawings\u00a0II. In: 27th International Symposium on Graph Drawing and Network Visualization (Prague 2019). Lecture Notes in Comput. Sci., vol. 11904, pp. 33\u201345. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-35802-0_3"},{"issue":"1","key":"475_CR38","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00454-012-9400-1","volume":"48","author":"D Gon\u00e7alves","year":"2012","unstructured":"Gon\u00e7alves, D., L\u00e9v\u00eaque, B., Pinlou, A.: Triangle contact representations and duality. Discrete Comput. Geom. 48(1), 239\u2013254 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"475_CR39","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0097-8493(00)00108-4","volume":"25","author":"C Gotsman","year":"2001","unstructured":"Gotsman, C., Surazhsky, V.: Guaranteed intersection-free polygon morphing. Comput. Graph. 25(1), 67\u201375 (2001)","journal-title":"Comput. Graph."},{"key":"475_CR40","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.comgeo.2019.07.007","volume":"84","author":"L Kleist","year":"2019","unstructured":"Kleist, L., Klemz, B., Lubiw, A., Schlipf, L., Staals, F., Strash, D.: Convexity-increasing morphs of planar graphs. Comput. Geom. 84, 69\u201388 (2019)","journal-title":"Comput. Geom."},{"key":"475_CR41","unstructured":"Klemz, B.: Convex drawings of hierarchical graphs in linear time, with applications to planar graph morphing. In: 29th Annual European Symposium on Algorithms. Leibniz Int. Proc. Inform., vol. 204, # 57. Leibniz-Zent. Inform., Wadern (2021)"},{"issue":"1","key":"475_CR42","doi-asserted-by":"publisher","first-page":"113","DOI":"10.7155\/jgaa.00162","volume":"12","author":"SG Kobourov","year":"2008","unstructured":"Kobourov, S.G., Landis, M.: Morphing planar graphs in spherical space. J. Graph Algorithms Appl. 12(1), 113\u2013127 (2008)","journal-title":"J. Graph Algorithms Appl."},{"key":"475_CR43","doi-asserted-by":"crossref","unstructured":"Kobourov, S., Ueckerdt, T., Verbeek, K.: Combinatorial and geometric properties of planar Laman graphs. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 1668\u20131678. SIAM, Philadelphia (2013)","DOI":"10.1137\/1.9781611973105.120"},{"key":"475_CR44","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. S\u00e4chs. Akad. Wiss. Leipzig Math. Phys. Kl. 88, 141\u2013164 (1936)"},{"issue":"4","key":"475_CR45","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01534980","volume":"4","author":"G Laman","year":"1970","unstructured":"Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4(4), 331\u2013340 (1970)","journal-title":"J. Eng. Math."},{"issue":"1","key":"475_CR46","first-page":"47","volume":"7","author":"M N\u00f6llenburg","year":"2016","unstructured":"N\u00f6llenburg, M., Prutkin, R., Rutter, I.: On self-approaching and increasing-chord drawings of 3-connected planar graphs. J. Comput. Geom. 7(1), 47\u201369 (2016)","journal-title":"J. Comput. Geom."},{"key":"475_CR47","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: 1st Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco 1990), pp. 138\u2013148. SIAM, Philadelphia (1990)"},{"key":"475_CR48","unstructured":"Schramm, O.: Combinatorially Prescribed Packings and Applications to Conformal and Quasiconformal Maps. PhD thesis, Princeton University (1990)"},{"key":"475_CR49","doi-asserted-by":"crossref","unstructured":"Schrezenmaier, H.: Homothetic triangle contact representations. In: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science (Eindhoven 2017). Lecture Notes in Comput. Sci., vol. 10520, pp. 425\u2013437. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-68705-6_32"},{"issue":"4","key":"475_CR50","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1145\/502783.502784","volume":"20","author":"V Surazhsky","year":"2001","unstructured":"Surazhsky, V., Gotsman, C.: Controllable morphing of compatible planar triangulations. ACM Trans. Graph. 20(4), 203\u2013231 (2001)","journal-title":"ACM Trans. Graph."},{"issue":"3","key":"475_CR51","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0095-8956(83)90038-2","volume":"34","author":"C Thomassen","year":"1983","unstructured":"Thomassen, C.: Deformations of plane graphs. J. Comb. Theory Ser. B 34(3), 244\u2013257 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"475_CR52","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0095-8956(86)90061-4","volume":"40","author":"C Thomassen","year":"1986","unstructured":"Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B 40(1), 9\u201320 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"key":"475_CR53","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"WT Tutte","year":"1963","unstructured":"Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. 13, 743\u2013767 (1963)","journal-title":"Proc. Lond. Math. Soc."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00475-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00475-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00475-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T17:04:22Z","timestamp":1696439062000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00475-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,15]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["475"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00475-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,3,15]]},"assertion":[{"value":"27 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}