Planar Graphs

Introduction

Planar triangulations can be constructed in large numbers by the program plantri.c written by Gunnar Brinkmann and Brendan McKay. It is available from Brendan's home page. The latest version of this excellent program can also produce 3-connected planar graphs (equivalent to polyhedra with n nodes).

Planar Graphs (3-connected)
Planar Triangulations
Triangles in planar triangulations

Planar Graphs (3-connected)

The numbers of 3-connected planar graphs are given in the following table. Highlighted numbers are links to the files containing the planar graphs (just as abstract graphs) in graph6 format. If you actually want the embeddings then you will have to run plantri, or embed them yourself.

# edges	4 vx	5 vx	6 vx	7 vx	8 vx	9 vx	10 vx	11 vx	12 vx	13 vx
6	1
7
8		1
9		1	1
10			2
11			2	2
12			2	8	2
13				11	11
14				8	42	8
15				5	74	74	5
16					76	296	76
17					38	633	633	38
18					14	768	2635	768	14
19						558	6134	6134	558
20						219	8822	25626	8822	219
21						50	7916	64439	64439	7916
22							4442	104213	268394	104213
23							1404	112082	709302	709302
24							233	79773	1263032	2937495
25								36528	1556952	8085725
26								9714	1338853	15535572
27								1249	789749	21395274
28									306470	21317178
29									70454	15287112
30									7595	7706577
31										2599554
32										527235
33										49566

Number of planar triangulations

The numbers of triangulations are given in the following table. Highlighted numbers are links to the files containing the planar triangulations (just as graphs) in graph6 format. If you actually want the embeddings then you will have to run plantri, or embed them yourself.

Vertices	Triangulations	.. with mindeg >= 4	.. with mindeg >= 5
4	1	0	0
5	1	0	0
6	2	1	0
7	5	1	0
8	14	2	0
9	50	5	0
10	233	12	0
11	1249	34	0
12	7595	130	1
13	49566	525	0
14	339722	2472	1
15	2406841	12400	1
16	17490241	65619	3
17	129664753	357504	4
18	977526957	?	12
19	7475907149	?	23
20	57896349553	?	73
21	453382272049	?	192
22	about 3.58585e12	?	651
23	about 2.86157e13	?	?
24	about 2.30215e14	?	?
25	about 1.86579e15	?	?

Triangles in triangulations

A triangulation on v vertices has 2v-4 faces, which are necessarily triangles. However it can also have extra triangles. What are the possible triangle numbers in a planar triangulation? The following table expresses them in terms of the "excess" e of the number of triangles over the minimum number 2v-4. Each number represents the number of triangulations with the stated excess.

Vertices	e=0	e=1	e=2	e=3	e=4	e=5	e=6	e=7	e=8	e=9	e=10	e=11
4	1	-	-	-	-	-	-	-	-	-	-	-
5	-	1	-	-	-	-	-	-	-	-	-	-
6	1	-	1	-	-	-	-	-	-	-	-	-
7	1	1	-	3	-	-	-	-	-	-	-	-
8	2	1	4	-	7	-	-	-	-	-	-	-
9	4	4	7	11	-	24	-	-	-	-	-	-
10	10	14	30	29	57	-	93	-	-	-	-	-
11	25	51	120	164	184	270	-	434	-	-	-	-
12	87	237	550	837	1126	1084	1564	-	2110	-	-	-
13	313	1135	2785	4598	6358	7422	6825	9128	-	11002	-	-
14	1357	5744	14879	26551	38303	46175	50177	42535	55288	-	58713	-
15	6244	30247	82488	156543	236965	299906	331985	335990	267548	337149	-	321776

4-connected triangulations

Clearly, if a triangulation has a non-facial triangle, then it has a cutset of size 3. Conversely, any cutset of size three must be a non-facial triangle in the graph. Therefore the set of 4-connected triangulations is the set of triangulations with precisely 2v-4 triangles (that is, those with excess e=0).

This sequence of numbers appears in Sloane's Encyclopedia of Integer Sequences as sequence A007021.

Vertices	4-conn planar triangulations.
6	1
7	1
8	2
9	4
10	10
11	25
12	87
13	313
14	1357
15	6244
16	30926
17	158428
18	836749
19	4504607
20	24649284