Improvements on the density of maximal 1-planar graphs

DOI10.1002/JGT.22187MaRDI QIDQ4575520zbMATHOpenAlexFDO

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)

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

zbMATH Keywords

edge density1-planar graph

Mathematics Subject Classification ID

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

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$.

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

Cited in

(19)

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

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)