On the Density of Maximal 1Planar GraphsBrandenburg, Franz Josef and Eppstein, David and Gleißner, Andreas and Goodrich, Michael T. and Hanauer, Kathrin and Reislhuber, Josef (2013) On the Density of Maximal 1Planar Graphs. In: 20th International Symposium, GD 2012, September 1921, 2012 , pp. 327338(Official URL: http://link.springer.com/chapter/10.1007/9783642...). Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/9783642...
AbstractA graph is 1planar if it can be drawn in the plane such that each edge is crossed at most once. It is maximal 1planar if the addition of any edge violates 1planarity. Maximal 1planar graphs have at most 4n−8 edges. We show that there are sparse maximal 1planar graphs with only $\frac{45}{17} n + \mathcal{O}(1)$ edges. With a fixed rotation system there are maximal 1planar graphs with only $\frac{7}{3} n + \mathcal{O}(1)$ edges. This is sparser than maximal planar graphs. There cannot be maximal 1planar 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 1planar rotation system of a graph uniquely determines its 1planar embedding.
Actions (login required)
