pith. sign in

arxiv: 1509.05548 · v1 · pith:BL2KQQOVnew · submitted 2015-09-18 · 🧮 math.CO

Improvements on the density of maximal 1-planar graphs

classification 🧮 math.CO
keywords maximalplanarapproxedgesfracgraphplanegraphs
0
0 comments X
read the original 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 $\frac{45}{17}n + O(1)\approx 2.647n$ edges and maximal 1-plane graphs with only $\frac{7}{3}n+O(1)\approx 2.33n$ edges. On the other hand, they showed that a maximal 1-planar graph has at least $\frac{28}{13}n-O(1)\approx 2.15n-O(1)$ edges, and a maximal 1-plane graph has at least $2.1n-O(1)$ edges. We improve both lower bounds to $\frac{20n}{9}\approx 2.22n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.