On the relationship between k-planar and k-quasi-planar graphs

DOI10.1007/978-3-319-68705-6_5zbMATH Open1483.05044arXiv1702.08716OpenAlexW2592788043MaRDI QIDQ1687902FDOQ1687902

Authors: Patrizio Angelini, Michael A. Bekos, Giordano Da Lozzo, Giuseppe Di Battista, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, Ignaz Rutter, Franz J. Brandenburg 

Publication date: 4 January 2018

Abstract: A graph is $k$-planar $(kgeq1)$ if it can be drawn in the plane such that no edge is crossed more than $k$ times. A graph is $k$-quasi planar $(kgeq2)$ if it can be drawn in the plane with no $k$ pairwise crossing edges. The families of $k$-planar and $k$-quasi planar graphs have been widely studied in the literature, and several bounds have been proven on their edge density. Nonetheless, only trivial results are known about the relationship between these two graph families. In this paper we prove that, for $kgeq3$, every $k$-planar graph is $(k+1)$-quasi planar.

Full work available at URL: https://arxiv.org/abs/1702.08716

Recommendations

• \(k\)-planar graphs
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• Quasi-planar graphs have a linear number of edges
• The number of edges in \(k\)-quasi-planar graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (14)

• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• Fan-planar graphs
• Quasi-planar Graphs
• Two-Planar Graphs Are Quasiplanar
• Upper bound on the sum of powers of the degrees of graphs with few crossings per edge
• Graph Drawing
• Gap-Planar Graphs
• Beyond outerplanarity
• On the density of non-simple 3-planar graphs
• Gap-planar graphs
• On quasi-planar graphs: clique-width and logical description
• Quantitative restrictions on crossing patterns
• \(k\)-planar graphs
• Beyond-planarity: Turán-type results for non-planar bipartite graphs

This page was built for publication: On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1687902)