The General (Degree, Diameter) Problem for Graphs 

The (Degree, Diameter) Problem for Planar Graphs

We consider only the special case when the graph is planar. If the graph is also regular, Euler's formula implies that Δ can be at most 5. Each entry in the first table is either a single number or a closed interval [lower bound, upper bound] containing the order (number of vertices) of the largest planar Δ-regular graph with diameter D. In all cases, the lower bound arises from the construction of a graph. If an entry consists of a single number, the lower and upper bounds are known to be the same.  In order to be consistent with the second and third tables, these entries are also marked with an asterisk. The newest bounds are in bold.

LOWER AND UPPER BOUNDS FOR LARGEST PLANAR REGULAR (Δ, D)-GRAPHS (November 5, 1998)
Δ \ D 
1
2
3
4
5
6
7
8
1
2*
none exists 
none exists 
none exists 
none exists 
none exists 
none exists 
none exists 
2
3*
5*
7*
9*
11*
13*
15*
17*
3
4*
6*
12*
[18, 30] 
[28, 62] 
[36, 122] 
[52, 244] 
[76, 488] 
4
none exists
9*
[16, 33] 
[27, 96] 
[44, 291] 
[81, 867] 
[134, 2595] 
[243, 7779] 
5
none exists
none exists 
[16, 52] 
[28, 248] 
[62, 984] 
[124, 3928] 
[254, 11294] 
[500, 62808] 
 

To confirm the first two rows and extend them infinitely to the right, note that K2 is the only connected (equivalently, finite diameter) 1-regular graph and that cycles are the only connected 2-regular graphs.

To check that the first column is correct, note that the diameter-1 graphs are exactly the complete graphs (by definition) and that both K5 and K6 are nonplanar.

The upper bounds for (5,3) and (5,7) come from the following paper:

M. Fellows, P. Hell, and K. Seyffarth. Large planar graphs with given diameter and maximum degree. Disc. Appl. Math. 61 (1995), 133-153. MR 96e:05081.

The lower bound for (5,4) comes from a graph constructed by James Preen using a genetic algorithm. Preen also constructed the (4,4) graph.

Most of the previously best-known lower bounds and a proof of the non-existence of (5,2) can be found in the following paper:

F. Göbel and W. Kern. Planar regular graphs with prescribed diameter. Univ. of Twente (The Netherlands) Applied Math. Memorandum No. 1183, December 1993.

The lower bounds for (3,D), D ≥ 6; (4,D), D ≥ 5; and (5,D), D ≥ 5 arise from improving the constructions of Göbel and Kern.

The lower bound for (4,D), D even and ≥ 4, given without proof in Proposition 3.2(c) in the Göbel/Kern paper, should be 8*3D/2-1-2. Also, the lower bound for (4,D), D odd and ≥ 5, should be 4*3(D-1)/2-2. These corrections have been verified by Frits Göbel, but Erich Friedman and I have improved the bounds, as reflected in the table.

Friedman and I are working on a paper together detailing the many recent improvements.  For pictures of the largest-known regular graphs, see Friedman's slightly smaller table.

The second table gives the best-known upper bounds for the number of vertices in a planar (but not necessarily regular) graph with maximum degree Δ and diameter D. The newest bounds (due to Friedman and me) are in bold.  Bounds known to be optimal are marked with an asterisk.

The third table gives the best-known lower bounds for the number of vertices in a planar (but not necessarily regular) graph with maximum degree Δ and diameter D. Almost all of these bounds are due to Fellows, Hell, and Seyffarth. The lower bounds for (3,6) and (5,4) come from graphs constructed by Geoff Exoo using simulated annealing and tabu search. The lower bounds for Δ = 4 agree with those for regular graphs. Again, bounds known to be optimal are marked with an asterisk.

UPPER BOUNDS FOR LARGEST PLANAR GRAPHS WITH MAXIMUM DEGREE Δ AND DIAMETER D (November 20, 1998)
Δ \ D 
2
3
4
5
6
7
8
9
10
3
7*
15
31
63
127
255
511
1023
2047
4
11
35
104
313
934
2797
8386
25153
75454
5
13
52
248
984
3928
11295
62808
71307
393813
6
13
60
521
2409
12971
19485
132243
147801
979839
7
13
68
938
3267
26793
30915
244953
273771
2117745
8
13*
76
1529
4257
39975
46125
417843
467001
4128831
9
14*
84
2324
5379
56901
65655
669273
748011
7440237
10
16*
92
3353
6633
78039
90045
1020051
1140057
12600063
11
17*
100
4646
8019
103857
119835
1493433
1669131
20292489
12
19*
108
6233
9537
134823
155565
2115123
2363961
31352895
13
20*
116
8144
11187
171405
197775
2913273
3256011
46782981
14
22*
124
10409
12969
214071
247005
3918483
4379481
67765887
15
23*
132
12177
14883
263289
303795
5163801
5771307
95681313
16
25*
140
13851
16929
319527
368685
6684723
7471161
132120639
 
LOWER BOUNDS FOR LARGEST PLANAR GRAPHS WITH MAXIMUM DEGREE Δ AND DIAMETER D (July 30, 2001)
Δ \ D 
2
3
4
5
6
7
8
9
10
3
7*
12
18
28
38
53
77
109
157
4
9
16
27
44
81
134
243
404
729
5
10
19
39
73
150
289
598
1153
2390
6
11
24
52
114
262
564
1312
2814
6562
7
12
28
71
161
428
959
2570
5747
15422
8
13*
33
93
225
653
1569
4573
10977
32013
9
14*
37
118
289
946
2305
7570
18433
60562
10
16*
42
146
372
1316
3342
11846
30072
106616
 

Links to this page.

Please send any updates or corrections to: rpratt@email.unc.edu

Return to my home page.