{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:10Z","timestamp":1750220950671,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:00:00Z","timestamp":1556150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["CH 897\/2-2"],"award-info":[{"award-number":["CH 897\/2-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            , the NP-hard\n            <jats:italic>Maximum Planar Subgraph<\/jats:italic>\n            problem asks for a planar subgraph of\n            <jats:italic>G<\/jats:italic>\n            with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski\u2019s famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-Boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.\n          <\/jats:p>","DOI":"10.1145\/3320344","type":"journal-article","created":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T12:23:24Z","timestamp":1556281404000},"page":"1-21","source":"Crossref","is-referenced-by-count":1,"title":["Exact Algorithms for the Maximum Planar Subgraph Problem"],"prefix":"10.1145","volume":"24","author":[{"given":"Markus","family":"Chimani","sequence":"first","affiliation":[{"name":"Osnabr\u00fcck University, Osnabr\u00fcck, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0335-7825","authenticated-orcid":false,"given":"Ivo","family":"Hedtke","sequence":"additional","affiliation":[{"name":"Schenker AG, Essen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-4114","authenticated-orcid":false,"given":"Tilo","family":"Wiedera","sequence":"additional","affiliation":[{"name":"Osnabr\u00fcck University, Osnabr\u00fcck, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0164-1212(84)90006-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(96)00005-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63515"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-38851-9_6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00091"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222068"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0920"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-1020-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0027-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_29"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.078"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00264"},{"volume-title":"Handbook on Graph Drawing and Visualization","author":"Chimani Markus","key":"e_1_2_1_13_1","unstructured":"Markus Chimani , Carsten Gutwenger , Michael J\u00fcnger , Gunnar W. Klau , Karsten Klein , and Petra Mutzel . 2013. The open graph drawing framework (OGDF) . In Handbook on Graph Drawing and Visualization , Roberto Tamassia (Ed.). Chapman and Hall\/CRC , 543--569. crcpress.com\/Handbook-of-Graph-Drawing-and-Visualization\/Tamassia\/9781584884125 Markus Chimani, Carsten Gutwenger, Michael J\u00fcnger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. 2013. The open graph drawing framework (OGDF). In Handbook on Graph Drawing and Visualization, Roberto Tamassia (Ed.). Chapman and Hall\/CRC, 543--569. crcpress.com\/Handbook-of-Graph-Drawing-and-Visualization\/Tamassia\/9781584884125"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 17th International Symposium on Experimental Algorithms, SEA 2018, June 27--29","volume":"103","author":"Chimani Markus","year":"2018","unstructured":"Markus Chimani , Ivo Hedtke , and Tilo Wiedera . 2018 . Exact algorithms for the maximum planar subgraph problem: New models and experiments . In Proceedings of the 17th International Symposium on Experimental Algorithms, SEA 2018, June 27--29 , 2018, L\u2019Aquila, Italy (LIPIcs), Gianlorenzo D\u2019Angelo (Ed.) , Vol. 103 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 22:1--22:15. Markus Chimani, Ivo Hedtke, and Tilo Wiedera. 2018. Exact algorithms for the maximum planar subgraph problem: New models and experiments. In Proceedings of the 17th International Symposium on Experimental Algorithms, SEA 2018, June 27--29, 2018, L\u2019Aquila, Italy (LIPIcs), Gianlorenzo D\u2019Angelo (Ed.), Vol. 103. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 22:1--22:15."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0030-z"},{"volume-title":"Graph Drawing and Network Visualization (Lecture Notes in Computer Science)","author":"Chimani Markus","key":"e_1_2_1_16_1","unstructured":"Markus Chimani , Karsten Klein , and Tilo Wiedera . 2016. A note on the practicality of maximal planar subgraph algorithms . In Graph Drawing and Network Visualization (Lecture Notes in Computer Science) , Vol. 9801 . Springer , 357--364. arxiv.org\/abs\/1609.02443 Markus Chimani, Karsten Klein, and Tilo Wiedera. 2016. A note on the practicality of maximal planar subgraph algorithms. In Graph Drawing and Network Visualization (Lecture Notes in Computer Science), Vol. 9801. Springer, 357--364. arxiv.org\/abs\/1609.02443"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 15th International Symposium on Graph Drawing, GD 2007","author":"Chimani Markus","year":"2007","unstructured":"Markus Chimani , Petra Mutzel , and Jens M. Schmidt . 2007. Efficient extraction of multiple Kuratowski subdivisions . In Proceedings of the 15th International Symposium on Graph Drawing, GD 2007 , Sydney, Australia, September 24--26 , 2007 . Revised Papers (Lecture Notes in Computer Science, Vol. 4875), Seok-Hee Hong, Takao Nishizeki, and Wu Quan (Eds.), Springer, 159--170. Markus Chimani, Petra Mutzel, and Jens M. Schmidt. 2007. Efficient extraction of multiple Kuratowski subdivisions. In Proceedings of the 15th International Symposium on Graph Drawing, GD 2007, Sydney, Australia, September 24--26, 2007. Revised Papers (Lecture Notes in Computer Science, Vol. 4875), Seok-Hee Hong, Takao Nishizeki, and Wu Quan (Eds.), Springer, 159--170."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 26th Annual European Symposium on Algorithms, ESA 2018, August 20--22","volume":"112","author":"Chimani Markus","year":"2018","unstructured":"Markus Chimani and Tilo Wiedera . 2018 . Cycles to the rescue&excl; Novel constraints to compute maximum planar subgraphs fast . In Proceedings of the 26th Annual European Symposium on Algorithms, ESA 2018, August 20--22 , 2018, Helsinki, Finland (LIPIcs), Yossi Azar, Hannah Bast, and Grzegorz Herman (Eds.) , Vol. 112 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1--19:14. Markus Chimani and Tilo Wiedera. 2018. Cycles to the rescue&excl; Novel constraints to compute maximum planar subgraphs fast. In Proceedings of the 26th Annual European Symposium on Algorithms, ESA 2018, August 20--22, 2018, Helsinki, Finland (LIPIcs), Yossi Azar, Hannah Bast, and Grzegorz Herman (Eds.), Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1--19:14."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207169408804320"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 22--24","author":"Cimikowski Robert J.","year":"1995","unstructured":"Robert J. Cimikowski . 1995 . An analysis of some heuristics for the maximum planar subgraph problem . In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 22--24 January 1995. San Francisco, California, Kenneth L. Clarkson (Ed.). ACM\/SIAM, 322--331. dl.acm.org\/citation.cfm?id&equals;313651.313713. Robert J. Cimikowski. 1995. An analysis of some heuristics for the maximum planar subgraph problem. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 22--24 January 1995. San Francisco, California, Kenneth L. Clarkson (Ed.). ACM\/SIAM, 322--331. dl.acm.org\/citation.cfm?id&equals;313651.313713."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672876"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371374"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(85)90288-7"},{"key":"e_1_2_1_24_1","volume-title":"Leslie Richard Foulds, and J. W. Giffin","author":"Eades Peter","year":"1982","unstructured":"Peter Eades , Leslie Richard Foulds, and J. W. Giffin . 1982 . An efficient heuristic for identifying a maximum weight planar subgraph. In Combinatorial Mathematics IX (Lecture Notes in Mathematics , Vol. 952), Elizabeth J. Billington, Sheila Oates-Williams, and Anne Penfold Street (Eds.), 239-- 251 . Peter Eades, Leslie Richard Foulds, and J. W. Giffin. 1982. An efficient heuristic for identifying a maximum weight planar subgraph. In Combinatorial Mathematics IX (Lecture Notes in Mathematics, Vol. 952), Elizabeth J. Billington, Sheila Oates-Williams, and Anne Penfold Street (Eds.), 239--251."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.5.1091"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1976.174"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"H. de Fraysseix and P. Rosenstiehl. 1985. A characterization of planar graphs by Tr\u00e9maux orders. Combinatorica. An International Journal of the J\u00e1nos Bolyai Mathematical Society 5 2 (1985) 127--135.  H. de Fraysseix and P. Rosenstiehl. 1985. A characterization of planar graphs by Tr\u00e9maux orders. Combinatorica. An International Journal of the J\u00e1nos Bolyai Mathematical Society 5 2 (1985) 127--135.","DOI":"10.1007\/BF02579375"},{"key":"e_1_2_1_28_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability. A Guide to the Theory of NP-completeness. W. H. Freeman and Co. , San Francisco, Calif. x+338 pages. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability. A Guide to the Theory of NP-completeness. W. H. Freeman and Co., San Francisco, Calif. x+338 pages."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1971622.1971623"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240203"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207549108948041"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.1995.tb00007.x"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"Jan","year":"2007","unstructured":"Jan M. Hochstein and Karsten Weihe. 2007. Maximum s-t-flow with k crossings in O(kn log n) time . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 , New Orleans, Louisiana, USA, January 7--9 , 2007 , Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 843--847. dl.acm.org\/citation.cfm?id&equals;1283383.1283473. Jan M. Hochstein and Karsten Weihe. 2007. Maximum s-t-flow with k crossings in O(kn log n) time. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7--9, 2007, Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 843--847. dl.acm.org\/citation.cfm?id&equals;1283383.1283473."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11533719_80"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.21845"},{"key":"e_1_2_1_37_1","first-page":"33","article-title":"Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica","volume":"16","author":"J\u00fcnger Michael","year":"1996","unstructured":"Michael J\u00fcnger and Petra Mutzel . 1996 . Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica . An International Journal in Computer Science 16 , 1 (1996), 33 -- 59 . Michael J\u00fcnger and Petra Mutzel. 1996. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica. An International Journal in Computer Science 16, 1 (1996), 33--59.","journal-title":"An International Journal in Computer Science"},{"volume-title":"Technical Report RUU-CS-92-03. Department of Computer Science","author":"Kant Goos","key":"e_1_2_1_38_1","unstructured":"Goos Kant . 1992. An O(n<sup>2<\/sup>) Maximal Planarization Algorithm Based on PQ-trees. Technical Report RUU-CS-92-03. Department of Computer Science , Utrecht University , P.O. Box 80.089, 3508 TB Utrecht, the Netherlands. Goos Kant. 1992. An O(n<sup>2<\/sup>) Maximal Planarization Algorithm Based on PQ-trees. Technical Report RUU-CS-92-03. Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, the Netherlands."},{"key":"e_1_2_1_39_1","volume-title":"Tech. Rep. ZIB-Report 00-37. Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin, Takustr. 7","author":"Koch T.","year":"2000","unstructured":"T. Koch , A. Martin , and S. Vo\u00df . 2000 . SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Tech. Rep. ZIB-Report 00-37. Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin, Takustr. 7 , Berlin . elib.zib.de\/steinlib. T. Koch, A. Martin, and S. Vo\u00df. 2000. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Tech. Rep. ZIB-Report 00-37. Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin, Takustr. 7, Berlin. elib.zib.de\/steinlib."},{"key":"e_1_2_1_40_1","volume-title":"Sur le probl\u00e8me des courbes gauches en topologie.Fundamenta Mathematicae 15","author":"Kuratowski Kazimierz","year":"1930","unstructured":"Kazimierz Kuratowski . 1930. Sur le probl\u00e8me des courbes gauches en topologie.Fundamenta Mathematicae 15 ( 1930 ), 271--283. Kazimierz Kuratowski. 1930. Sur le probl\u00e8me des courbes gauches en topologie.Fundamenta Mathematicae 15 (1930), 271--283."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.37236\/464"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory and Computing","author":"Liu P. C.","year":"1979","unstructured":"P. C. Liu and R. C. Geldmacher . 1979. On the deletion of nonplanar edges of a graph . In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory and Computing ( Florida Atlantic Univ., Boca Raton, Fla. , 1979 ) (Congress. Numer., XXIII--XXIV). Utilitas Math., Winnipeg, Man., 727--738. P. C. Liu and R. C. Geldmacher. 1979. On the deletion of nonplanar edges of a graph. In Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979) (Congress. Numer., XXIII--XXIV). Utilitas Math., Winnipeg, Man., 727--738."},{"volume-title":"Librairie Scientifique et Technique Albert Blanchard","author":"Lucas \u00c9douard","key":"e_1_2_1_43_1","unstructured":"\u00c9douard Lucas . 1960. R\u00e9cr\u00e9ations Math\u00e9matiques . Librairie Scientifique et Technique Albert Blanchard , Paris . xxv+254 pages. gallica.bnf.fr\/ark:\/12148\/bpt6k3943s\/f72.image \u00c9douard Lucas. 1960. R\u00e9cr\u00e9ations Math\u00e9matiques. Librairie Scientifique et Technique Albert Blanchard, Paris. xxv+254 pages. gallica.bnf.fr\/ark:\/12148\/bpt6k3943s\/f72.image"},{"key":"e_1_2_1_44_1","first-page":"17","article-title":"The SCIP Optimization Suite 4.0","author":"Maher Stephen J.","year":"2017","unstructured":"Stephen J. Maher , Tobias Fischer , Tristan Gally , Gerald Gamrath , Ambros Gleixner , Robert Lion Gottwald , Gregor Hendel , Thorsten Koch , Marco E. L\u00fcbbecke , Matthias Miltenberger , Benjamin M\u00fcller , Marc E. Pfetsch , Christian Puchert , Daniel Rehfeldt , Sebastian Schenker , Robert Schwarz , Felipe Serrano , Yuji Shinano , Dieter Weninger , Jonas T. Witt , and Jakob Witzig . 2017 . The SCIP Optimization Suite 4.0 . Tech. Rep. 17 - 12 . ZIB, Takustr. 7, 14195 Berlin. Stephen J. Maher, Tobias Fischer, Tristan Gally, Gerald Gamrath, Ambros Gleixner, Robert Lion Gottwald, Gregor Hendel, Thorsten Koch, Marco E. L\u00fcbbecke, Matthias Miltenberger, Benjamin M\u00fcller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Dieter Weninger, Jonas T. Witt, and Jakob Witzig. 2017. The SCIP Optimization Suite 4.0. Tech. Rep. 17-12. ZIB, Takustr. 7, 14195 Berlin.","journal-title":"Tech. Rep."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01545513"},{"key":"e_1_2_1_47_1","unstructured":"Stephen C. North. 1995. 5114 directed graphs. Manuscript.  Stephen C. North. 1995. 5114 directed graphs. Manuscript."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1080\/002075499191760"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207160410001684352"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1466514.1466524"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195439"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199705)29:3<173::AID-NET5>3.0.CO;2-E"},{"key":"e_1_2_1_53_1","volume-title":"Planar graphs and poset dimension. Order. A Journal on the Theory of Ordered Sets and its Applications 5, 4","author":"Schnyder Walter","year":"1989","unstructured":"Walter Schnyder . 1989. Planar graphs and poset dimension. Order. A Journal on the Theory of Ordered Sets and its Applications 5, 4 ( 1989 ), 323--343. Walter Schnyder. 1989. Planar graphs and poset dimension. Order. A Journal on the Theory of Ordered Sets and its Applications 5, 4 (1989), 323--343."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003867"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-16-1-386-389"},{"key":"e_1_2_1_56_1","volume-title":"A near-optimum parallel planarization algorithm. Science 245, 4923","author":"Takefuji Yoshiyasu","year":"1989","unstructured":"Yoshiyasu Takefuji and Kuo Chun Lee . 1989. A near-optimum parallel planarization algorithm. Science 245, 4923 ( 1989 ), 1221--1223. Yoshiyasu Takefuji and Kuo Chun Lee. 1989. A near-optimum parallel planarization algorithm. Science 245, 4923 (1989), 1221--1223."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.103509"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/21.87055"},{"key":"e_1_2_1_59_1","first-page":"187","article-title":"Le probl\u00e8me des labyrinthes. Nouvelles annales de math\u00e9matiques: journal des candidats aux \u00e9coles polytechnique et normale","volume":"3","author":"Tarry Gaston","year":"1895","unstructured":"Gaston Tarry . 1895 . Le probl\u00e8me des labyrinthes. Nouvelles annales de math\u00e9matiques: journal des candidats aux \u00e9coles polytechnique et normale , S\u00e9rie 3 14 (1895), 187 -- 190 . numdam.org\/article\/NAM_1895_3_14__187_1.pdf. Gaston Tarry. 1895. Le probl\u00e8me des labyrinthes. Nouvelles annales de math\u00e9matiques: journal des candidats aux \u00e9coles polytechnique et normale, S\u00e9rie 3 14 (1895), 187--190. numdam.org\/article\/NAM_1895_3_14__187_1.pdf.","journal-title":"S\u00e9rie"},{"key":"e_1_2_1_60_1","first-page":"244","article-title":"Planarity and duality of finite and infinite graphs. Journal of Combinatorial Theory","volume":"29","author":"Thomassen Carsten","year":"1980","unstructured":"Carsten Thomassen . 1980 . Planarity and duality of finite and infinite graphs. Journal of Combinatorial Theory . Series B 29 , 2 (1980), 244 -- 271 . Carsten Thomassen. 1980. Planarity and duality of finite and infinite graphs. Journal of Combinatorial Theory. Series B 29, 2 (1980), 244--271.","journal-title":"Series B"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/81.989179"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/646246.684703"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24553-4_55"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3320344","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3320344","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:57Z","timestamp":1750204437000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3320344"}},"subtitle":["New Models and Experiments"],"short-title":[],"issued":{"date-parts":[[2019,4,25]]},"references-count":61,"alternative-id":["10.1145\/3320344"],"URL":"https:\/\/doi.org\/10.1145\/3320344","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,4,25]]}}}