Triangulated Graph

A triangulated graph (also called maximal planar) is a finite simple graph on vertices that is a planar graph and for which adding any missing edge between two existing nonadjacent vertices results in a nonplanar graph.

For , triangulated graphs are the skeletons of simplicial convex polyhedra, whose dual polyhedra are simple polyhedra. They are precisely the planar graphs with edges. The triangle graph also satisfies this edge count but does not represent a nondegenerate polyhedron.

A list of triangulated graphs implemented in the Wolfram Language is available as GraphData["Triangulated"].

Two-dimensional Apollonian networks are triangulated graphs. The following table summarizes some named triangulated graphs.

	graph
3	triangle graph
4	tetrahedral graph
6	octahedral graph
8	triakis tetrahedral graph
9	Fritsch graph
11	Goldner-Harary graph
12	icosahedral graph
14	small triakis octahedral graph
14	tetrakis hexahedral graph
15	Poussin graph
17	Errera graph
23	Kittell graph
25	Heawood four-color map (original graph)
26	disdyakis dodecahedral graph
32	pentakis dodecahedral graph
32	triakis icosahedral graph
62	disdyakis triacontahedral graph
341	Moore four-color graph

The numbers of unlabeled maximal planar simple graphs on , 4, ... nodes are 1, 1, 1, 2, 5, 14, 50, 233, 1249, ... (OEIS A000109), the first few of which are illustrated above.