Graph Theory – How to Find All 2-Planar Drawings of K6 and K7

co.combinatoricsgraph theorygraph-drawingtopological-graph-theory

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.
enter image description here

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.

enter image description here

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.

Best Answer

The list of all good drawings of $K_6$ can be found in the doctoral thesis by Nabil H. Rafla: https://escholarship.mcgill.ca/concern/theses/x346d4920

On pages 164-165 the drawings are described by the list of all crossing pairs of edges, which may be helpful to identify 2-planar drawings.

Then there is also a highly compressed list of all good drawings of $K_7$ with a noncrossing Hamiltonian cycle.

Related Question