4
$\begingroup$

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.
$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.