The Degree Diameter Problem for Planar Graphs

From Combinatorics Wiki

Citation

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

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