K-planar graphs

Introduction:

There is a natural generalisation of planar graphs namely k-planar graphs. A graph is k-planar if it has a drawing in the plane in which each edge is involved in at most k crossings. The study of 1-planar graphs goes back to more than fifty years ago. More precisely 1-planar graphs have been introduced by Ringel. They have several applications in the areas of graph theory, graph algorithms, graph drawing, and computational geometry, see recent bibliography on 1-planar graphs and the 140 references therein [1]. For instance the complete graph K_6 is 1-planar or the following graph.

A 1-planar graph G with n vertices has at most 4n − 8 edges. More precisely we have the following theorem.

Theorem: Let G be a 1-planar graph with n vertices. Then the maximum number of edges of G is given by 

References:

1. Kobourov, Stephen G., Giuseppe Liotta, and Fabrizio Montecchiani. "An annotated bibliography on 1-planarity." Computer Science Review 25 (2017): 49-67.

2. Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM J. Discrete Math., 31(2):805–824, 2017. 

3. J. Pach and G. T´oth. Graphs drawn with few crossings per edge. Combinatorica, 17(3):427–439, 1997.

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

5. Y. Suzuki, K_7-minors in optimal 1-planar graphs, Discrete Math. 340 (2017), 1227–1234.

6. A. Grigoriev, H. L. Bodlaender, Algorithms for graphs embeddable with few crossings per edge, Algorithmica 49 (2007), 1–11.

7. V. P. Korzhik, B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory 72 (2013), 30–71

8. L. Zhang and Y. HuangThe reducibility of optimal 1-planar graphs with respect to the lexicographic product, arXiv.

9. Y. Suzuki, Re-embeddings of maximum 1-planar graphs, SIAM J. Discrete Math. 24 (2010), 1527–1540.

10. Ringel G, Ein sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg., 29 (1965), pp. 107-117

11. I. Fabrici, J. Harant, T. Madaras, S. Mohr, R. Sot´ak, and C. T. Zamfirescu, Long cycles and spanning subgraphs of locally maximal 1-planar graphs, J. Graph Theory 95 (2020), 125–137.

12. K. Noguchi and Y. Suzuki, Relationship among triangulations, quadrangulations and optimal 1-planar graphs, Graphs and Combin. 31 (2015), 1965–1972.