maximal planar graph

A planar graph G is said to be triangulated (also called maximal planar) if the addition of any edge to G results in a nonplanar graph. If the special cases of the triangle graph C_3 and tetrahedral graph K_4 (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 3n - 6 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.

critical nonplanar graph | Laman graph | nonplanar graph | planar graph | simple polyhedron