Plane graphs

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+2e+n bytes.

Plane 5-regular simple connected graphs

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)

Nonhamiltonian planar cubic graphs

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.

No faces of size 3

38 vertices: 6
40 vertices: 37
42 vertices: 277
44 vertices: 1732
46 vertices: 11204
48 vertices: 70614

Cyclically 4-connected

42 vertices: 3
44 vertices: 3
46 vertices: 19
48 vertices: 30
50 vertices: 126

No faces of size 3 or 4, cyclic connectivity exactly 4

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)

Cyclically 5-connected

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

Hypohamiltonian planar graphs

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.

Cubic graphs of girth 4

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 below. It is not known if these graphs are the smallest.

70 vertices: 7

cubic planar hypohamiltonian graph with 70 vertices

Cubic planar graphs of girth 5

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.

76 vertices: 3

cubic planar hypohamiltonian graph with 76 vertices cubic planar hypohamiltonian graph with 76 vertices cubic planar hypohamiltonian graph with 76 vertices

Cubic planar graphs with an a-edge

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, brendan.mckay@anu.edu.au

Up to the combinatorial data page