On this page we give some classes of graphs imbedded in the plane.
We focus on graph classes that are not so easy to generate using
`plantri`.

The graph format is `planar code`. A complete definition can
be found in the
plantri manual (Appendix A).
For the graphs on this page, the following should be adequate.
Each graph is given as a sequence of bytes, starting with a byte
containing the number of vertices. Then for each vertex, a list of
the neighbours is given, one neighbour per byte in clockwise order,
plus a zero byte to end the list. Vertices are numbered starting
with 1. A graph with *n* vertices and *e* edges thus
occupies exactly 1+2*e*+*n* bytes.

12 vertices: 1

14 vertices: 0

16 vertices: 1

18 vertices: 1

20 vertices: 6

22 vertices: 14

24 vertices: 98

26 vertices: 529

28 vertices: 4035

30 vertices: 31009

32 vertices: 252386

34 vertices: 2073769 (bzip2)

36 vertices: 17277113 (bzip2; 395MB)

In this section we give some families of nonhamiltonian planar cubic graphs defined according to some properties. All the graphs are simple, 3-connected, cubic, planar and nonhamiltonian; we list any further defining properties in the heading. For each graph family, there are no smaller graphs than we give.

42 vertices: 277

44 vertices: 1732

46 vertices: 11204

48 vertices: 70614

42 vertices: 3

44 vertices: 3

46 vertices: 19

48 vertices: 30

50 vertices: 126

44 vertices: 1

46 vertices: 3

48 vertices: 1

50 vertices: 3

52 vertices: 6

54 vertices: 12

56 vertices: 49

58 vertices: 126

60 vertices: 214

62 vertices: 659

64 vertices: 1467

66 vertices: 3247

68 vertices: 9187

70 vertices: 22069

72 vertices: 50514

74 vertices: 137787

76 vertices: 339804 (bzip2)

44 vertices: 1

46 vertices: 1

48 vertices: 0

50 vertices: 3

52 vertices: 6

54 vertices: 2

56 vertices: 22

58 vertices: 37

60 vertices: 31

62 vertices: 194

64 vertices: 298

66 vertices: 306

68 vertices: 1538

70 vertices: 2566

72 vertices: 3091

74 vertices: 13487

A graph is *hypohamiltonian* if it is not hamiltonian but
becomes hamiltonian if any vertex is removed. Here are some examples
of hypohamiltonian graphs which are planar.

The smallest known cubic planar hypohamiltonian graphs have 70 vertices. The first was found by Araya and Wiener, while six more were found by Mohammadreza Jooyandeh and myself. These graphs have girth 4, which is the smallest possible girth for a cubic hypohamiltonian graph. One of the new graphs, with a structure somewhat different from the rest, appears on the right. It is not known if these graphs are the smallest.

70 vertices: 7

We have proved that the smallest cubic planar hypohamiltonian graphs of girth 5 (the largest possible girth for a cubic planar graph) have 76 vertices. There are three of them.

graphs will appear here

An *a*-edge in a graph is an edge which is present on every
hamiltonian cycle. We exclude the case of non-hamiltonian graphs.
For a 3-connected cubic graph, it is easy to see what happens when
a triangle is reduced to a point, so we exclude that case too.

In the following files are all cubic planar 3-connected hamiltonian
graphs with no 3-cycle (which is equivalent to no 3-face) that have
at least one *a*-edge, up to 38 vertices.

16 vertices: 1

18 vertices: 1

20 vertices: 4

22 vertices: 13

24 vertices: 58

26 vertices: 279

28 vertices: 1406

30 vertices: 7525

32 vertices: 40659

34 vertices: 225731 (bzip2)

36 vertices: 1266106 (bzip2)

38 vertices: 7204890 (bzip2; 110MB)

Page Master: Brendan McKay, bdm@cs.anu.edu.au and http://cs.anu.edu.au/~bdm.