On Optimal 2- and 3-Planar Graphs

DOI10.4230/LIPICS.SOCG.2017.16MaRDI QIDQ4580088zbMATH OpenOpenAlexFDO

Authors Michael A. Bekos, Michael Kaufmann, Chrysanthi N. Raftopoulou

Publication date 13 August 2018

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

zbMATH Keywords

characterizationoptimal \(k\)-planar graphstopological graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: A graph is $k$-planar if it can be drawn in the plane such that no edge is crossed more than $k$ times. While for $k=1$, optimal $1$-planar graphs, i.e., those with $n$ vertices and exactly $4n-8$ edges, have been completely characterized, this has not been the case for $kgeq2$. For $k=2,3$ and $4$, upper bounds on the edge density have been developed for the case of simple graphs by Pach and T'oth, Pach et al. and Ackerman, which have been used to improve the well-known "Crossing Lemma". Recently, we proved that these bounds also apply to non-simple $2$- and $3$-planar graphs without homotopic parallel edges and self-loops. In this paper, we completely characterize optimal $2$- and $3$-planar graphs, i.e., those that achieve the aforementioned upper bounds. We prove that they have a remarkably simple regular structure, although they might be non-simple. The new characterization allows us to develop notable insights concerning new inclusion relationships with other graph classes.

Recommendations

• On optimal beyond-planar graphs
• scientific article; zbMATH DE number 2094794
• On maximal and minimal triangular planar graphs: an optimization approach
• Edge partitions of optimal 2-plane and 3-plane graphs
• Edge partitions of optimal 2-plane and 3-plane graphs
• Recognizing and embedding simple optimal 2-planar graphs

Cited in

(43)

• Optimal 1-planar graphs which triangulate other surfaces
• Turning cliques into paths to achieve planarity
• Gap-planar graphs
• Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar
• On plane drawings of 2-planar graphs
• The density of fan-planar graphs
• Edge-minimum saturated \(k\)-planar drawings
• Simplifying non-simple fan-planar drawings
• Recognizing and embedding simple optimal 2-planar graphs
• Polyline drawings with topological constraints
• On 3D visibility representations of graphs with few crossings per edge
• On the density of non-simple 3-planar graphs
• The crossing number of 2-planar graphs and its application
• Optimal enclosing regions in planar graphs
• 3D Visibility Representations of 1-planar Graphs
• scientific article; zbMATH DE number 2094794 (Why is no real title available?)
• Quantitative restrictions on crossing patterns
• Quasi-planar Graphs
• \(k\)-planar graphs
• Fan-planar graphs
• 2-Layer k-Planar Graphs
• Polyline Drawings with Topological Constraints
• Two-Planar Graphs Are Quasiplanar
• Simplifying Non-Simple Fan-Planar Drawings
• Edge partitions of optimal 2-plane and 3-plane graphs
• On RAC drawings of graphs with one bend per edge
• Edge partitions of optimal 2-plane and 3-plane graphs
• On RAC drawings of graphs with one bend per edge
• Straight-line drawings of 1-planar graphs
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• The family of fan-planar graphs
• The thickness of fan-planar graphs is at most three
• On optimal beyond-planar graphs
• Nonplanar Graph Drawings with k Vertices per Face
• Min-\(k\)-planar drawings of graphs
• Edge-minimum saturated \(k\)-planar drawings
• Min-k-planar drawings of graphs
• The number of edges in maximal 2-planar graphs
• Graph product structure for \(h\)-framed graphs
• Improving the crossing lemma by characterizing dense 2-planar and 3-planar graphs
• On k-planar graphs without short cycles
• A parameterized algorithm for vertex and edge connectivity of embedded graphs
• Cops and robbers for graphs on surfaces with crossings

This page was built for publication: On Optimal 2- and 3-Planar Graphs

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