{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:45:15Z","timestamp":1742913915158,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":48,"publisher":"Springer Singapore","isbn-type":[{"type":"print","value":"9789811565328"},{"type":"electronic","value":"9789811565335"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-981-15-6533-5_7","type":"book-chapter","created":{"date-parts":[[2020,9,30]],"date-time":"2020-09-30T13:06:26Z","timestamp":1601471186000},"page":"109-130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$$\\textit{\\textbf{k}}$$-Planar Graphs"],"prefix":"10.1007","author":[{"given":"Michael A.","family":"Bekos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,1]]},"reference":[{"issue":"1","key":"7_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","volume":"15","author":"C Kuratowski","year":"1930","unstructured":"Kuratowski, C.: Sur le probl\u00e8me des courbes gauches en topologie. Fundamenta Mathematicae 15(1), 271\u2013283 (1930)","journal-title":"Fundamenta Mathematicae"},{"issue":"2","key":"7_CR2","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7155\/jgaa.00091","volume":"8","author":"JM Boyer","year":"2004","unstructured":"Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified O(n) planarity by edge addition. J. Graph Algorithms Appl. 8(2), 241\u2013273 (2004)","journal-title":"J. Graph Algorithms Appl."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"de\u00a0Fraysseix, H., de Mendez, P.O., Rosenstiehl, P.: Tr\u00e9maux trees and planarity. Int. J. Found. Comput. Sci. 17(5):1017\u20131030 (2006)","DOI":"10.1142\/S0129054106004248"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974)","DOI":"10.1145\/321850.321852"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Appel, K., Haken, W.: Every planar map is four colorable. part I: discharging. Illinois J. Math. 21(3):429\u2013490 (1977)","DOI":"10.1215\/ijm\/1256049011"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Appel, K., Haken, W., Koch, J.: Every planar map is four colorable. part II: Reducibility. Illinois J. Math. 21(3):491\u2013567 (1977)","DOI":"10.1215\/ijm\/1256049012"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Aigner, M., Ziegler, G. M.: Proofs from THE BOOK (3. ed.). Springer, Berlin (2004)","DOI":"10.1007\/978-3-662-05412-3"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02996313","volume":"29","author":"G Ringel","year":"1965","unstructured":"Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 29, 107\u2013117 (1965)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.dam.2014.05.025","volume":"175","author":"E Ackerman","year":"2014","unstructured":"Ackerman, E.: A note on 1-planar graphs. Discrete Appl. Math. 175, 104\u2013108 (2014)","journal-title":"Discrete Appl. Math."},{"key":"7_CR10","first-page":"12","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\u201326 (1984)","journal-title":"Metody Diskret. Analiz"},{"issue":"4","key":"7_CR11","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1002\/jgt.3190190406","volume":"19","author":"OV Borodin","year":"1995","unstructured":"Borodin, O.V.: A new proof of the 6 color theorem. J. Graph Theory 19(4), 507\u2013521 (1995)","journal-title":"J. Graph Theory"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Planar map graphs. In: Vitter, J.S. (ed.) STOC, pp. 514\u2013523. ACM (1998)","DOI":"10.1145\/276698.276865"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s00453-005-1184-8","volume":"45","author":"Z-Z Chen","year":"2006","unstructured":"Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Recognizing hole-free 4-map graphs in cubic time. Algorithmica 45(2), 227\u2013262 (2006)","journal-title":"Algorithmica"},{"issue":"4","key":"7_CR14","doi-asserted-by":"publisher","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. Discrete Math. 24(4), 1527\u20131540 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Von Bodendiek, R., Schumacher, H., Wagner, K.: Bemerkungen zu einem Sechsfarbenproblem von G. Ringel. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg 53(1):41\u201352 (1983)","DOI":"10.1007\/BF02941309"},{"issue":"1","key":"7_CR16","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/mana.3211170125","volume":"117","author":"R Von Bodendiek","year":"1984","unstructured":"Von Bodendiek, R., Schumacher, H., Wagner, K.: \u00dcber 1-optimale Graphen. Mathematische Nachrichten 117(1), 323\u2013339 (1984)","journal-title":"Mathematische Nachrichten"},{"issue":"3","key":"7_CR17","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/j.ipl.2010.11.001","volume":"111","author":"X Zhang","year":"2011","unstructured":"Zhang, X., Jianliang, W.: On edge colorings of 1-planar graphs. Inf. Process. Lett. 111(3), 124\u2013128 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"7_CR18","doi-asserted-by":"publisher","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"},{"issue":"1","key":"7_CR19","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-immersions and hardness of 1-planarity testing. J. Graph Theory 72(1), 30\u201371 (2013)","journal-title":"J. Graph Theory"},{"issue":"1","key":"7_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7155\/jgaa.00457","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23\u201349 (2018)","journal-title":"J. Graph Algorithms Appl."},{"issue":"5","key":"7_CR21","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":"7_CR22","unstructured":"Brandenburg, F.J.: On 4-map graphs and 1-planar graphs and their recognition problem (2015). \n              arXiv:1509.03447"},{"issue":"1","key":"7_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-016-0226-8","volume":"80","author":"FJ Brandenburg","year":"2018","unstructured":"Brandenburg, F.J.: Recognizing optimal 1-planar graphs in linear time. Algorithmica 80(1), 1\u201328 (2018)","journal-title":"Algorithmica"},{"issue":"3","key":"7_CR24","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":"7_CR25","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, Berlin (2012)","DOI":"10.1007\/978-3-642-32241-9_29"},{"key":"7_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.cosrev.2017.06.002","volume":"25","author":"SG Kobourov","year":"2017","unstructured":"Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bibliography on 1-planarity. Comput. Sci. Rev. 25, 49\u201367 (2017)","journal-title":"Comput. Sci. Rev."},{"issue":"1","key":"7_CR27","doi-asserted-by":"publisher","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. Discrete Math. 310(1), 6\u201311 (2010)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"7_CR28","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.disc.2005.10.005","volume":"305","author":"G Brinkmann","year":"2005","unstructured":"Brinkmann, G., Greenberg, S., Greenhill, C.S., McKay, B.D., Thomas, R., Wollan, P.: Generation of simple quadrangulations of the sphere. Discrete Math. 305(1\u20133), 33\u201354 (2005)","journal-title":"Discrete Math."},{"key":"7_CR29","unstructured":"Bekos, M.A., Kaufmann, M., Raftopoulou, C.N.: On optimal 2- and 3-planar graphs. In: Aronov, B., Katz, M.J. (eds.) SoCG, LIPIcs, vol. 77, pp. 16:1\u201316:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"3","key":"7_CR30","doi-asserted-by":"publisher","first-page":"417","DOI":"10.7155\/jgaa.00232","volume":"15","author":"M Hasheminezhad","year":"2011","unstructured":"Hasheminezhad, M., McKay, B.D., Reeves, T.: Recursive generation of simple planar 5-regular graphs and pentangulations. J. Graph Algorithms Appl. 15(3), 417\u2013436 (2011)","journal-title":"J. Graph Algorithms Appl."},{"key":"7_CR31","unstructured":"Urschel, J.C., Wellens, J.: Testing k-planarity is NP-complete (2019). \n              arXiv:1907.02104"},{"issue":"4","key":"7_CR32","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","volume":"36","author":"J Pach","year":"2006","unstructured":"Pach, J., Radoicic, R., Tardos, G., T\u00f3th, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36(4), 527\u2013552 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"7_CR33","unstructured":"Ackerman, E.: On topological graphs with at most four crossings per edge (2015). \n              arXiv:1509.01932"},{"issue":"3","key":"7_CR34","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 few crossings per edge. Combinatorica 17(3), 427\u2013439 (1997)","journal-title":"Combinatorica"},{"key":"7_CR35","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M.M., Szemer\u00e9di, E.: Crossing-free sub-graphs. In: Hammer, P.L., Rosa, A., Sabidussi, G., Turgeon, J. (eds.) Theory and Practice of Combinatorics, Number\u00a012 in North-Holland Mathematics Studies, pp. 9\u201312. North-Holland (1982)","DOI":"10.1016\/S0304-0208(08)73484-4"},{"key":"7_CR36","volume-title":"Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks","author":"Frank Thomson Leighton","year":"1983","unstructured":"Frank Thomson Leighton: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge (1983)"},{"issue":"1","key":"7_CR37","doi-asserted-by":"publisher","first-page":"141","DOI":"10.7151\/dmgt.1845","volume":"36","author":"J Czap","year":"2016","unstructured":"Czap, J., Przybylo, J., Skrabul\u2019\u00e1kov\u00e1, E.: On an extremal problem in the class of bipartite 1-planar graphs. Discuss. Math. Graph Theory 36(1), 141\u2013151 (2016)","journal-title":"Discuss. Math. Graph Theory"},{"key":"7_CR38","unstructured":"Angelini, P., Bekos, M.A., Kaufmann, M., Pfister, M., Ueckerdt, T.: Beyond-planarity: Tur\u00e1n-type results for non-planar bipartite graphs. In: Hsu, W.-L., Lee, D.-T., Liao, C.-S. (eds.) ISAAC, LIPIcs, vol. 123, pp. 28:1\u201328:13. Schloss Dagstuhl (2018)"},{"key":"7_CR39","doi-asserted-by":"crossref","unstructured":"Bekos, M.A., Kaufmann, M., Raftopoulou, C.N.: On the density of non-simple 3-planar graphs. In: Hu, Y., N\u00f6llenburg, M. (eds.) Graph Drawing and Network Visualization, LNCS, vol. 9801, pp. 344\u2013356. Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-50106-2_27"},{"key":"7_CR40","unstructured":"Bae, S.W., Baffier, J.-F., Chun, J., Eades, P., Eickmeyer, K., Grilli, L., Hong, S.-H., Korman, M., Montecchiani, F., Rutter, I., T\u00f3th, C.D.: Gap-planar graphs. Theor. Comput. Sci. 745, 36\u201352 (2018)"},{"key":"7_CR41","doi-asserted-by":"crossref","unstructured":"Auer, C., Brandenburg, F.-J., Glei\u00dfner, A., Hanauer, K.: On sparse maximal 2-planar graphs. In Didimo, W., Patrignani, M. (eds.) Graph Drawing, LNCS, vol. 7704, pp. 555\u2013556. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-36763-2_50"},{"key":"7_CR42","doi-asserted-by":"crossref","unstructured":"Chaplick, S., Kryven, M., Liotta, G., L\u00f6ffler, A., Wolff, A.: Beyond planarity. In: Frati, F., Ma, K.-L. (eds.) Graph Drawing and Network Visualization, LNCS, vol. 10692, pp. 546\u2013559. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-73915-1_42"},{"key":"7_CR43","doi-asserted-by":"crossref","unstructured":"Hong, S.-H., Nagamochi, H.: Testing full outer-2-planarity in linear time. In: Mayr, E.W. (ed.) WG, LNCS, vol. 9224, pp. 406\u2013421. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-53174-7_29"},{"issue":"4","key":"7_CR44","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G Di Battista","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":"7_CR45","doi-asserted-by":"crossref","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of spqr-trees. In: Marks, J. (ed.) Graph Drawing, LNCS, vol. 1984, pp. 77\u201390. Springer, Berlin (2000)","DOI":"10.1007\/3-540-44541-2_8"},{"issue":"4","key":"7_CR46","doi-asserted-by":"publisher","first-page":"1293","DOI":"10.1007\/s00453-015-0002-1","volume":"74","author":"C Auer","year":"2016","unstructured":"Auer, C., Bachmaier, C., Brandenburg, F.J., Glei\u00dfner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293\u20131320 (2016)","journal-title":"Algorithmica"},{"key":"7_CR47","doi-asserted-by":"crossref","unstructured":"Angelini, P., Bekos, M.A., Brandenburg, F.J., Da Lozzo, G., Di Battista, G., Didimo, W., Liotta, G., Montecchiani, F., Rutter, I.: On the relationship between k-planar and k-quasi-planar graphs. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG, LNCS, vol. 10520, pp. 59\u201374. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-68705-6_5"},{"key":"7_CR48","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Two-planar graphs are quasiplanar. In: Larsen, K.G., Bodlaender, H.L., Raskin, J.-F. (eds.) MFCS, LIPIcs, vol. 83, pp. 47:1\u201347:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"}],"container-title":["Beyond Planar Graphs"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-15-6533-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T15:03:21Z","timestamp":1601737401000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-981-15-6533-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9789811565328","9789811565335"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-981-15-6533-5_7","relation":{},"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"1 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}