page_title: Planar graph
section_title: Maximal planar graphs
hierarchical_section_title: Planar graph / Related families of graphs / Maximal planar graphs
context_page_description: In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
  Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection.
  Plane graphs can be encoded by combinatorial maps.
  The equivalence class of topologically equivalent drawings on the sphere is called a planar map. Although a plane graph has an external or unbounded face, none of the faces of a planar map have a particular status.
  Planar graphs generalize to graphs drawable on a surface of a given genus. In this terminology, planar graphs have graph genus 0, since the plane are surfaces of genus 0.
context_section_description: A simple graph is called maximal planar if it is planar but adding any edge (on the given vertex set) would destroy that property. All faces (including the outer one) are then bounded by three edges, explaining the alternative term plane triangulation. The alternative names "triangular graph" or "triangulated graph" have also been used, but are ambiguous, as they more commonly refer to the line graph of a complete graph and to the chordal graphs respectively. Every maximal planar is 3-vertex-connected.
  If a maximal planar graph has v vertices with v > 2, then it has precisely 3v − 6 edges and 2v − 4 faces.
  Apollonian networks are the maximal planar graphs formed by repeatedly splitting triangular faces into triples of smaller triangles.  Equivalently, they are the planar 3-trees.
  Strangulated graphs are the graphs in which every peripheral cycle is a triangle. In a maximal planar graph (or more generally a polyhedral graph) the peripheral cycles are the faces, so maximal planar graphs are strangulated. The strangulated graphs include also the chordal graphs, and are exactly the graphs that can be formed by clique-sums (without deleting edges) of complete graphs and maximal planar graphs.
caption: The Goldner–Harary graph is maximal planar. All its faces are bounded by three edges.