The Degree Diameter Problem for Planar Graphs

Citation

If you are using combinatoricsWiki, then we would like to ask you to cite the site as follows.

• E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). Combinatorics Wiki, http://combinatoricswiki.org.

If you are using a specific page in combinatoricsWiki, say the "The degree-diameter problem for planar graphs" page, then it would be better to cite the page as follows.

• E. Loz, H. P\'erez-Ros\'es and G.Pineda-Villavicencio (2010). The degree-diameter problem for planar graphs, Combinatorics Wiki, http://combinatoricswiki.org.

Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem

[math]d[/math]\[math]k[/math]	2	3	4	5	6	7	8
3	6	12	18	28	36	52	76
4	9	16	27	44	81	134	243
5	NA	16	28	62	124	254	500

Optimal graphs are marked in bold. The following table is the key to the colors in the table presented above:

Color	Details
*	Graphs found by Preen.
*	Graphs found by Pratt and Friedman.

Table of the orders of the largest known planar graphs for the undirected degree diameter problem

[math]d[/math]\[math]k[/math]	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	728
5	10	19	39	73	158	289	638	1153	2558
6	11	24	55	117	280	579	1405	2889	7030
7	12	28	74	165	452	984	2720	5898	16328
8	13	33	97	228	685	1590	4901	11124	33613
9	14	37	122	293	986	2338	7898	18698	63194
10	16	42	151	375	1366	3369	12301	30315	110716

Optimal graphs are marked in bold. The following table is the key to the colors in the table presented above:

Color	Details
*	Graphs of unknown author.
*	Graphs found by Fellows, Hell, and Seyffarth. Details are available in a paper by the authors.
*	Graphs found by Yang, Lin, and Dai. Details are available in a paper by the authors.
*	Graphs found by Geoffrey Exoo.
*	Graphs found by S. A. Tishchenko. Details are available in a paper by the author.
*	Graphs found by R. Feria-Purón and G. Pineda-Villavicencio. Details are available in a paper by the authors.

References

• Fellows, M.; Hell, P.; Seyffarth, K. (1998), "Constructions of large planar networks with given degree and diameter", Networks 32: 275-281.

• Feria-Purón, R.; Pineda-Villavicencio, G. (2013), "Constructions of large graphs on surfaces", preprint, PDF version.

• Tishchenko, S. A. (2012), "Maximum size of a planar graph with given degree and even diameter", European Journal of Combinatorics 33: 380-396.

• Yang, Y.; Lin, J.; Dai, Y. (2002), "Largest planar graphs and largest maximal planar graphs of diameter two", Journal of Computational and Applied Mathematics 144:349-358.

External links

• Tables of the largest known planar graphs maintained by James Preen