Triangulated Graph

A planar graph is said to be triangulated (also called maximal planar) if the addition of any edge to results in a nonplanar graph.

If the special cases of the triangle graph and tetrahedral graph (which are planar that already contain a maximal number of edges) are included, maximal planar graphs are the skeletons of simple polyhedra and are isomorphic to planar graphs with edges.

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

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 graph
26	disdyakis dodecahedral graph
32	pentakis dodecahedral graph
32	triakis icosahedral graph
62	disdyakis triacontahedral graph
341	Moore's graph

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