On the Density of Maximal 1-Planar Graphs

Brandenburg, Franz J. and Eppstein, David and Gleißner, Andreas and Goodrich, Michael T. and Hanauer, Kathrin and Reislhuber, Josef (2013) On the Density of Maximal 1-Planar Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012 , pp. 327-338(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

Full text not available from this repository.


A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. It is maximal 1-planar if the addition of any edge violates 1-planarity. Maximal 1-planar graphs have at most 4n−8 edges. We show that there are sparse maximal 1-planar graphs with only $\frac{45}{17} n + \mathcal{O}(1)$ edges. With a fixed rotation system there are maximal 1-planar graphs with only $\frac{7}{3} n + \mathcal{O}(1)$ edges. This is sparser than maximal planar graphs. There cannot be maximal 1-planar graphs with less than $\frac{21}{10} n - \mathcal{O}(1)$ edges and less than $\frac{28}{13} n - \mathcal{O}(1)$ edges with a fixed rotation system. Furthermore, we prove that a maximal 1-planar rotation system of a graph uniquely determines its 1-planar embedding.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-36763-2_29
Classifications: G Algorithms and Complexity > G.490 Embeddings
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1321

Actions (login required)

View Item View Item