Two-Planar Graphs Are Quasiplanar

DOI10.4230/LIPICS.MFCS.2017.47MaRDI QIDQ5111262zbMATH OpenOpenAlexFDO

Authors

Publication date 26 May 2020

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

zbMATH Keywords

graph drawingnear-planar graphsimple topological plane graph

Mathematics Subject Classification ID

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

Abstract: It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross.

Recommendations

• Quasi-planar graphs have a linear number of edges
• On the maximum number of edges in quasi-planar graphs
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• On plane drawings of 2-planar graphs
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs

Cites work

• scientific article; zbMATH DE number 5037083 (Why is no real title available?)
• Adjacent crossings do matter
• An annotated bibliography on 1-planarity
• Applications of a new separator theorem for string graphs
• Applications of the crossing number
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• Crossing-Free Subgraphs
• Graph minor theory
• Graphs drawn with few crossings per edge
• Improving the crossing lemma by finding more crossings in sparse graphs
• On Optimal 2- and 3-Planar Graphs
• On graph thickness, geometric thickness, and separator theorems
• On the maximum number of edges in quasi-planar graphs
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• On topological graphs with at most four crossings per edge
• Quasi-planar graphs have a linear number of edges
• The number of edges in k-quasi-planar graphs
• Two-Planar Graphs Are Quasiplanar

Cited in

(11)

• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• Fan-planar graphs
• Quasi-planar Graphs
• Two-Planar Graphs Are Quasiplanar
• h-quasi planar drawings of bounded treewidth graphs in linear area
• Combinatorial properties and recognition of unit square visibility graphs
• Gap-Planar Graphs
• Gap-planar graphs
• \(k\)-planar graphs
• Beyond-planarity: Turán-type results for non-planar bipartite graphs
• On plane drawings of 2-planar graphs

This page was built for publication: Two-Planar Graphs Are Quasiplanar

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