Guillermo at 05:54, 18 February 2022

2022-02-18T05:54:19Z

Grahame: 1 revision imported

2019-01-03T14:39:33Z

1 revision imported

CW>Gpineda: /* Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem */

2013-06-07T14:43:33Z

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

New page

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

<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8'''
|-
| '''3''' || style="background-color: blue; text-align: center;" |6 || style="background-color: blue; text-align: center;" |12 ||style="background-color: blue; text-align: center;" | 18 || style="background-color: blue; text-align: center;" |28 ||style="background-color: brown; text-align: center;" | 36 || style="background-color: brown; text-align: center;" |52 ||style="background-color: brown; text-align: center;" | 76
|-
| '''4''' ||style="background-color: blue; text-align: center;" | 9 || style="background-color: blue; text-align: center;" |16 || style="background-color: yellow; text-align: center;" |27 || style="background-color: brown; text-align: center;" |44 ||style="background-color: brown; text-align: center;" | 81 || style="background-color: brown; text-align: center;" |134 ||style="background-color: brown; text-align: center;" | 243
|-
| '''5''' || NA ||style="background-color: blue; text-align: center;" | '''16''' || style="background-color: yellow; text-align: center;" |28 || style="background-color: brown; text-align: center;" |62 || style="background-color: brown; text-align: center;" |124 ||style="background-color: brown; text-align: center;" | 254 ||style="background-color: brown; text-align: center;" | 500
|-
|}
</center>

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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: yellow; text-align: center;" | * || Graphs found by Preen.
|-
|style="background-color: brown; text-align: center;" | * || Graphs found by Pratt and Friedman.
|}
</center>

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

<center>
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10'''
|-
| '''3''' || style="background-color: red; text-align: center;" | '''7''' || style="background-color: blue; text-align: center;" | '''12''' || style="background-color: blue; text-align: center;" | 18 || style="background-color: blue; text-align: center;" | 28 || style="background-color: purple; text-align: center;" | 38||style="background-color: red; text-align: center;" | 53||style="background-color: red; text-align: center;" | 77||style="background-color: red; text-align: center;" |109||style="background-color: red; text-align: center;" |157
|-
| '''4''' || style="background-color: green; text-align: center;" | '''9''' || style="background-color: blue; text-align: center;" | 16 || style="background-color: blue; text-align: center;" | 27 || style="background-color: red; text-align: center;" | 44 || style="background-color: blue; text-align: center;" | 81||style="background-color: red; text-align: center;" |134||style="background-color: yellow; text-align: center;" | 243||style="background-color: red; text-align: center;" |404||style="background-color: red; text-align: center;" |728
|-
| '''5''' || style="background-color: green; text-align: center;" | '''10''' || style="background-color: red; text-align: center;" | 19 || style="background-color: purple; text-align: center;" | 39 || style="background-color: red; text-align: center;" | 73 || style="background-color:yellow; text-align: center;" | 158||style="background-color: red; text-align: center;" |289||style="background-color: yellow; text-align: center;" |638||style="background-color: red; text-align: center;" |1153||style="background-color:yellow; text-align: center;" |2558
|-
| '''6''' || style="background-color: green; text-align: center;" | '''11''' || style="background-color: red; text-align: center;" | 24 || style="background-color:yellow; text-align: center;" | 55 || style="background-color: #00ff7f; text-align: center;" | 117 || style="background-color: yellow; text-align: center;" | 280||style="background-color: #00ff7f; text-align: center;" |579||style="background-color:yellow; text-align: center;" |1405||style="background-color: #00ff7f; text-align: center;" |2889||style="background-color:yellow; text-align: center;" |7030
|-
| '''7''' || style="background-color: green; text-align: center;" | '''12''' || style="background-color: red; text-align: center;" | 28 || style="background-color:yellow; text-align: center;" | 74 || style="background-color: #00ff7f; text-align: center;" | 165 || style="background-color: yellow; text-align: center;" | 452||style="background-color: #00ff7f; text-align: center;" | 984||style="background-color:yellow; text-align: center;" |2720||style="background-color: #00ff7f; text-align: center;" |5898||style="background-color:yellow; text-align: center;" |16328
|-
| '''8''' || style="background-color: red; text-align: center;" | '''13'''|| style="background-color: red; text-align: center;" | 33 || style="background-color:yellow; text-align: center;" | 97 || style="background-color: #00ff7f; text-align: center;" | 228 || style="background-color: yellow; text-align: center;" |685||style="background-color: #00ff7f; text-align: center;" | 1590||style="background-color:yellow; text-align: center;" |4901||style="background-color: #00ff7f; text-align: center;" |11124||style="background-color:yellow; text-align: center;" |33613
|-
| '''9''' || style="background-color: red; text-align: center;" | '''14''' || style="background-color: red; text-align: center;" | 37 || style="background-color:yellow; text-align: center;" | 122 || style="background-color: #00ff7f; text-align: center;" | 293 || style="background-color: yellow; text-align: center;" |986||style="background-color: #00ff7f; text-align: center;" | 2338||style="background-color:yellow; text-align: center;" |7898||style="background-color: #00ff7f; text-align: center;" |18698||style="background-color:yellow; text-align: center;" |63194
|-
| '''10''' || style="background-color: red; text-align: center;" | '''16''' || style="background-color: red; text-align: center;" | 42 || style="background-color: yellow; text-align: center;" | 151 || style="background-color: #00ff7f; text-align: center;" | 375 || style="background-color: yellow; text-align: center;" | 1366||style="background-color: #00ff7f; text-align: center;" | 3369||style="background-color:yellow; text-align: center;" |12301||style="background-color: #00ff7f; text-align: center;" |30315||style="background-color:yellow; text-align: center;" |110716
|-
|}
</center>

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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: blue; text-align: center;" | * || Graphs of unknown author.
|-
|style="background-color: red; text-align: center;" | * || Graphs found by Fellows, Hell, and Seyffarth. Details are available in a paper by the authors.
|-
|style="background-color: green; text-align: center;" | * || Graphs found by Yang, Lin, and Dai. Details are available in a paper by the authors.
|-
|style="background-color: purple; text-align: center;" | * || Graphs found by Geoffrey Exoo.
|-
|style="background-color: yellow; text-align: center;" | * || Graphs found by S. A. Tishchenko. Details are available in a paper by the author.
|-
|style="background-color: #00ff7f; text-align: center;" | * || Graphs found by R. Feria-Purón and G. Pineda-Villavicencio. Details are available in a paper by the authors.
|}
</center>

==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, [http://arxiv.org/pdf/1302.1648v1.pdf 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==

*[http://faculty.cbu.ca/jpreen/degdiam.html Tables of the largest known planar graphs maintained by James Preen]

[[Category:The Degree/Diameter Problem]]

← Older revision		Revision as of 05:54, 18 February 2022
Line 1:		Line 1:
		+	==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==		==Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem==

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)

The Degree Diameter Problem for Planar Graphs - Revision history

Guillermo at 05:54, 18 February 2022

Grahame: 1 revision imported

CW>Gpineda: /* Table of the orders of the largest known regular planar graphs for the undirected degree diameter problem */