{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:31:52Z","timestamp":1771036312238,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,15]],"date-time":"2016-08-15T00:00:00Z","timestamp":1471219200000},"content-version":"unspecified","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":[[2017,10]]},"DOI":"10.1007\/s00453-016-0200-5","type":"journal-article","created":{"date-parts":[[2016,8,15]],"date-time":"2016-08-15T14:38:51Z","timestamp":1471271931000},"page":"401-427","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs"],"prefix":"10.1007","volume":"79","author":[{"given":"Michael A.","family":"Bekos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sabine","family":"Cornelsen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Grilli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seok-Hee","family":"Hong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,15]]},"reference":[{"issue":"3","key":"200_CR1","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00454-009-9143-9","volume":"41","author":"E Ackerman","year":"2009","unstructured":"Ackerman, E.: On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom. 41(3), 365\u2013375 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"200_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01196127","volume":"17","author":"PK Agarwal","year":"1997","unstructured":"Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17(1), 1\u20139 (1997)","journal-title":"Combinatorica"},{"issue":"2","key":"200_CR3","doi-asserted-by":"crossref","first-page":"569","DOI":"10.7155\/jgaa.00274","volume":"16","author":"EN Argyriou","year":"2012","unstructured":"Argyriou, E.N., Bekos, M.A., Symvonis, A.: The straight-line RAC drawing problem is np-hard. J. Graph Algorithms Appl. 16(2), 569\u2013597 (2012)","journal-title":"J. Graph Algorithms Appl."},{"key":"200_CR4","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.) GD 2013. LNCS, vol. 8242, pp. 107\u2013118. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-319-03841-4_10"},{"key":"200_CR5","doi-asserted-by":"crossref","unstructured":"Bekos, M.A., Cornelsen, S., Grilli, L., Hong, S.-H., Kaufmann, M.: On the recognition of fan-planar and maximal outer-fan-planar graphs. In: Duncan, C., Symvonis, A. (eds.) GD\u201914. LNCS, vol. 8871, pp. 198\u2013209. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-45803-7_17"},{"key":"200_CR6","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.tcs.2015.04.020","volume":"589","author":"C Binucci","year":"2015","unstructured":"Binucci, C., Di Giacomo, E., Didimo, W., Montecchiani, F., Patrignani, M., Symvonis, A., Tollis, I.G.: Fan-planarity: properties and complexity. Theor. Comput. Sci. 589, 76\u201386 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"200_CR7","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/mana.3211170125","volume":"117","author":"R Bodendiek","year":"1984","unstructured":"Bodendiek, R., Schumacher, H., Wagner, K.: \u00dcber 1-optimale graphen. Mathematische Nachrichten 117(1), 323\u2013339 (1984)","journal-title":"Mathematische Nachrichten"},{"key":"200_CR8","doi-asserted-by":"crossref","unstructured":"Cabello, S., Mohar, B.: Adding one edge to planar graphs makes crossing number and 1-planarity hard. CoRR. arXiv:1203.5944 (2012)","DOI":"10.1137\/120872310"},{"key":"200_CR9","doi-asserted-by":"crossref","unstructured":"Cheong, O., Har-Peled, S., Kim, H., Kim H.-S.: On the number of edges of fan-crossing free graphs. In: Leizhen, C., Siu-Wing, C., Tak\u00a0Wah, L. (eds.) ISAAC 2013, volume 8283 of LNCS, pp. 163\u2013173. Springer, Heidelberg, (2013)","DOI":"10.1007\/978-3-642-45030-3_16"},{"issue":"6","key":"200_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."},{"issue":"34","key":"200_CR11","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0925-7721(98)00039-X","volume":"11","author":"O Devillers","year":"1998","unstructured":"Devillers, O., Liotta, G., Preparata, F.P., Tamassia, R.: Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. 11(34), 187\u2013208 (1998)","journal-title":"Comput. Geom."},{"issue":"39","key":"200_CR12","doi-asserted-by":"crossref","first-page":"5156","DOI":"10.1016\/j.tcs.2011.05.025","volume":"412","author":"W Didimo","year":"2011","unstructured":"Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. Theor. Comput. Sci. 412(39), 5156\u20135166 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"200_CR13","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."},{"issue":"7\u20138","key":"200_CR14","doi-asserted-by":"crossref","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":"200_CR15","first-page":"149","volume":"29","author":"R Eggleton","year":"1986","unstructured":"Eggleton, R.: Rectilinear drawings of graphs. Utilitas Math. 29, 149\u2013172 (1986)","journal-title":"Utilitas Math."},{"issue":"7\u20138","key":"200_CR16","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. Discrete Math. 307(7\u20138), 854\u2013865 (2007)","journal-title":"Discrete Math."},{"key":"200_CR17","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representations of planar graphs. Acta Sci. Math. Szeged 11, 229\u2013233 (1948)","journal-title":"Acta Sci. Math. Szeged"},{"issue":"1","key":"200_CR18","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/110858586","volume":"27","author":"J Fox","year":"2013","unstructured":"Fox, J., Pach, J., Suk, A.: The number of edges in k-quasi-planar graphs. SIAM J. Discrete Math. 27(1), 550\u2013561 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"200_CR19","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. W. H. Freeman & Co., New York (1979)"},{"issue":"3","key":"200_CR20","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is np-complete. SIAM J. Algebr. Discrete Methods 4(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"1","key":"200_CR21","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":"200_CR22","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77\u201390. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44541-2_8"},{"key":"200_CR23","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.) GD 2013. LNCS, vol. 8242, pp. 71\u201382. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-319-03841-4_7"},{"key":"200_CR24","doi-asserted-by":"crossref","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.) COCOON. LNCS, vol. 7434, pp. 335\u2013346. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-32241-9_29"},{"key":"200_CR25","unstructured":"Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR. arXiv:1403.6184 (2014)"},{"issue":"1","key":"200_CR26","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF02187912","volume":"3","author":"DG Kirkpatrick","year":"1988","unstructured":"Kirkpatrick, D.G.: Establishing order in planar subdivisions. Discrete Comput. Geom. 3(1), 267\u2013280 (1988)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"200_CR27","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. Graph Theory 72(1), 30\u201371 (2013)","journal-title":"J. Graph Theory"},{"key":"200_CR28","unstructured":"Nagamochi, H.: Straight-line drawability of embedded graphs. Technical Reports 2013-005, Department of Applied Mathematics and Physics, Kyoto University (2013)"},{"key":"200_CR29","doi-asserted-by":"crossref","unstructured":"Pach, J., Radoicic, R., T\u00f3th, G.: Relaxing planarity for topological graphs. In: Akiyama, J., Kano, M. (eds.) JCDCG 2002. LNCS, vol. 2866, pp. 221\u2013232. Springer, Heidelberg (2002)","DOI":"10.1007\/978-3-540-44400-8_24"},{"issue":"3","key":"200_CR30","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"},{"issue":"2","key":"200_CR31","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0953-5438(00)00032-1","volume":"13","author":"HC Purchase","year":"2000","unstructured":"Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interact. Comput. 13(2), 147\u2013162 (2000)","journal-title":"Interact. Comput."},{"key":"200_CR32","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":"3","key":"200_CR33","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. Graph Theory 12(3), 335\u2013341 (1988)","journal-title":"J. Graph Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0200-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0200-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0200-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0200-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T15:25:24Z","timestamp":1568301924000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0200-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,15]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["200"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0200-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,15]]}}}