{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T02:11:14Z","timestamp":1774059074811,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["101055448"],"award-info":[{"award-number":["101055448"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100019239","name":"Berlin Mathematics Research Center MATH+","doi-asserted-by":"publisher","award":["390685689"],"award-info":[{"award-number":["390685689"]}],"id":[{"id":"10.13039\/501100019239","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>We provide a set of tools for generating planar embeddings of triangulated topological spheres. The algorithms make use of Schnyder labelings and realizers. A new representation of the realizer based on dual trees leads to a simple linear time algorithm mapping from weights per triangle to barycentric coordinates and, more importantly, also in the reverse direction. The algorithms can be implemented so that all coefficients involved are 1 or -1. This enables integer computation, making all computations exact. Being a Schnyder realizer, mapping from positive triangle weights guarantees that the barycentric coordinates form an embedding. The reverse direction enables an algorithm for fixing flipped triangles in planar realizations, by mapping from coordinates to weights and adjusting the weights (without forcing them to be positive). In a range of experiments, we demonstrate that all algorithms are orders of magnitude faster than existing robust approaches.<\/jats:p>","DOI":"10.1145\/3592445","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T14:29:21Z","timestamp":1690381761000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Embeddings in Exact Arithmetic"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7098-1524","authenticated-orcid":false,"given":"Ugo","family":"Finnendahl","sequence":"first","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8920-5544","authenticated-orcid":false,"given":"Dimitrios","family":"Bogiokas","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1167-8795","authenticated-orcid":false,"given":"Pablo","family":"Robles Cervantes","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-8466","authenticated-orcid":false,"given":"Marc","family":"Alexa","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Ziegler","author":"Aigner Martin","year":"2009","unstructured":"Martin Aigner and Gnter M. Ziegler. 2009. Proofs from THE BOOK (4th ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9169-z"},{"key":"e_1_2_2_3_1","volume-title":"Morphing Schnyder Drawings of Planar Triangulations","author":"Barrera-Cruz Fidel","unstructured":"Fidel Barrera-Cruz, Penny Haxell, and Anna Lubiw. 2014. Morphing Schnyder Drawings of Planar Triangulations. In Graph Drawing, Christian Duncan and Antonios Symvonis (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 294--305."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-0018-9"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009264"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531383"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0177-6"},{"key":"e_1_2_2_8_1","unstructured":"Enno Brehm. 2000. 3-orientations and Schnyder 3-tree-decompositions. Master's thesis. FB Mathematik und Informatik Freie Universit\u00e4t Berlin."},{"key":"e_1_2_2_9_1","unstructured":"Herv\u00e9 Br\u00f6nnimann Andreas Fabri Geert-Jan Giezeman Susan Hert Michael Hoffmann Lutz Kettner Sylvain Pion and Stefan Schirra. 2023. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (5.5.2 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.5.2\/Manual\/packages.html#PkgKernel23"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925890"},{"key":"e_1_2_2_11_1","volume-title":"Balanced Schnyder Woods for Planar Triangulations: An Experimental Study with Applications to Graph Drawing and Graph Separators","author":"Aleardi Luca Castelli","unstructured":"Luca Castelli Aleardi. 2019. Balanced Schnyder Woods for Planar Triangulations: An Experimental Study with Applications to Graph Drawing and Graph Separators. In Graph Drawing and Network Visualization, Daniel Archambault and Csaba D. T\u00f3th (Eds.). Springer International Publishing, Cham, 114--121."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000144"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00020-D"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9235-6"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392484"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550469.3555419"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010604726900"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9027-9"},{"key":"e_1_2_2_21_1","volume-title":"Floater and Kai Hormann","author":"Michael","year":"2005","unstructured":"Michael S. Floater and Kai Hormann. 2005. Surface Parameterization: a Tutorial and Survey. In Advances in Multiresolution for Geometric Modelling, Neil A. Dodgson, Michael S. Floater, and Malcolm A. Sabin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 157--186."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459847"},{"key":"e_1_2_2_23_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (6.2.1 ed.). https:\/\/gmplib.org\/","author":"Torbj\u00f6rn Granlund","year":"2020","unstructured":"Torbj\u00f6rn Granlund et al. 2020. GNU MP: The GNU Multiple Precision Arithmetic Library (6.2.1 ed.). https:\/\/gmplib.org\/"},{"key":"e_1_2_2_24_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_2_25_1","volume-title":"Theory and Applications of Models of Computation, Jan Kratochv\u00edl, Angsheng Li, Jivr\u00ed Fiala","author":"He Xin","unstructured":"Xin He and Huaming Zhang. 2010. Schnyder Greedy Routing Algorithm. In Theory and Applications of Models of Computation, Jan Kratochv\u00edl, Angsheng Li, Jivr\u00ed Fiala, and Petr Kolman (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 271--283."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.16223"},{"key":"e_1_2_2_27_1","volume-title":"On straight-line representation of planar graphs. Acta scientiarum mathematicarum 11, 229--233","author":"Istv\u00e1n F\u00e1ry","year":"1948","unstructured":"F\u00e1ry Istv\u00e1n. 1948. On straight-line representation of planar graphs. Acta scientiarum mathematicarum 11, 229--233 (1948), 2."},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo et al. 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086606"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566590"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185604"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the Symposium on Geometry Processing","author":"Liu Ligang","unstructured":"Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local\/Global Approach to Mesh Parameterization. In Proceedings of the Symposium on Geometry Processing (Copenhagen, Denmark) (SGP '08). Eurographics Association, Goslar, DEU, 1495--1504."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.2983621"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132705"},{"key":"e_1_2_2_35_1","volume-title":"Handbook of Computational Geometry, J\u00f6rg-R\u00fcdiger Sack and Jorge Urrutia (Eds.)","author":"Schirra Stefan","unstructured":"Stefan Schirra. 2000. Robustness and Precision Issues in Geometric Computation. In Handbook of Computational Geometry, J\u00f6rg-R\u00fcdiger Sack and Jorge Urrutia (Eds.). Elsevier, Amsterdam, The Netherlands, 597--632."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14607"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00353652"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320191"},{"key":"e_1_2_2_39_1","first-page":"502","article-title":"Convex embeddings of 3-connected plane graphs","volume":"13","author":"Schnyder Walter","year":"1992","unstructured":"Walter Schnyder and William Thomas Trotter. 1992. Convex embeddings of 3-connected plane graphs. Abstracts of the AMS 13 (1992), 502.","journal-title":"Abstracts of the AMS"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/0600000011"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323012"},{"key":"e_1_2_2_42_1","volume-title":"Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator","author":"Shewchuk Jonathan Richard","year":"1996","unstructured":"Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied Computational Geometry Towards Geometric Engineering, Ming C. Lin and Dinesh Manocha (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 203--222."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1951-0041425-5"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392435"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-10.1.304"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-13.1.743"},{"key":"e_1_2_2_50_1","first-page":"26","article-title":"Bemerkungen zum vierfarbenproblem","volume":"46","author":"Wagner Klaus","year":"1936","unstructured":"Klaus Wagner. 1936. Bemerkungen zum vierfarbenproblem. Jahresbericht der Deutschen Mathematiker-Vereinigung 46 (1936), 26--32.","journal-title":"Jahresbericht der Deutschen Mathematiker-Vereinigung"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00040-2"},{"key":"e_1_2_2_52_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).","journal-title":"A Dataset of"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:59Z","timestamp":1750182539000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1145\/3592445"],"URL":"https:\/\/doi.org\/10.1145\/3592445","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"assertion":[{"value":"2023-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}