{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:36:05Z","timestamp":1777520165396,"version":"3.51.4"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T00:00:00Z","timestamp":1429660800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,4,22]],"date-time":"2015-04-22T00:00:00Z","timestamp":1429660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00453-015-0002-1","type":"journal-article","created":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T19:26:13Z","timestamp":1429644373000},"page":"1293-1320","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":43,"title":["Outer 1-Planar Graphs"],"prefix":"10.1007","volume":"74","author":[{"given":"Christopher","family":"Auer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Bachmaier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franz J.","family":"Brandenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Glei\u00dfner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathrin","family":"Hanauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Neuwirth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Josef","family":"Reislhuber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,22]]},"reference":[{"key":"2_CR1","first-page":"83","volume-title":"Graph Grawing, GD 2013, Lecture Notes in Computer Science","author":"MJ Alam","year":"2014","unstructured":"Alam, M.J., Brandenburg, F.J., Kobourov, S.G.: Straight-line drawings of 3-connected 1-planar graphs. In: Wismath, S., Wolff, A. (eds.) Graph Grawing, GD 2013, Lecture Notes in Computer Science, vol. 8242, pp. 83\u201394. Springer, Berlin (2014)"},{"key":"2_CR2","first-page":"429","volume":"21","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable. Part I. discharging. Ill. J. Math. 21, 429\u2013490 (1977)","journal-title":"Ill. J. Math."},{"key":"2_CR3","first-page":"491","volume":"21","author":"K Appel","year":"1977","unstructured":"Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. Part II. reducibility. Illinois Journal of Mathematics 21, 491\u2013567 (1977)","journal-title":"Illinois Journal of Mathematics"},{"issue":"1","key":"2_CR4","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for $$K$$-hard problems restricted to partial $$k$$-trees. Discrete Appl. Math. 23(1), 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"key":"2_CR5","first-page":"107","volume-title":"Graph Grawing, GD 2013, Lecture Notes in Computer Science","author":"C Auer","year":"2014","unstructured":"Auer, C., Bachmaier, C., Brandenburg, F.J., Glei\u00dfner, A., Hanauer, K., Neuwirth, D., Josef, R.: Recognizing outer 1-planar graphs in linear time. In: Wismath, S., Wolff, A. (eds.) Graph Grawing, GD 2013, Lecture Notes in Computer Science, vol. 8242, pp. 107\u2013118. Springer, Berlin (2014)"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Auer, C., Brandenburg, F.J., Glei\u00dfner, A., Reislhuber, J.: 1-planarity of graphs with a rotation system. J. Graph Algorithms Appl. 19(1), 67\u201386 (2015)","DOI":"10.7155\/jgaa.00347"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F.., Solis-Oba, R., Sack, J.R. (eds.) WADS 2013, pp. 97\u2013108. (2013)","DOI":"10.1007\/978-3-642-40104-6_9"},{"issue":"3","key":"2_CR8","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F Bernhard","year":"1979","unstructured":"Bernhard, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory Ser. B 27(3), 320\u2013331 (1979)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00454-010-9310-z","volume":"45","author":"TC Biedl","year":"2011","unstructured":"Biedl, T.C.: Small drawings of outerplanar graphs, series\u2013parallel graphs, and other planar graphs. Discrete Comput. Geom. 45(1), 141\u2013160 (2011)","journal-title":"Discrete Comput. Geom."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Bodendiek, R., Schumacher, H., Wagner, K.: Bemerkungen zu einem Sechsfarbenproblem von G. Ringel. Abh. aus dem Math. Seminar der Univ. Hamburg, vol. 53, pp. 41\u201352. (1983)","DOI":"10.1007\/BF02941309"},{"issue":"6","key":"2_CR11","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithms for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"2_CR12","first-page":"327","volume-title":"Graph Grawing, GD 2012, Lecture Notes in Computer Science","author":"FJ Brandenburg","year":"2013","unstructured":"Brandenburg, F.J., Eppstein, D., Glei\u00dfner, A., Goodrich, M.T., Hanauer, K., Reislhuber, J.: On the density of maximal 1-planar graphs. In: Didimo, W., Patrignani, M. (eds.) Graph Grawing, GD 2012, Lecture Notes in Computer Science, vol. 7704, pp. 327\u2013338. Springer, Berlin (2013)"},{"key":"2_CR13","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"issue":"5","key":"2_CR14","doi-asserted-by":"publisher","first-page":"1803","DOI":"10.1137\/120872310","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput. 42(5), 1803\u20131829 (2013)","journal-title":"SIAM J. Comput."},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41\u201351 (1990)","DOI":"10.1007\/BF02122694"},{"issue":"6","key":"2_CR16","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1142\/S021819591250015X","volume":"22","author":"HR Dehkordi","year":"2012","unstructured":"Dehkordi, H.R., Eades, P.: Every outer-1-plane graph has a right angle crossing drawing. J. Comput. Geom. Appl. 22(6), 543\u2013558 (2012)","journal-title":"J. Comput. Geom. Appl."},{"issue":"5","key":"2_CR17","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"2_CR18","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Di Battista","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Englewood Cliffs (1999)"},{"issue":"1","key":"2_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00453-007-9117-3","volume":"54","author":"G Di Battista","year":"2009","unstructured":"Di Battista, G., Frati, F.: Small area drawings of outerplanar graphs. Algorithmica 54(1), 25\u201353 (2009)","journal-title":"Algorithmica"},{"issue":"6","key":"2_CR20","doi-asserted-by":"publisher","first-page":"2243","DOI":"10.1137\/130908051","volume":"42","author":"G Di Battista","year":"2013","unstructured":"Di Battista, G., Frati, F., Pach, J.: On the queue number of planar graphs. SIAM J. Comput. 42(6), 2243\u20132285 (2013)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"2_CR21","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.ipl.2013.01.013","volume":"113","author":"W Didimo","year":"2013","unstructured":"Didimo, W.: Density of straight-line 1-planar graph drawings. Inf. Process. Lett. 113(7), 236\u2013240 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"2_CR22","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1137\/S0097539702416141","volume":"34","author":"V Dujmovi\u0107","year":"2005","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. Comput. 34(3), 553\u2013579 (2005)","journal-title":"SIAM J. Comput."},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2013.09.029","volume":"513","author":"P Eades","year":"2013","unstructured":"Eades, P., Hong, S.H., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: Testing maximal 1-planarity of graphs with a rotation system in linear time. Theor. Comput. Sci. 513, 65\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"7\u20138","key":"2_CR24","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1016\/j.dam.2012.11.019","volume":"161","author":"P Eades","year":"2013","unstructured":"Eades, P., Liotta, G.: Right angle crossing graphs and 1-planarity. Discrete Appl. Math. 161(7\u20138), 961\u2013969 (2013)","journal-title":"Discrete Appl. Math."},{"key":"2_CR25","first-page":"149","volume":"29","author":"RB Eggleton","year":"1986","unstructured":"Eggleton, R.B.: Rectilinear drawings of graphs. Util. Math. 29, 149\u2013172 (1986)","journal-title":"Util. Math."},{"issue":"7\u20138","key":"2_CR26","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1016\/j.disc.2005.11.056","volume":"307","author":"I Fabrici","year":"2007","unstructured":"Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Math. 307(7\u20138), 854\u2013865 (2007)","journal-title":"Discrete Math."},{"issue":"9","key":"2_CR27","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1016\/j.comgeo.2010.03.007","volume":"45","author":"F Frati","year":"2012","unstructured":"Frati, F.: Straight-line drawings of outerplanar graphs in $${\\fancyscript {O}}$$(dn logn) area. Comput. Geom. 45(9), 524\u2013533 (2012)","journal-title":"Comput. Geom."},{"key":"2_CR28","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"2_CR29","first-page":"77","volume-title":"Graph Drawing, GD 2000. Lecture Notes in Computer Science","author":"C Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) Graph Drawing, GD 2000. Lecture Notes in Computer Science, vol. 1984, pp. 77\u201390. Springer, Berlin (2001)"},{"issue":"5","key":"2_CR30","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1137\/0221055","volume":"21","author":"LS Heath","year":"1992","unstructured":"Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927\u2013958 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR31","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/j.jctb.2005.09.009","volume":"96","author":"P Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Crossing number is hard for cubic graphs. J. Comb. Theory Ser. B 96(4), 455\u2013471 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"2_CR32","doi-asserted-by":"crossref","unstructured":"Hong, S.H., Eades, P., Naoki, K., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. Algorithmica (2014). Published online","DOI":"10.1007\/978-3-319-03841-4_7"},{"key":"2_CR33","first-page":"335","volume-title":"Computing and Combinatorics Conference, COCOON 2012, Lecture Notes in Computer Science","author":"SH Hong","year":"2012","unstructured":"Hong, S.H., Eades, P., Liotta, G., Poon, S.H.: F\u00e1ry\u2019s theorem for 1-planar graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Computing and Combinatorics Conference, COCOON 2012, Lecture Notes in Computer Science, vol. 7434, pp. 335\u2013346. Springer, Berlin (2012)"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1002\/jgt.21630","volume":"72","author":"VP Korzhik","year":"2013","unstructured":"Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersion and hardness of 1-planarity testing. J. Graph Theory 72, 30\u201371 (2013)","journal-title":"J. Graph Theory"},{"issue":"3","key":"2_CR35","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1215\/S0012-7094-37-00336-3","volume":"3","author":"S Mac Lane","year":"1937","unstructured":"Mac Lane, S.: A structural characterization of planar combinatorial graphs. Duke Math. J. 3(3), 460\u2013472 (1937)","journal-title":"Duke Math. J."},{"issue":"5","key":"2_CR36","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"SL Mitchell","year":"1979","unstructured":"Mitchell, S.L.: Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Inf. Process. Lett. 9(5), 229\u2013232 (1979)","journal-title":"Inf. Process. Lett."},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with a few crossings per edge. Combinatorica 17, 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"2_CR38","doi-asserted-by":"crossref","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. aus dem Math. Seminar der Univ. Hamburg, vol. 29, pp. 107\u2013117 (1965)","DOI":"10.1007\/BF02996313"},{"key":"2_CR39","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 138\u2013147. SIAM (1990)"},{"key":"2_CR40","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0095-8956(80)90083-0","volume":"29","author":"C Thomassen","year":"1980","unstructured":"Thomassen, C.: Planarity and duality of finite and infinite graphs. J. Comb. Theory Ser. B 29, 244\u2013271 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"2_CR41","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1002\/jgt.3190050304","volume":"5","author":"C Thomassen","year":"1981","unstructured":"Thomassen, C.: Kuratowski\u2019s theorem. J. Graph Theory 5(3), 225\u2013241 (1981)","journal-title":"J. Graph Theory"},{"issue":"3","key":"2_CR42","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1002\/jgt.3190120306","volume":"12","author":"C Thomassen","year":"1988","unstructured":"Thomassen, C.: Rectilinear drawings of graphs. J. Graph Theory 12(3), 335\u2013341 (1988)","journal-title":"J. Graph Theory"},{"key":"2_CR43","unstructured":"Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. Tech. Rep. 298, Department of EECS, Princeton University (1982)"},{"issue":"4","key":"2_CR44","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1145\/1634.322451","volume":"31","author":"SG Williamson","year":"1984","unstructured":"Williamson, S.G.: Depth-first search and Kuratowski subgraphs. J. ACM 31(4), 681\u2013693 (1984)","journal-title":"J. ACM"}],"updated-by":[{"DOI":"10.1007\/s00453-021-00874-z","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,9,26]],"date-time":"2021-09-26T00:00:00Z","timestamp":1632614400000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0002-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-015-0002-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0002-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0002-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,26]],"date-time":"2021-09-26T07:04:16Z","timestamp":1632639856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-015-0002-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,22]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["2"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0002-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,22]]},"assertion":[{"value":"14 November 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00453-021-00874-z","URL":"https:\/\/doi.org\/10.1007\/s00453-021-00874-z","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}