{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T13:12:02Z","timestamp":1768914722498,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T00:00:00Z","timestamp":1679011200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T00:00:00Z","timestamp":1679011200000},"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":"crossref","award":["EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1"]}],"id":[{"id":"10.13039\/501100001659","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":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Tutte\u2019s embedding theorem states that every 3-connected graph without a <jats:inline-formula><jats:alternatives><jats:tex-math>$$K_5$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mn>5<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>- or <jats:inline-formula><jats:alternatives><jats:tex-math>$$K_{3,3}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mn>3<\/mml:mn>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-minor (i.e., a <jats:italic>planar<\/jats:italic> graph) is embedded in the plane if the outer face is in convex position and the interior vertices are convex combinations of their neighbors. We show that this result extends to simply connected tetrahedral meshes in a natural way: for the tetrahedral mesh to be embedded if the outer polyhedron is in convex position and the interior vertices are convex combination of their neighbors it is sufficient (but not necessary) that the graph of the tetrahedral mesh contains no <jats:inline-formula><jats:alternatives><jats:tex-math>$$K_6$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mn>6<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and no <jats:inline-formula><jats:alternatives><jats:tex-math>$$K_{3,3,1}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mn>3<\/mml:mn>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mn>3<\/mml:mn>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and all triangles incident on three boundary vertices are boundary triangles.<\/jats:p>","DOI":"10.1007\/s00454-023-00494-0","type":"journal-article","created":{"date-parts":[[2023,3,27]],"date-time":"2023-03-27T00:52:31Z","timestamp":1679878351000},"page":"197-207","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Tutte Embeddings of Tetrahedral Meshes"],"prefix":"10.1007","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-8466","authenticated-orcid":false,"given":"Marc","family":"Alexa","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,3,17]]},"reference":[{"key":"494_CR1","doi-asserted-by":"crossref","unstructured":"Aigerman, N., Lipman, Y.: Orbifold Tutte embeddings. ACM Trans. Graph. 34(6), # 190 (2015)","DOI":"10.1145\/2816795.2818099"},{"issue":"6","key":"494_CR2","doi-asserted-by":"publisher","first-page":"#\u00a0217","DOI":"10.1145\/2980179.2982412","volume":"35","author":"N Aigerman","year":"2016","unstructured":"Aigerman, N., Lipman, Y.: Hyperbolic orbifold Tutte embeddings. ACM Trans. Graph. 35(6), #\u00a0217 (2016)","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"494_CR3","doi-asserted-by":"publisher","first-page":"#\u00a074","DOI":"10.1145\/2897824.2925890","volume":"35","author":"M Campen","year":"2016","unstructured":"Campen, M., Silva, C.T., Zorin, D.: Bijective maps from simplicial foliations. ACM Trans. Graph. 35(4), #\u00a074 (2016)","journal-title":"ACM Trans. Graph."},{"key":"494_CR4","first-page":"129","volume":"107","author":"K Chilakamarri","year":"1995","unstructured":"Chilakamarri, K., Dean, N., Littman, M.: Three-dimensional Tutte embedding. Congr. Numer. 107, 129\u2013140 (1995)","journal-title":"Congr. Numer."},{"key":"494_CR5","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11, 229\u2013233 (1948)","journal-title":"Acta Univ. Szeged. Sect. Sci. Math."},{"issue":"242","key":"494_CR6","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1090\/S0025-5718-02-01466-7","volume":"72","author":"MS Floater","year":"2003","unstructured":"Floater, M.S.: One-to-one piecewise linear mappings over triangulations. Math. Comput. 72(242), 685\u2013696 (2003)","journal-title":"Math. Comput."},{"issue":"4","key":"494_CR7","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10444-004-7620-5","volume":"25","author":"MS Floater","year":"2006","unstructured":"Floater, M.S., Pham-Trong, V.: Convex combination maps over triangulations, tilings, and tetrahedral meshes. Adv. Comput. Math. 25(4), 347\u2013356 (2006)","journal-title":"Adv. Comput. Math."},{"key":"494_CR8","unstructured":"Geelen, J.: On \u201cHow to draw a graph\u201d. University of Waterloo (2012). https:\/\/www.math.uwaterloo.ca\/~jfgeelen\/Publications\/tutte.pdf"},{"issue":"2","key":"494_CR9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/j.cagd.2005.05.002","volume":"23","author":"SJ Gortler","year":"2006","unstructured":"Gortler, S.J., Gotsman, C., Thurston, D.: Discrete one-forms on meshes and applications to 3D mesh parameterization. Comput. Aided Geom. Des. 23(2), 83\u2013112 (2006)","journal-title":"Comput. Aided Geom. Des."},{"issue":"4","key":"494_CR10","first-page":"357","volume":"28","author":"RS Laugesen","year":"1996","unstructured":"Laugesen, R.S.: Injectivity can fail for higher-dimensional harmonic extensions. Complex Variables Theory Appl. 28(4), 357\u2013369 (1996)","journal-title":"Complex Variables Theory Appl."},{"issue":"2","key":"494_CR11","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0020-0190(90)90142-K","volume":"34","author":"J-P Laumond","year":"1990","unstructured":"Laumond, J.-P.: Connectivity of plane triangulations. Inform. Process. Lett. 34(2), 87\u201396 (1990)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"494_CR12","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1090\/S0002-9939-1993-1112497-9","volume":"117","author":"AD Melas","year":"1993","unstructured":"Melas, A.D.: An example of a harmonic map between Euclidean balls. Proc. Am. Math. Soc. 117(3), 857\u2013859 (1993)","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"494_CR13","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1006\/jctb.1995.1032","volume":"64","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P., Thomas, R.: Sachs\u2019 linkless embedding conjecture. J. Comb. Theory Ser. B 64(2), 185\u2013227 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"key":"494_CR14","doi-asserted-by":"crossref","unstructured":"Sachs, H.: On a spatial analogue of Kuratowski\u2019s theorem on planar graphs\u2014an open problem. In: Graph Theory (\u0141ag\u00f3w 1981). Lecture Notes in Mathematics, vol. 1018, pp. 230\u2013241. Springer, Berlin (1983)","DOI":"10.1007\/BFb0071633"},{"key":"494_CR15","unstructured":"Spielman, D.A.: Tutte\u2019s Theorem: How to draw a graph. Lecture notes for Spectral Graph Theory, Yale University (2018). https:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect15-18.pdf"},{"key":"494_CR16","unstructured":"Steinitz, E.: Polyeder und Raumteilungen. In: Encyklop\u00e4die der Mathematischen Wissenschaften, vol. 3-1-2, #\u00a012 (1922)"},{"key":"494_CR17","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."},{"key":"494_CR18","doi-asserted-by":"crossref","unstructured":"Wood, D.R.: Cliques in graphs excluding a complete graph minor. Electron. J. Comb. 23(3), #\u00a0P3.18 (2016)","DOI":"10.37236\/5715"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00494-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00494-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00494-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T02:01:44Z","timestamp":1736215304000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00494-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,17]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["494"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00494-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,17]]},"assertion":[{"value":"15 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}