{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:17:01Z","timestamp":1740107821092,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T00:00:00Z","timestamp":1721692800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T00:00:00Z","timestamp":1721692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021786","name":"Technische Universit\u00e4t Bergakademie Freiberg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100021786","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a graph <jats:italic>G<\/jats:italic> and a parameter <jats:italic>r<\/jats:italic>, we define the <jats:italic>r<\/jats:italic>-<jats:italic>local matroid<\/jats:italic> of <jats:italic>G<\/jats:italic> to be the matroid generated by its cycles of length at most <jats:italic>r<\/jats:italic>. Extending Whitney\u2019s abstract planar duality theorem from 1932, we prove that for every <jats:italic>r<\/jats:italic> the <jats:italic>r<\/jats:italic>-local matroid of <jats:italic>G<\/jats:italic> is co-graphic if and only if <jats:italic>G<\/jats:italic> admits a certain type of embedding in a surface, which we call <jats:italic>r<\/jats:italic>-<jats:italic>planar embedding<\/jats:italic>. The maximum value of <jats:italic>r<\/jats:italic> such that a graph <jats:italic>G<\/jats:italic> admits an <jats:italic>r<\/jats:italic>-planar embedding is closely related to face-width, and such embeddings for this maximum value of <jats:italic>r<\/jats:italic> are quite often embeddings of minimum genus. Unlike minimum genus embeddings, these <jats:italic>r<\/jats:italic>-planar embeddings can be computed in polynomial time. This provides the first systematic and polynomially computable method to construct for every graph <jats:italic>G<\/jats:italic> a surface so that <jats:italic>G<\/jats:italic> embeds in that surface in an optimal way (phrased in our notion of <jats:italic>r<\/jats:italic>-planarity).<\/jats:p>","DOI":"10.1007\/s00493-024-00118-y","type":"journal-article","created":{"date-parts":[[2024,7,23]],"date-time":"2024-07-23T12:19:01Z","timestamp":1721737141000},"page":"1297-1323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Whitney Type Theorem for Surfaces: Characterising Graphs with Locally Planar Embeddings"],"prefix":"10.1007","volume":"44","author":[{"given":"Johannes","family":"Carmesin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,23]]},"reference":[{"issue":"4","key":"118_CR1","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1002\/jgt.10095","volume":"42","author":"L Abrams","year":"2003","unstructured":"Abrams, L., Slilaty, D.C.: An algebraic characterization of projective-planar graphs. J. Graph Theory 42(4), 320\u2013331 (2003)","journal-title":"J. Graph Theory"},{"issue":"06","key":"118_CR2","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1142\/S0218216506004683","volume":"15","author":"L Abrams","year":"2006","unstructured":"Abrams, L., Slilaty, D.C.: Algebraic characterizations of graph imbeddability in surfaces and pseudosurfaces. J. Knot Theory Ramif. 15(06), 681\u2013693 (2006)","journal-title":"J. Knot Theory Ramif."},{"issue":"2","key":"118_CR3","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1002\/1097-0118(200102)36:2<105::AID-JGT5>3.0.CO;2-H","volume":"36","author":"MO Albertson","year":"2001","unstructured":"Albertson, M.O., Hutchinson, J.P.: Extending colorings of locally planar graphs. J. Graph Theory 36(2), 105\u2013116 (2001)","journal-title":"J. Graph Theory"},{"key":"118_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.103062","volume":"85","author":"N Bowler","year":"2020","unstructured":"Bowler, N., Funk, D., Slilaty, D.: Describing quasi-graphic matroids. Eur. J. Comb. 85, 103062 (2020)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"118_CR5","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.jctb.2008.03.005","volume":"99","author":"H Bruhn","year":"2009","unstructured":"Bruhn, H., Diestel, R.: Maclane\u2019s theorem for arbitrary surfaces. J. Comb. Theory Ser. B 99(2), 275\u2013286 (2009)","journal-title":"J. Comb. Theory Ser. B"},{"key":"118_CR6","doi-asserted-by":"crossref","unstructured":"Carmesin, J.: Local 2-separators. J. Comb. Theory Ser. B 156, 101\u2013144. Extended online version, see https:\/\/arxiv.org\/abs\/2008.03032 (2022)","DOI":"10.1016\/j.jctb.2022.04.005"},{"issue":"6","key":"118_CR7","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1016\/j.jctb.2008.01.003","volume":"98","author":"M DeVos","year":"2008","unstructured":"DeVos, M., Kawarabayashi, K., Mohar, B.: Locally planar graphs are 5-choosable. J. Comb. Theory Ser. B 98(6), 1215\u20131232 (2008)","journal-title":"J. Comb. Theory Ser. B"},{"key":"118_CR8","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Coloring triangle-free graphs on surfaces. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 120\u2013129. SIAM (2009)","DOI":"10.1137\/1.9781611973068.14"},{"issue":"5","key":"118_CR9","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1016\/j.jctb.2013.07.001","volume":"103","author":"J Geelen","year":"2013","unstructured":"Geelen, J., Gerards, B.: Characterizing graphic matroids by a system of linear equations. J. Comb. Theory Ser. B 103(5), 642\u2013646 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"118_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/jgt.22177","volume":"87","author":"J Geelen","year":"2018","unstructured":"Geelen, J., Gerards, B., Whittle, G.: Quasi-graphic matroids. J. Graph Theory 87(2), 253\u2013264 (2018)","journal-title":"J. Graph Theory"},{"key":"118_CR11","doi-asserted-by":"publisher","first-page":"R144","DOI":"10.37236\/233","volume":"16","author":"A Georgakopoulos","year":"2009","unstructured":"Georgakopoulos, A., Spr\u00fcssel, P.: Geodetic topological cycles in locally finite graphs. Electron. J. Comb. 16, R144 (2009)","journal-title":"Electron. J. Comb."},{"issue":"6","key":"118_CR12","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1016\/j.ejc.2003.06.004","volume":"25","author":"K Kawarabayashi","year":"2004","unstructured":"Kawarabayashi, K.: A theorem on paths in locally planar triangulations. Eur. J. Comb. 25(6), 781\u2013784 (2004)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"118_CR13","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1137\/060674211","volume":"24","author":"K Kawarabayashi","year":"2010","unstructured":"Kawarabayashi, K., Mohar, B.: Star coloring and acyclic coloring of locally planar graphs. SIAM J. Discret. Math. 24(1), 56\u201371 (2010)","journal-title":"SIAM J. Discret. Math."},{"key":"118_CR14","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Sidiropoulos, A.: Beyond the Euler characteristic: approximating the genus of general graphs. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pp. 675\u2013682 (2015)","DOI":"10.1145\/2746539.2746583"},{"key":"118_CR15","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Sidiropoulos, A.: Polylogarithmic approximation for Euler genus on bounded degree graphs. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 164\u2013175 (2019)","DOI":"10.1145\/3313276.3316409"},{"issue":"1","key":"118_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ejc.2005.07.017","volume":"28","author":"K Kawarabayashi","year":"2007","unstructured":"Kawarabayashi, K., Niu, J., Zhang, C.-Q.: Chords of longest circuits in locally planar graphs. Eur. J. Comb. 28(1), 315\u2013321 (2007)","journal-title":"Eur. J. Comb."},{"key":"118_CR17","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Mohar, B., Reed, B.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 771\u2013780. IEEE (2008)","DOI":"10.1109\/FOCS.2008.53"},{"issue":"1","key":"118_CR18","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discret. Math. 12(1), 6\u201326 (1999)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"118_CR19","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s004930100003","volume":"21","author":"B Mohar","year":"2001","unstructured":"Mohar, B.: Existence of polyhedral embeddings of graphs. Combinatorica 21(3), 395\u2013401 (2001)","journal-title":"Combinatorica"},{"issue":"1","key":"118_CR20","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1006\/jctb.2000.2026","volume":"82","author":"B Mohar","year":"2001","unstructured":"Mohar, B.: Face covers and the genus problem for apex graphs. J. Comb. Theory Ser. B 82(1), 102\u2013117 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"118_CR21","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jctb.2001.2036","volume":"83","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Robertson, N.: Flexibility of polyhedral embeddings of graphs in surfaces. J. Comb. Theory Ser. B 83(1), 38\u201357 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"key":"118_CR22","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins, Baltimore (2001)"},{"issue":"1\u20133","key":"118_CR23","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(94)00349-N","volume":"149","author":"B Mohar","year":"1996","unstructured":"Mohar, B., Robertson, N., Vitray, R.P.: Planar graphs on the projective plane. Discret. Math. 149(1\u20133), 141\u2013157 (1996)","journal-title":"Discret. Math."},{"key":"118_CR24","doi-asserted-by":"crossref","unstructured":"Nakasawa, T.: On axiomatics of linear dependence III. In: A Lost Mathematician, Takeo Nakasawa, pp. 205\u2013221. Springer, New York (2009)","DOI":"10.1007\/978-3-7643-8573-6_13"},{"key":"118_CR25","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001","volume-title":"Matroid Theory","author":"J Oxley","year":"2011","unstructured":"Oxley, J.: Matroid Theory, 2nd edn. Oxford University Press, New York (2011)","edition":"2"},{"issue":"3","key":"118_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"PD Seymour","year":"1980","unstructured":"Seymour, P.D.: Disjoint paths in graphs. Discret. Math. 29(3), 293\u2013309 (1980)","journal-title":"Discret. Math."},{"issue":"1","key":"118_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02579179","volume":"1","author":"PD Seymour","year":"1981","unstructured":"Seymour, P.D.: Recognizing graphic matroids. Combinatorica 1(1), 75\u201378 (1981)","journal-title":"Combinatorica"},{"issue":"5","key":"118_CR28","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1017\/S0963548302005278","volume":"11","author":"DC Slilaty","year":"2002","unstructured":"Slilaty, D.C.: Matroid duality from topological duality in surfaces of nonnegative Euler characteristic. Comb. Probab. Comput. 11(5), 515 (2002)","journal-title":"Comb. Probab. Comput."},{"issue":"2\u20133","key":"118_CR29","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.disc.2005.07.003","volume":"301","author":"DC Slilaty","year":"2005","unstructured":"Slilaty, D.C.: On cographic matroids and signed-graphic matroids. Discret. Math. 301(2\u20133), 207\u2013217 (2005)","journal-title":"Discret. Math."},{"issue":"3","key":"118_CR30","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1017\/S0004972700042660","volume":"8","author":"G Szekeres","year":"1973","unstructured":"Szekeres, G.: Polyhedral decompositions of cubic graphs. Bull. Aust. Math. Soc. 8(3), 367\u2013387 (1973)","journal-title":"Bull. Aust. Math. Soc."},{"issue":"4","key":"118_CR31","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C Thomassen","year":"1989","unstructured":"Thomassen, C.: The graph genus problem is NP-complete. J. Algorithms 10(4), 568\u2013576 (1989)","journal-title":"J. Algorithms"},{"issue":"2","key":"118_CR32","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C Thomassen","year":"1990","unstructured":"Thomassen, C.: Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory Ser. B 48(2), 155\u2013177 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"118_CR33","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34, 339\u2013362 (1932)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"118_CR34","doi-asserted-by":"publisher","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57(3), 509\u2013533 (1935)","journal-title":"Am. J. Math."},{"issue":"1\u20133","key":"118_CR35","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0012-365X(93)90518-X","volume":"113","author":"T Zaslavsky","year":"1993","unstructured":"Zaslavsky, T.: The projective-planar signed graphs. Discret. Math. 113(1\u20133), 223\u2013247 (1993)","journal-title":"Discret. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00118-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00118-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00118-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T14:03:54Z","timestamp":1731679434000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00118-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,23]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["118"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00118-y","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2024,7,23]]},"assertion":[{"value":"13 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 May 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}