We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Improvements on the density of maximal 1‐planar graphs.
- Authors
Barát, János; Tóth, Géza
- Abstract
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. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al. showed that there are maximal 1‐planar graphs with only 45 17 n + O ( 1 ) ≈ 2.647 n edges and maximal 1‐plane graphs with only 7 3 n + O ( 1 ) ≈ 2.33 n edges. On the other hand, they showed that a maximal 1‐planar graph has at least 28 13 n − O ( 1 ) ≈ 2.15 n − O ( 1 ) edges, and a maximal 1‐plane graph has at least 2.1 n − O ( 1 ) edges. We improve both lower bounds to 20 n 9 ≈ 2.22 n.
- Subjects
PLANAR graphs; PATHS &; cycles in graph theory; MATHEMATICAL bounds; MAXIMA &; minima; GRAPH theory
- Publication
Journal of Graph Theory, 2018, Vol 88, Issue 1, p101
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22187