{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:02Z","timestamp":1759638422962},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319687049"},{"type":"electronic","value":"9783319687056"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68705-6_5","type":"book-chapter","created":{"date-parts":[[2017,11,1]],"date-time":"2017-11-01T06:06:22Z","timestamp":1509516382000},"page":"59-74","source":"Crossref","is-referenced-by-count":6,"title":["On the Relationship Between k-Planar and k-Quasi-Planar Graphs"],"prefix":"10.1007","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[]},{"given":"Michael A.","family":"Bekos","sequence":"additional","affiliation":[]},{"given":"Franz J.","family":"Brandenburg","sequence":"additional","affiliation":[]},{"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[]},{"given":"Walter","family":"Didimo","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]},{"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[]},{"given":"Ignaz","family":"Rutter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,2]]},"reference":[{"issue":"3","key":"5_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":"3","key":"5_CR2","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/j.jcta.2006.08.002","volume":"114","author":"E Ackerman","year":"2007","unstructured":"Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. J. Comb. Theory Ser. A 114(3), 563\u2013571 (2007)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"1","key":"5_CR3","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"},{"key":"5_CR4","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$$ k -planar and $$k$$ k -quasi planar graphs. CoRR, abs\/1702.08716 (2017)","DOI":"10.1007\/978-3-319-68705-6_5"},{"issue":"2","key":"5_CR5","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.comgeo.2014.08.001","volume":"48","author":"P Angelini","year":"2015","unstructured":"Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Roselli, V.: Relaxing the constraints of clustered planarity. Comput. Geom. 48(2), 42\u201375 (2015)","journal-title":"Comput. Geom."},{"key":"5_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-662-45803-7_17","volume-title":"Graph Drawing","author":"MA Bekos","year":"2014","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 2014. LNCS, vol. 8871, pp. 198\u2013209. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-45803-7_17"},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-319-50106-2_27","volume-title":"Graph Drawing and Network Visualization","author":"MA Bekos","year":"2016","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.) GD 2016. LNCS, vol. 9801, pp. 344\u2013356. Springer, Cham (2016). doi: 10.1007\/978-3-319-50106-2_27"},{"key":"5_CR8","unstructured":"Bekos, M.A., Kaufmann, M., Raftopoulou, C.N.: On optimal 2- and 3-planar graphs. In: Aronov, B., Katz, M.J. (eds.) SoCG 2017. LIPIcs, vol. 77, p. 16:1. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"1","key":"5_CR9","doi-asserted-by":"crossref","first-page":"81","DOI":"10.7155\/jgaa.00398","volume":"21","author":"C Binucci","year":"2017","unstructured":"Binucci, C., Chimani, M., Didimo, W., Gronemann, M., Klein, K., Kratochv\u00edl, J., Montecchiani, F., Tollis, I.G.: Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus. J. Graph Algorithms Appl. 21(1), 81\u2013102 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"5_CR10","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":"3","key":"5_CR11","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.026","volume":"636","author":"FJ Brandenburg","year":"2016","unstructured":"Brandenburg, F.J., Didimo, W., Evans, W.S., Kindermann, P., Liotta, G., Montecchiani, F.: Recognizing and drawing IC-planar graphs. Theor. Comput. Sci. 636, 1\u201316 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR13","first-page":"43","volume-title":"Handbook on Graph Drawing and Visualization","author":"C Buchheim","year":"2013","unstructured":"Buchheim, C., Chimani, M., Gutwenger, C., J\u00fcnger, M., Mutzel, P.: Crossings and planarization. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 43\u201385. Chapman and Hall\/CRC, Boca Raton (2013)"},{"issue":"1","key":"5_CR14","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0095-8956(92)90003-G","volume":"56","author":"V Capoyleas","year":"1992","unstructured":"Capoyleas, V., Pach, J.: A Tur\u00e1n-type theorem on chords of a convex polygon. J. Comb. Theory Ser. B 56(1), 9\u201315 (1992)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"5_CR15","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1007\/s00453-014-9935-z","volume":"73","author":"O Cheong","year":"2015","unstructured":"Cheong, O., Har-Peled, S., Kim, H., Kim, H.: On the number of edges of fan-crossing free graphs. Algorithmica 73(4), 673\u2013695 (2015)","journal-title":"Algorithmica"},{"key":"5_CR16","volume-title":"Graph Drawing","author":"G Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Didimo, W., Liotta, G.: Mining graph data. In: Graph Visualization and Data Mining, pp. 35\u201364. Wiley, Hoboken (2007)","DOI":"10.1002\/9780470073049.ch3"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-1-4614-0110-0_10","volume-title":"Thirty Essays on Geometric Graph Theory","author":"W Didimo","year":"2013","unstructured":"Didimo, W., Liotta, G.: The crossing-angle resolution in graph drawing. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 167\u2013184. Springer, New York (2013). doi: 10.1007\/978-1-4614-0110-0_10"},{"issue":"7\u20138","key":"5_CR19","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."},{"issue":"5","key":"5_CR20","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1016\/j.ejc.2011.09.021","volume":"33","author":"J Fox","year":"2012","unstructured":"Fox, J., Pach, J.: Coloring $$K_k$$ K k -free-free intersection graphs of geometric objects in the plane. Eur. J. Comb. 33(5), 853\u2013866 (2012)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"5_CR21","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$$ k -quasi-planar graphs. SIAM J. Discrete Math. 27(1), 550\u2013561 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"5_CR22","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. Algebraic Discrete Methods 4(3), 312\u2013316 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"5_CR23","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Two-planar graphs are quasiplanar. CoRR, abs\/1705.05569. Accepted at MFCS 2017 (2017)"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Hong, S., Tokuyama, T.: Algorithmics for beyond planar graphs. NII Shonan Meeting Seminar 089, 27 November\u20131 December 2016","DOI":"10.1007\/978-981-15-6533-5_1"},{"issue":"4","key":"5_CR25","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"JE Hopcroft","year":"1974","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"issue":"2","key":"5_CR26","doi-asserted-by":"crossref","first-page":"397","DOI":"10.7155\/jgaa.00152","volume":"11","author":"W Huang","year":"2007","unstructured":"Huang, W., Hong, S., Eades, P.: Effects of sociogram drawing conventions and edge crossings in social network visualization. J. Graph Algorithms Appl. 11(2), 397\u2013429 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"5_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18638-7","volume-title":"Graph Drawing Software","year":"2003","unstructured":"J\u00fcnger, M., Mutzel, P. (eds.): Graph Drawing Software. Springer, Heidelberg (2003). doi: 10.1007\/978-3-642-18638-7"},{"key":"5_CR28","unstructured":"Kaufmann, M., Kobourov, S., Pach, J., Hong, S.: Beyond planar graphs: algorithmic and combinatorics. Dagstuhl Seminar 16452, 6\u201311 November 2016"},{"key":"5_CR29","unstructured":"Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. CoRR, abs\/1403.6184 (2014)"},{"key":"5_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44969-8","volume-title":"Drawing Graphs","year":"2001","unstructured":"Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001). doi: 10.1007\/3-540-44969-8"},{"key":"5_CR31","unstructured":"Liotta, G.: Graph drawing beyond planarity: some results and open problems. In: ICTCS 2014. CEUR Workshop Proceedings, vol. 1231, pp. 3\u20138. CEUR-WS.org (2014)"},{"key":"5_CR32","unstructured":"Nishizeki, T., Chiba, N.: Planar Graphs: Theory and Algorithms. North-Holland Mathematics Studies. Elsevier Science (1988)"},{"key":"5_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-540-44400-8_24","volume-title":"Discrete and Computational Geometry","author":"J Pach","year":"2003","unstructured":"Pach, J., Radoi\u010di\u0107, 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 (2003). doi: 10.1007\/978-3-540-44400-8_24"},{"issue":"4","key":"5_CR34","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","volume":"36","author":"J Pach","year":"2006","unstructured":"Pach, J., Radoi\u010di\u0107, 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."},{"issue":"1","key":"5_CR35","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02086610","volume":"16","author":"J Pach","year":"1996","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica 16(1), 111\u2013117 (1996)","journal-title":"Algorithmica"},{"issue":"3","key":"5_CR36","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":"5_CR37","first-page":"194","volume":"9","author":"J Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Thirteen problems on crossing numbers. Geombinatorics 9, 194\u2013207 (2000)","journal-title":"Geombinatorics"},{"issue":"2","key":"5_CR38","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."},{"issue":"3","key":"5_CR39","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1023\/A:1016344215610","volume":"7","author":"HC Purchase","year":"2002","unstructured":"Purchase, H.C., Carrington, D.A., Allder, J.: Empirical evaluation of aesthetics-based graph layout. Empirical Softw. Eng. 7(3), 233\u2013255 (2002)","journal-title":"Empirical Softw. Eng."},{"key":"5_CR40","first-page":"1","volume":"DS21","author":"M Schaefer","year":"2014","unstructured":"Schaefer, M.: The graph crossing number and its variants: a survey. Electron. J. Combin. DS21, 1\u2013100 (2014)","journal-title":"Electron. J. Combin."},{"key":"5_CR41","doi-asserted-by":"crossref","DOI":"10.1142\/4902","volume-title":"Graph Drawing and Applications for Software and Knowledge Engineers","author":"K Sugiyama","year":"2002","unstructured":"Sugiyama, K.: Graph Drawing and Applications for Software and Knowledge Engineers. World Scientific, Singapore (2002)"},{"key":"5_CR42","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.comgeo.2015.06.001","volume":"50","author":"A Suk","year":"2015","unstructured":"Suk, A., Walczak, B.: New bounds on the maximum number of edges in $$k$$ k -quasi-planar graphs. Comput. Geom. 50, 24\u201333 (2015)","journal-title":"Comput. Geom."},{"volume-title":"Handbook of Graph Drawing and Visualization","year":"2013","key":"5_CR43","unstructured":"Tamassia, R. (ed.): Handbook of Graph Drawing and Visualization. Chapman and Hall\/CRC, Boca Raton (2013)"},{"key":"5_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-63938-1_63","volume-title":"Graph Drawing","author":"P Valtr","year":"1997","unstructured":"Valtr, P.: Graph drawing with no k pairwise crossing edges. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 205\u2013218. Springer, Heidelberg (1997). doi: 10.1007\/3-540-63938-1_63"},{"key":"5_CR45","unstructured":"Vr\u0165o, I.: Crossing numbers bibliography. www.ifi.savba.sk\/~imrich"},{"issue":"2","key":"5_CR46","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1057\/palgrave.ivs.9500013","volume":"1","author":"C Ware","year":"2002","unstructured":"Ware, C., Purchase, H.C., Colpoys, L., McGill, M.: Cognitive measurements of graph aesthetics. Inf. Vis. 1(2), 103\u2013110 (2002)","journal-title":"Inf. Vis."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68705-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T22:53:12Z","timestamp":1603234392000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68705-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687049","9783319687056"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68705-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}