On the Density of Maximal 1-Planar Graphs
| Autor: | Andreas Gleißner, Josef Reislhuber, Franz J. Brandenburg, David Eppstein, Michael T. Goodrich, Kathrin Hanauer |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Graph Drawing ISBN: 9783642367625 Graph Drawing |
| DOI: | 10.1007/978-3-642-36763-2_29 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|