On the Density of Maximal 1-Planar Graphs

Brandenburg, 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 1-Planar Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 327-338 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_29).

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
ID Code:1321

Repository Staff Only: item control page


Auer, C., Brandenburg, F.J., Gleißner, A., Reislhuber, J.: On 1-Planar Graphs with Rotation Systems. Tech. Rep. MIP-1207, Fakultät für Informatik und Mathematik, Universität Passau (2012)

Bodendiek, R., Schumacher, H., Wagner, K.: Bemerkungen zu einem Sechsfarbenproblem von G. Ringel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 53, 41–52 (1983)

Bodendiek, R., Schumacher, H., Wagner, K.: Über 1-optimale Graphen. Mathematische Nachrichten 117, 323–339 (1984)

Borodin, O.V.: A New Proof of the 6 Color Theorem. Journal of Graph Theory 19(4), 507–521 (1995)

De Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)

Hong, S.-H., Eades, P., Liotta, G., Poon, S.-H.: Fáry’s Theorem for 1-Planar Graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS, vol. 7434, pp. 335–346. Springer, Heidelberg (2012)

Eades, P., Liotta, G.: Right Angle Crossing Graphs and 1-Planarity. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 148–153. Springer, Heidelberg (2012)

Fabrici, I., Madaras, T.: The Structure of 1-Planar Graphs. Discrete Mathematics 307(7-8), 854–865 (2007)

Goodrich, M.T., Wagner, C.G.: A Framework for Drawing Planar Graphs with Curves and Polylines. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 153–166. Springer, Heidelberg (1999)

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)

Korzhik, V.P., Mohar, B.: Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 302–312. Springer, Heidelberg (2009)

Korzhik, V.P.: Minimal Non-1-Planar Graphs. Discrete Math. 308(7), 1319–1327 (2008)

Mehlhorn, K., Mutzel, P.: On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm. Algorithmica 16, 233–242 (1995)

Nishizeki, T., Rahman, S.: Planar Graph Drawing. World Scientific (2004)

Pach, J., Tóth, G.: Graphs Drawn with Few Crossings per Edge. Combinatorica 17, 427–439 (1997)

Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 29, 107–117 (1965)

Schnyder, W.: Embedding Planar Graphs on the Grid. In: Proc. SODA, pp. 138–148 (1990)

Schumacher, H.: Zur Struktur 1-planarer Graphen. Mathematische Nachrichten 125, 291–300 (1986)

Suzuki, Y.: Optimal 1-planar Graphs which Triangulate other Surfaces. Discrete Mathematics 310(1), 6–11 (2010)

Suzuki, Y.: Re-embeddings of Maximum 1-Planar Graphs. SIAM J. Discrete Math. 24(4), 1527–1540 (2010)