{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T02:01:26Z","timestamp":1713405686687},"reference-count":66,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"name":"Giordano Da Lozzo","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,4,14]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The $2$-layer drawing model is a well-established paradigm to visualize bipartite graphs where vertices of the two parts lie on two horizontal lines and edges lie between these lines. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of $k$-planar graphs has been considered only for $k=1$ in this context. We provide several contributions that address this gap in the literature.<\/jats:p>\n               <jats:p>First, we show tight density bounds for the classes of $2$-layer $k$-planar graphs with $k\\in \\{2,3,4,5\\}$. Based on these results, we provide a Crossing Lemma for $2$-layer $k$-planar graphs, which then implies a general density bound for $2$-layer $k$-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between $k$-planarity and $h$-quasiplanarity in the $2$-layer model and show that $2$-layer $k$-planar graphs have pathwidth at most $k+1$ while there are also $2$-layer $k$-planar graphs with pathwidth at least $(k+3)\/2$.<\/jats:p>","DOI":"10.1093\/comjnl\/bxad038","type":"journal-article","created":{"date-parts":[[2023,4,22]],"date-time":"2023-04-22T13:00:01Z","timestamp":1682168401000},"page":"1005-1016","source":"Crossref","is-referenced-by-count":1,"title":["2-Layer <i>k<\/i>-Planar Graphs Density, Crossing Lemma, Relationships And Pathwidth"],"prefix":"10.1093","volume":"67","author":[{"given":"Patrizio","family":"Angelini","sequence":"first","affiliation":[{"name":"John Cabot University , Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[{"name":"Roma Tre University , Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"F\u00f6rster","sequence":"additional","affiliation":[{"name":"University of T\u00fcbingen , T\u00fcbingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schneck","sequence":"additional","affiliation":[{"name":"University of T\u00fcbingen , T\u00fcbingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"2024041716571616600_ref1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3301281","article-title":"A survey on graph drawing beyond planarity","volume":"52","author":"Didimo","year":"2019","journal-title":"ACM Comput. Surv."},{"key":"2024041716571616600_ref2","volume-title":"Beyond Planar Graphs, Communications of NII Shonan Meetings","year":"2020"},{"key":"2024041716571616600_ref3","first-page":"2","article-title":"Graphs","volume":"3","author":"Avital","year":"1966","journal-title":"Gilyonot Lematematika"},{"key":"2024041716571616600_ref4","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF02996313","article-title":"Ein Sechsfarbenproblem auf der kugel","volume":"29","author":"Ringel","year":"1965","journal-title":"Abh. Math. Sem. Univ. Hamb."},{"key":"2024041716571616600_ref5","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF01215922","article-title":"Graphs drawn with few crossings per edge","volume":"17","author":"Pach","year":"1997","journal-title":"Combinatorica"},{"key":"2024041716571616600_ref6","first-page":"344","article-title":"On the density of non-simple 3-planar graphs","volume-title":"Graph Drawing and Network Visualization - 24th International Symposium, GD 2016","author":"Bekos","year":"2016"},{"key":"2024041716571616600_ref7","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","article-title":"Improving the crossing lemma by finding more crossings in sparse graphs","volume":"36","author":"Pach","year":"2006","journal-title":"Discret. Comput. Geom."},{"key":"2024041716571616600_ref8","doi-asserted-by":"crossref","first-page":"101574","DOI":"10.1016\/j.comgeo.2019.101574","article-title":"On topological graphs with at most four crossings per edge","volume":"85","author":"Ackerman","year":"2019","journal-title":"Comput. Geom."},{"key":"2024041716571616600_ref9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05412-3","volume-title":"Proofs from THE BOOK","author":"Aigner","year":"2004"},{"key":"2024041716571616600_ref10","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00454-009-9143-9","article-title":"On the maximum number of edges in topological graphs with no four pairwise crossing edges","volume":"41","author":"Ackerman","year":"2009","journal-title":"Discret. Comput. Geom."},{"key":"2024041716571616600_ref11","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1016\/j.jcta.2006.08.002","article-title":"On the maximum number of edges in quasi-planar graphs","volume":"114","author":"Ackerman","year":"2007","journal-title":"J. Comb. Theory, Ser. A"},{"key":"2024041716571616600_ref12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01196127","article-title":"Quasi-planar graphs have a linear number of edges","volume":"17","author":"Agarwal","year":"1997","journal-title":"Combinatorica"},{"key":"2024041716571616600_ref13","first-page":"221","article-title":"Relaxing planarity for topological graphs","volume-title":"Discrete and Computational Geometry, Japanese Conference, JCDCG 2002, Tokyo, Japan, December 6-9, 2002, Revised Papers","author":"Pach","year":"2002"},{"key":"2024041716571616600_ref14","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0095-8956(92)90003-G","article-title":"A Tur\u00e1n-type theorem on chords of a convex polygon","volume":"56","author":"Capoyleas","year":"1992","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2024041716571616600_ref15","first-page":"346","article-title":"Coloring k$_k$k-free intersection graphs of geometric objects in the plane","volume-title":"Proceedings of the 24th ACM Symposium on Computational Geometry","author":"Fox","year":"2008"},{"key":"2024041716571616600_ref16","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/110858586","article-title":"The number of edges in k-quasi-planar graphs","volume":"27","author":"Fox","year":"2013","journal-title":"SIAM J. Discrete Math."},{"key":"2024041716571616600_ref17","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02086610","article-title":"Applications of the crossing number","volume":"16","author":"Pach","year":"1996","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref18","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.comgeo.2015.06.001","article-title":"New bounds on the maximum number of edges in k-quasi-planar graphs","volume":"50","author":"Suk","year":"2015","journal-title":"Comput. Geom."},{"key":"2024041716571616600_ref19","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/PL00009364","article-title":"On geometric graphs with no k pairwise parallel edges","volume":"19","author":"Valtr","year":"1998","journal-title":"Discrete Comput. Geom."},{"key":"2024041716571616600_ref20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jctb.2019.08.006","article-title":"Simple k-planar graphs are simple (k+1)-quasiplanar","volume":"142","author":"Angelini","year":"2020","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2024041716571616600_ref21","first-page":"16","article-title":"On optimal 2- and 3-planar graphs","volume-title":"33rd International Symposium on Computational Geometry, SoCG 2017","author":"Bekos","year":"2017"},{"key":"2024041716571616600_ref22","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1002\/jgt.21630","article-title":"Minimal obstructions for 1-immersions and hardness of 1-planarity testing","volume":"72","author":"Korzhik","year":"2013","journal-title":"J. Graph Theory"},{"key":"2024041716571616600_ref23","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/s00453-016-0200-5","article-title":"On the recognition of fan-planar and maximal outer-fan-planar graphs","volume":"79","author":"Bekos","year":"2017","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref24","doi-asserted-by":"crossref","first-page":"81","DOI":"10.7155\/jgaa.00398","article-title":"Algorithms and characterizations for 2-layer fan-planarity: from caterpillar to stegosaurus","volume":"21","author":"Binucci","year":"2017","journal-title":"J. Graph Algorithms Appl."},{"key":"2024041716571616600_ref25","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.tcs.2015.04.020","article-title":"Fan-planarity: properties and complexity","volume":"589","author":"Binucci","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"2024041716571616600_ref26","article-title":"The density of fan-planar graphs","volume":"1403.6184","author":"Kaufmann","year":"2014","journal-title":"CoRR"},{"key":"2024041716571616600_ref27","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.tcs.2020.04.018","article-title":"On RAC drawings of graphs with one bend per edge","volume":"828-829","author":"Angelini","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"2024041716571616600_ref28","doi-asserted-by":"crossref","first-page":"5156","DOI":"10.1016\/j.tcs.2011.05.025","article-title":"Drawing graphs with right angle crossings","volume":"412","author":"Didimo","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"2024041716571616600_ref29","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-1-4614-0110-0_10","article-title":"The crossing-angle resolution in graph drawing","volume-title":"Thirty Essays on Geometric Graph Theory","author":"Didimo","year":"2013"},{"key":"2024041716571616600_ref30","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1016\/j.dam.2012.11.019","article-title":"Right angle crossing graphs and 1-planarity","volume":"161","author":"Eades","year":"2013","journal-title":"Discret. Appl. Math."},{"key":"2024041716571616600_ref31","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1007\/s00453-015-0002-1","article-title":"Outer 1-planar graphs","volume":"74","author":"Auer","year":"2016","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref32","first-page":"546","article-title":"Beyond outerplanarity","volume-title":"Graph Drawing and Network Visualization - 25th International Symposium, GD 2017","author":"Chaplick","year":"2017"},{"key":"2024041716571616600_ref33","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.tcs.2016.05.017","article-title":"Circular right-angle crossing drawings in linear time","volume":"639","author":"Dehkordi","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"2024041716571616600_ref34","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.ipl.2013.01.013","article-title":"Density of straight-line 1-planar graph drawings","volume":"113","author":"Didimo","year":"2013","journal-title":"Inf. Process. Lett."},{"key":"2024041716571616600_ref35","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1007\/s00453-014-9890-8","article-title":"A linear-time algorithm for testing outer-1-planarity","volume":"72","author":"Hong","year":"2015","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref36","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.dam.2018.08.018","article-title":"A linear-time algorithm for testing full outer-2-planarity","volume":"255","author":"Hong","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"2024041716571616600_ref37","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1007\/s00453-012-9706-7","article-title":"2-layer right angle crossing drawings","volume":"68","author":"Di Giacomo","year":"2014","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref38","doi-asserted-by":"crossref","first-page":"P4.24","DOI":"10.37236\/7581","article-title":"Analogies between the crossing number and the tangle crossing number","volume":"25","author":"Anderson","year":"2018","journal-title":"Electron. J. Comb."},{"key":"2024041716571616600_ref39","first-page":"593","article-title":"Comparing trees via crossing minimization","volume":"76","author":"Fernau","year":"2010","journal-title":"JCSS"},{"key":"2024041716571616600_ref40","doi-asserted-by":"crossref","first-page":"i248","DOI":"10.1093\/bioinformatics\/btr210","article-title":"Tanglegrams for rooted phylogenetic trees and networks","volume":"27","author":"Scornavacca","year":"2011","journal-title":"Bioinformatics"},{"key":"2024041716571616600_ref41","first-page":"489","article-title":"A tale of two communities: Assessing homophily in node-link diagrams","volume-title":"Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015","author":"Meulemans","year":"2015"},{"key":"2024041716571616600_ref42","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1006\/jcss.1996.0026","article-title":"Exact classification with two-layer neural nets","volume":"52","author":"Gibson","year":"1996","journal-title":"J. Comput. Syst. Sci."},{"key":"2024041716571616600_ref43","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0166-218X(97)00053-X","article-title":"Exact classification with two-layer neural nets in N dimensions","volume":"81","author":"Sweatman","year":"1998","journal-title":"Discret. Appl. Math."},{"key":"2024041716571616600_ref44","doi-asserted-by":"crossref","DOI":"10.1142\/4902","volume-title":"Graph Drawing and Applications for Software and Knowledge Engineers","author":"Sugiyama","year":"2002"},{"key":"2024041716571616600_ref45","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","article-title":"Methods for visual understanding of hierarchical system structures","volume":"11","author":"Sugiyama","year":"1981","journal-title":"IEEE Trans. Syst. Man. Cybern., SMC-11"},{"key":"2024041716571616600_ref46","article-title":"Old and new challenges in coloring graphs with geometric representations","volume-title":"Graph Drawing and Network Visualization - 27th International Symposium, GD 2019","author":"Walczak","year":"2019"},{"key":"2024041716571616600_ref47","doi-asserted-by":"crossref","first-page":"2779","DOI":"10.1137\/1.9781611976465.165","article-title":"2-level quasi-planarity or how caterpillars climb (SPQR-) trees","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021","author":"Angelini","year":"2021"},{"key":"2024041716571616600_ref48","doi-asserted-by":"crossref","first-page":"731","DOI":"10.7155\/jgaa.00437","article-title":"Intersection-link representations of graphs","volume":"21","author":"Angelini","year":"2017","journal-title":"J. Graph Algorithms Appl."},{"key":"2024041716571616600_ref49","first-page":"14","article-title":"Layered fan-planar graph drawings","volume-title":"45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020","author":"Biedl","year":"2020"},{"key":"2024041716571616600_ref50","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/s00453-007-9151-1","article-title":"On the parameterized complexity of layered graph drawing","volume":"52","author":"Dujmovi\u0107","year":"2008","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref51","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0095-8956(91)90068-U","article-title":"Quickly excluding a forest","volume":"52","author":"Bienstock","year":"1991","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2024041716571616600_ref52","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","article-title":"A partial k-arboretum of graphs with bounded treewidth","volume":"209","author":"Bodlaender","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"2024041716571616600_ref53","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1017\/S0963548300001450","article-title":"Graph minors 1: a short proof of the path-width theorem","volume":"4","author":"Diestel","year":"1995","journal-title":"Comb. Probab. Comput."},{"key":"2024041716571616600_ref54","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","article-title":"Graph minors. I. Excluding a forest","volume":"35","author":"Robertson","year":"1983","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2024041716571616600_ref55","doi-asserted-by":"crossref","first-page":"1561","DOI":"10.1007\/s00453-018-0487-5","article-title":"Track layouts, layered path decompositions, and leveled planarity","volume":"81","author":"Bannister","year":"2019","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref56","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s00453-019-00653-x","article-title":"Crossing number for graphs with bounded pathwidth","volume":"82","author":"Biedl","year":"2020","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref57","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00453-005-1181-y","article-title":"A fixed-parameter approach to 2-layer planarization","volume":"45","author":"Dujmovic","year":"2006","journal-title":"Algorithmica"},{"key":"2024041716571616600_ref58","doi-asserted-by":"crossref","first-page":"363","DOI":"10.7155\/jgaa.00075","article-title":"Straight-line drawings on restricted integer grids in two and three dimensions","volume":"7","author":"Felsner","year":"2003","journal-title":"J. Graph Algorithms Appl."},{"key":"2024041716571616600_ref59","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/S0095-8956(03)00037-6","article-title":"Crossing-number critical graphs have bounded path-width","volume":"88","author":"Hlinen\u00fd","year":"2003","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2024041716571616600_ref60","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1142\/S0218195904001433","article-title":"Pathwidth and layered drawings of trees","volume":"14","author":"Suderman","year":"2004","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"2024041716571616600_ref61","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista","year":"1999"},{"key":"2024041716571616600_ref62","volume-title":"Graph Theory, 4th Edition, Graduate texts in mathematics, 173","author":"Diestel","year":"2012"},{"key":"2024041716571616600_ref63","first-page":"9","article-title":"Crossing-free subgraphs","volume-title":"Theory and Practice of Combinatorics, North-Holland Mathematics Studies, 60","author":"Ajtai","year":"1982"},{"key":"2024041716571616600_ref64","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1080\/00029890.1973.11993230","article-title":"Crossing number problems","volume":"80","author":"Erd\u0151s","year":"1973","journal-title":"Am. Math. Mon."},{"key":"2024041716571616600_ref65","volume-title":"Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks","author":"Leighton","year":"1983"},{"key":"2024041716571616600_ref66","first-page":"28","article-title":"Beyond-planarity: Tur\u00e1n-type results for non-planar bipartite graphs","volume-title":"29th International Symposium on Algorithms and Computation, ISAAC 2018","author":"Angelini","year":"2018"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/3\/1005\/57231618\/bxad038.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/67\/3\/1005\/57231618\/bxad038.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T19:59:34Z","timestamp":1713383974000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/67\/3\/1005\/7135863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,21]]},"references-count":66,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,4,21]]},"published-print":{"date-parts":[[2024,4,14]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxad038","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,3]]},"published":{"date-parts":[[2023,4,21]]}}}