Two-Planar Graphs Are Quasiplanar

DOI10.4230/LIPICS.MFCS.2017.47zbMATH Open1441.68187arXiv1705.05569OpenAlexW2963074221MaRDI QIDQ5111262FDOQ5111262

Author name not available (Why is that?)

Publication date: 26 May 2020

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.

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

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

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)

Cites Work

• Graphs drawn with few crossings per edge
• Applications of a New Separator Theorem for String Graphs
• Improving the crossing lemma by finding more crossings in sparse graphs
• Graph minor theory
• Crossing-Free Subgraphs
• Quasi-planar graphs have a linear number of edges
• Recognizing and drawing IC-planar graphs
• The Number of Edges in $k$-Quasi-planar Graphs
• 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
• Applications of the crossing number
• On topological graphs with at most four crossings per edge
• Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• On graph thickness, geometric thickness, and separator theorems
• Title not available (Why is that?)
• An annotated bibliography on 1-planarity
• On Optimal 2- and 3-Planar Graphs
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Two-Planar Graphs Are Quasiplanar
• Adjacent Crossings Do Matter

Cited In (9)

• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• Quasi-planar Graphs
• Two-Planar Graphs Are Quasiplanar
• $$\textit{\textbf{k}}$$-Planar Graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Title not available (Why is that?)
• Gap-Planar Graphs
• Gap-planar graphs
• Fan-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)