Editing Planar graph (section)

===Maximal planar graphs===
[[File:Goldner-Harary graph.svg|thumb|240px|The [[Goldner–Harary graph]] is maximal planar. All its faces are bounded by three edges.]]

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''' (which technically means a plane drawing of the graph). The alternative names "triangular graph"<ref>{{citation|first=W.|last=Schnyder|title=Planar graphs and poset dimension|journal=[[Order (journal)|Order]]|volume=5|year=1989|issue=4|pages=323–343|doi=10.1007/BF00353652|mr=1010382|s2cid=122785359}}.</ref> or "triangulated graph"<ref>{{citation|journal=Algorithmica|volume=3|issue=1–4|year=1988|pages=247–278|doi= 10.1007/BF01762117|title=A linear algorithm to find a rectangular dual of a planar triangulated graph|first1=Jayaram|last1=Bhasker|first2=Sartaj|last2=Sahni|s2cid=2709057}}.</ref> have also been used, but are ambiguous, as they more commonly refer to the [[line graph]] of a [[complete graph]] and to the [[chordal graph]]s respectively. Every maximal planar graph on more than 3 vertices is at least 3-connected.<ref>{{citation
 | last1 = Hakimi | first1 = S. L.
 | last2 = Schmeichel | first2 = E. F.
 | doi = 10.1002/jgt.3190020404
 | issue = 4
 | journal = Journal of Graph Theory
 | mr = 512801
 | pages = 307–314
 | title = On the connectivity of maximal planar graphs
 | volume = 2
 | year = 1978}}; Hakimi and Schmeichel credit the 3-connectivity of maximal planar graphs to a theorem of [[Hassler Whitney]].</ref>

If a maximal planar graph has {{mvar|v}} vertices with {{math|''v'' > 2}}, then it has precisely {{math|3''v'' − 6}} edges and {{math|2''v'' − 4}} faces.

[[Apollonian network]]s are the maximal planar graphs formed by repeatedly splitting triangular faces into triples of smaller triangles.  Equivalently, they are the planar [[k-tree|3-trees]].

[[Strangulated graph]]s 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 graph]]s, and are exactly the graphs that can be formed by [[clique-sum]]s (without deleting edges) of [[complete graph]]s and maximal planar graphs.<ref>{{citation
 | last1 = Seymour | first1 = P. D.
 | last2 = Weaver | first2 = R. W.
 | doi = 10.1002/jgt.3190080206
 | issue = 2
 | journal = Journal of Graph Theory
 | mr = 742878
 | pages = 241–251
 | title = A generalization of chordal graphs
 | volume = 8
 | year = 1984}}.</ref>