Simple k-planar graphs are simple (k + 1)-quasiplanar

DOI10.1016/J.JCTB.2019.08.006zbMATH Open1436.05031arXiv1909.00223OpenAlexW3105254162MaRDI QIDQ1985441FDOQ1985441

Yanyan Li

Publication date: 7 April 2020

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A simple topological graph is $k$-quasiplanar ($kgeq2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is crossed more than $k$ times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $kgeq2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph.

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

Recommendations

• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• \(k\)-quasi-planar graphs
• Two-Planar Graphs Are Quasiplanar
• \(k\)-planar graphs
• On the maximum number of edges in quasi-planar graphs

zbMATH Keywords

graph drawingtopological graphs\(k\)-quasiplanar graphs\(k\)-planar graphsbeyond planarity

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Graphs drawn with few crossings per edge
• Improving the crossing lemma by finding more crossings in sparse graphs
• Right angle crossing graphs and 1-planarity
• 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 geometric graphs with no \(k\) pairwise parallel edges
• A Turán-type theorem on chords of a convex polygon
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• Applications of the crossing number
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Discrete and Computational Geometry
• New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
• On the Density of Non-simple 3-Planar Graphs
• On grids in topological graphs
• Topological graphs with no large grids
• On Optimal 2- and 3-Planar Graphs
• Fan-planarity: properties and complexity
• On the Number of Edges of Fan-Crossing Free Graphs
• On the relationship between \(k\)-planar and \(k\)-quasi-planar graphs
• Algorithms and Characterizations for 2-Layer Fan-planarity: From Caterpillar to Stegosaurus
• Gap-planar graphs
• Two-Planar Graphs Are Quasiplanar

Cited In (11)

• Beyond Planar Graphs: Introduction
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• Min-\(k\)-planar drawings of graphs
• Rotation systems and simple drawings in surfaces
• Quantitative Restrictions on Crossing Patterns
• Simplifying Non-Simple Fan-Planar Drawings
• 2-Layer k-Planar Graphs
• Min-\(k\)-planar drawings of graphs
• Nonplanar Graph Drawings with k Vertices per Face
• Finding geometric representations of apex graphs is \textsf{NP}-hard
• The family of fan-planar graphs

This page was built for publication: Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar

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