A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per edge.
It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$.
- Angelini P., Bekos M. A., Kaufmann M., et al., Efficient generation of different topological representations of graphs beyond-planarity, In: C. D. T´oth and D. Archambault eds., Proc. of 27th International Symposium on Graph Drawing (GD 2019), 2019.
- Xin ZHANG. The Crossing Number of 2-planar Graphs and Its Application. Acta Mathematica Sinica, Chinese Series. 2021, 64(3): 463-470 https://doi.org/10.12386/A20210039
What interests me is finding all non-isomorphic 2-planar drawings of $K_5$, $K_6$, and $K_7$, respectively. We say that two drawings of a graph are isomorphic if there is a homeomorphism of the sphere that maps one drawing to the other.
Perhaps it is simple to obtain all 2-planar drawings for $K_5$, since all non-isomorphic drawings are as follows.
The first four drawings in the figure above are all 2-planar drawings of $K_5$.
What about $K_6$ or $K_7$?
We can see from the following paper that there are $121$ and $46999$ non-isomorphic drawings of $K_6$ and $K_7$ respectively.
- Ábrego B M, Aichholzer O, Fernández-Merchant S, et al. All good drawings of small complete graphs[C]//Proc. 31st European Workshop on Computational Geometry (EuroCG). 2015: 57-60.
Unfortunately, I only saw the numbers and not drawings in above paper, so I cannot choose 2-planar drawings of $K_6$ and $K_7$, respectively.
Perhaps the following paper is useful for thinking about 2-planar drawings of $K_6$, but I have never been able to find the online version. It would be greatly appreciated if someone provided it.
- H-D. O. F. Gronau and H. Harborth, Numbers of nonisomorphic drawings for small graphs, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989). Congr. Numer. 71 (1990), 105–114.
