{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T03:37:29Z","timestamp":1777520249315,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,5,29]],"date-time":"2014-05-29T00:00:00Z","timestamp":1401321600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00453-014-9890-8","type":"journal-article","created":{"date-parts":[[2014,5,28]],"date-time":"2014-05-28T19:03:11Z","timestamp":1401303791000},"page":"1033-1054","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["A Linear-Time Algorithm for Testing Outer-1-Planarity"],"prefix":"10.1007","volume":"72","author":[{"given":"Seok-Hee","family":"Hong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Eades","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naoki","family":"Katoh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yusuke","family":"Suzuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,29]]},"reference":[{"key":"9890_CR1","unstructured":"Alon, N., Feldheim, ON.: Drawing outerplanar graphs. (2012). arXiv:1208.0744 [math.CO]"},{"key":"9890_CR2","doi-asserted-by":"crossref","unstructured":"Auer, C., Bachmaier, C., Brandenburg, F.J., Glei\u00dfner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Recognizing outer 1-planar graphs in linear time. In: Wismath, S., Wolff, A. (eds.): Graph Drawing 21st International Symposium, GD 2013, Bordeaux, France, September 23\u201325, 2013, Revised Selected Papers, vol. 8242 of Lecture Notes in Computer Science, pp. 107\u2013118. Springer (2013)","DOI":"10.1007\/978-3-319-03841-4_10"},{"key":"9890_CR3","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, vol. 8037 of Lecture Notes in Computer Science, pp. 97\u2013108. Springer (2013)","DOI":"10.1007\/978-3-642-40104-6_9"},{"issue":"3","key":"9890_CR4","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F Bernhart","year":"1979","unstructured":"Bernhart, 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":"12","key":"9890_CR5","first-page":"108","volume":"41","author":"OV Borodin","year":"1984","unstructured":"Borodin, O.V.: Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs. Metody Diskret. Analiz 41(12), 108 (1984)","journal-title":"Metody Diskret. Analiz"},{"key":"9890_CR6","doi-asserted-by":"crossref","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. CoRR, abs\/1203.5944 (2012)","DOI":"10.1137\/120872310"},{"key":"9890_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Z.-Z., Kouno, M.: A linear-time algorithm for 7-coloring 1-planar graphs. Mathematical Foundations of Computer Science (MFCS) 2003. vol. 2747 of Lecture Notes in Computer Science, pp. 348\u2013357. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-45138-9_29"},{"issue":"4","key":"9890_CR8","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line maintenance of triconnected components with spqr-trees. Algorithmica 15(4), 302\u2013318 (1996)","journal-title":"Algorithmica"},{"key":"9890_CR9","doi-asserted-by":"crossref","unstructured":"Di Giacomo, E., Didimo, W., Liotta, L., Montecchiani, F.: h-quasi planar drawings of bounded treewidth graphs in linear area. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 7551 of Lecture Notes in Computer Science, pp. 91\u2013102. Springer (2012)","DOI":"10.1007\/978-3-642-34611-8_12"},{"issue":"6","key":"9890_CR10","doi-asserted-by":"crossref","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. Int. J. Comput. Geom. Appl. 22(6), 543\u2013558 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9890_CR11","first-page":"339","volume":"2012","author":"P Eades","year":"2012","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. Proc. Graph Draw. 2012, 339\u2013345 (2012)","journal-title":"Proc. Graph Draw."},{"key":"9890_CR12","doi-asserted-by":"crossref","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.: A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system. Theor. Comput. Sci. 513, 65\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9890_CR13","first-page":"149","volume":"29","author":"R Eggleton","year":"1986","unstructured":"Eggleton, R.: Rectilinear drawings of graphs. Util. Math. 29, 149\u2013172 (1986)","journal-title":"Util. Math."},{"issue":"7\u20138","key":"9890_CR14","doi-asserted-by":"crossref","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. Discret. Math. 307(7\u20138), 854\u2013865 (2007)","journal-title":"Discret. Math."},{"issue":"9","key":"9890_CR15","doi-asserted-by":"crossref","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 o(dn log n) area. Comput. Geom. 45(9), 524\u2013533 (2012)","journal-title":"Comput. Geom."},{"issue":"1","key":"9890_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-0010-x","volume":"49","author":"A Grigoriev","year":"2007","unstructured":"Grigoriev, A., Bodlaender, H.L.: Algorithms for graphs embeddable with few crossings per edge. Algorithmica 49(1), 1\u201311 (2007)","journal-title":"Algorithmica"},{"key":"9890_CR17","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of spqr-trees. In: Marks, J. (ed.) Graph Drawing, volume 1984 of Lecture Notes in Computer Science, pp. 77\u201390. Springer (2000)","DOI":"10.1007\/3-540-44541-2_8"},{"key":"9890_CR18","doi-asserted-by":"crossref","unstructured":"Hong, S.-H., Eades, P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y.: A linear-time algorithm for testing outer-1-planarity. In: Wismath, S., Wolff, A. (eds.): Graph Drawing 21st International Symposium, GD 2013, Bordeaux, France, September 23\u201325, 2013, Revised Selected Papers, vol. 8242 of Lecture Notes in Computer Science, pp. 71\u201382. Springer (2013)","DOI":"10.1007\/978-3-319-03841-4_7"},{"key":"9890_CR19","doi-asserted-by":"crossref","unstructured":"Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: F\u00e1ry\u2019s theorem for 1-planar graphs. In: Proc. of COCOON 2012, Lecture Notes in Computer Science, pp. 335\u2013346 (2012)","DOI":"10.1007\/978-3-642-32241-9_29"},{"key":"9890_CR20","unstructured":"Hong, S.-H., Nagamochi, H.: Two-page book embedding and clustered planarity. Technical Report 2009\u2013004, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University (2009)"},{"key":"9890_CR21","unstructured":"Hong, S.-H., Nagamochi, H.: Simpler testing for two-page book embedding of partitioned graphs. Technical Report 2013\u2013001, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University (2013)"},{"key":"9890_CR22","doi-asserted-by":"crossref","unstructured":"Hong, S.-H., Nagamochi, H.: Simpler algorithms for testing two-page book embedding of partitioned graphs. In: Proc. of COCOON 2014 (to appear)","DOI":"10.1007\/978-3-319-08783-2_41"},{"issue":"3","key":"9890_CR23","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"9890_CR24","doi-asserted-by":"crossref","unstructured":"Knauer, K.B., Micek, P., Walczak, B.: Outerplanar graph drawings with few slopes. In: Proc. of COCOON 2012, Lecture Notes in Computer Science, pp. 323\u2013334 (2012)","DOI":"10.1007\/978-3-642-32241-9_28"},{"issue":"1","key":"9890_CR25","doi-asserted-by":"crossref","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-immersions and hardness of 1-planarity testing. J. Gr. Theory 72(1), 30\u201371 (2013)","journal-title":"J. Gr. Theory"},{"issue":"3","key":"9890_CR26","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF01215922","volume":"17","author":"J Pach","year":"1997","unstructured":"Pach, J., T\u00f3th, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"9890_CR27","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF02996313","volume":"29","author":"G Ringel","year":"1965","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Sem. Univ. Hamburg 29, 107\u2013117 (1965)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"issue":"1","key":"9890_CR28","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.disc.2009.07.016","volume":"310","author":"Y Suzuki","year":"2010","unstructured":"Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces. Discret. Math. 310(1), 6\u201311 (2010)","journal-title":"Discret. Math."},{"issue":"4","key":"9890_CR29","doi-asserted-by":"crossref","first-page":"1527","DOI":"10.1137\/090746835","volume":"24","author":"Y Suzuki","year":"2010","unstructured":"Suzuki, Y.: Re-embeddings of maximum 1-planar graphs. SIAM J. Discret. Math. 24(4), 1527\u20131540 (2010)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"9890_CR30","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/jgt.3190120306","volume":"12","author":"C Thomassen","year":"1988","unstructured":"Thomassen, C.: Rectilinear drawings of graphs. J. Gr. Theory 12(3), 335\u2013341 (1988)","journal-title":"J. Gr. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9890-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9890-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9890-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T03:11:21Z","timestamp":1565493081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9890-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,29]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9890"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9890-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,29]]}}}