8
$\begingroup$

Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere.

Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with the same vertex cross each other.

Non-isomorphic means that there is no isomorphism of the drawings as embedded graphs.

My questions are:

How many good drawings are there of $K_{3,3}$?

Is there any website or program that lists all good drawings of graphs with at most $n$ vertices?

The three requirements on a good graph are illustrated below: enter image description here

For small graphs, there are the following results.

For complete graphs with at most 5 vertices, the list of good drawings is basically clear. They are also summarized in Marcus Sahefer's book on Crossing Numbers of Graphs (CRC Press, 2018):

  • There are two non-isomorphic good drawings of $K_4$ on the sphere.
  • There are five non-isomorphic drawings of $K_5$ on the sphere.

Meanwhile $K_{2,3}$ has $4$ good drawings, as described in Michal Stas, "Join Products [K. sub. 2, 3]+[C. sub. n]" (Mathematics v8.6, 2020). They are illustrated in the graphic below:

enter image description here

We can get lists of non-isomorphic graphs from websites (e.g. http://users.cecs.anu.edu.au/~bdm/data/graphs.html) or from software such as maple or geng. How can we get a similar list of non-isomorphic good drawings?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ you need to describe in more detail what drawings you accept as good. $\endgroup$
    – Dima Pasechnik
    Commented Apr 21, 2021 at 14:11
  • $\begingroup$ @DimaPasechnik Sorry, wait a minute. I'll add it right away. $\endgroup$
    – Licheng Zhang
    Commented Apr 21, 2021 at 14:13

1 Answer 1

Reset to default
5
$\begingroup$

The list of nonisomorphic good drawings of $K_{m,n}$ with $2\le m,n \le 3$ appears in the following paper:

Heiko Harborth, Parity of numbers of crossings for complete n-partite graphs, Mathematica Slovaca, Vol. 26 (1976), No. 2, 77-95. Persistent URL: http://dml.cz/dmlcz/136111

The number of nonisomorphic good drawings of $K_{3,3}$ obtained is $102$.

For $K_{2,3}$, there are six nonisomorphic drawings. The two that are missing in Figure 1 referenced in the question may not be realizable with straight-line edges.

The list of nonisomorphic good drawings of graphs with up to five vertices appears in the paper

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you！Great reply, I looked for the last paper( Numbers of nonisomorphic drawings for small graphs )carefully, but unlucky I couldn't find it. Do you know where to download it, thanks again！ $\endgroup$
    – Licheng Zhang
    Commented Apr 22, 2021 at 0:40
  • $\begingroup$ It is cited in a large number of published paper(e.g. Leck V. The Numbers of Nonisomorphic Drawings of the Connected Graphs with 6 vertices[M]. Univ., Fachbereich Mathematik, 1998.）, but it is difficult to find electronic full text and very strange. Only see links to comments: zbmath.org/?q=an%3A04139770 $\endgroup$
    – Licheng Zhang
    Commented Apr 22, 2021 at 14:08
  • $\begingroup$ The journal can be found in some libraries, unfortunately it does not have online version (at least not yet). $\endgroup$
    – Jan Kyncl
    Commented Apr 22, 2021 at 21:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .