Improvements on the density of maximal 1-planar graphs

DOI10.1002/JGT.22187zbMATH Open1391.05151arXiv1509.05548OpenAlexW2963028755MaRDI QIDQ4575520FDOQ4575520

Authors: János Barát, Géza Tóth 

Publication date: 13 July 2018

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. Brandenburg et al. showed that there are maximal 1-planar graphs with only $frac4517n+O(1)approx2.647n$ edges and maximal 1-plane graphs with only $frac73n+O(1)approx2.33n$ edges. On the other hand, they showed that a maximal 1-planar graph has at least $frac2813n-O(1)approx2.15n-O(1)$ edges, and a maximal 1-plane graph has at least $2.1n-O(1)$ edges. We improve both lower bounds to $frac20n9approx2.22n$.

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

Recommendations

• On the density of maximal 1-planar graphs
• The maximal 1-planarity and crossing numbers of graphs
• Density of straight-line 1-planar graph drawings
• On properties of maximal 1-planar graphs
• A note on 1-planar graphs

zbMATH Keywords

edge density1-planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42)

Cited In (17)

• The density of fan-planar graphs
• A note on 1-planar graphs
• 1-Planar Graphs
• Counting cliques in 1-planar graphs
• Edge-minimum saturated \(k\)-planar drawings
• Bounded stub resolution for some maximal 1-planar graphs
• Cops and robbers on 1-planar graphs
• Edge-minimum saturated \(k\)-planar drawings
• Crossing lemma for the odd-crossing number
• On properties of maximal 1-planar graphs
• On the density of maximal 1-planar graphs
• Density of straight-line 1-planar graph drawings
• Saturated 2-plane drawings with few edges
• On an extremal problem in the class of bipartite 1-planar graphs
• Maximal 1-plane graphs with dominating vertices
• The maximal 1-planarity and crossing numbers of graphs
• Quantitative restrictions on crossing patterns

This page was built for publication: Improvements on the density of maximal 1-planar graphs

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