Editing Planar graph (section)

==Families of planar graphs==

===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>

===Outerplanar graphs===
[[Outerplanar graph]]s are graphs with an embedding in the plane such that all vertices belong to the unbounded face of the embedding. Every outerplanar graph is planar, but the converse is not true: {{math|''K''<sub>4</sub>}} is planar but not outerplanar. A theorem similar to Kuratowski's states that a finite graph is outerplanar if and only if it does not contain a subdivision of {{math|''K''<sub>4</sub>}} or of {{math|''K''<sub>2,3</sub>}}. The above is a direct corollary of the fact that a graph {{mvar|G}} is outerplanar if the graph formed from {{mvar|G}} by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph.<ref>{{citation
 | last = Felsner | first = Stefan
 | contribution = 1.4 Outerplanar Graphs and Convex Geometric Graphs
 | doi = 10.1007/978-3-322-80303-0_1
 | isbn = 3-528-06972-4
 | mr = 2061507
 | pages = 6–7
 | publisher = Friedr. Vieweg & Sohn, Wiesbaden
 | series = Advanced Lectures in Mathematics
 | title = Geometric graphs and arrangements
 | year = 2004}}</ref>

A 1-outerplanar embedding of a graph is the same as an outerplanar embedding.  For {{math|''k'' > 1}} a planar embedding is {{mvar|k}}-outerplanar if removing the vertices on the outer face results in a {{math|(''k'' − 1)}}-outerplanar embedding.  A graph is {{mvar|k}}-outerplanar if it has a {{mvar|k}}-outerplanar embedding.

===Halin graphs===
A [[Halin graph]] is a graph formed from an undirected plane tree (with no degree-two nodes) by connecting its leaves into a cycle, in the order given by the plane embedding of the tree. Equivalently, it is a [[polyhedral graph]] in which one face is adjacent to all the others. Every Halin graph is planar. Like outerplanar graphs, Halin graphs have low [[treewidth]], making many algorithmic problems on them more easily solved than in unrestricted planar graphs.<ref>{{citation
 | last1 = Sysło | first1 = Maciej M.
 | last2 = Proskurowski | first2 = Andrzej
 | contribution = On Halin graphs
 | doi = 10.1007/BFb0071635
 | pages = 248–256
 | publisher = Springer-Verlag
 | series = Lecture Notes in Mathematics
 | title = Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981
 | volume = 1018
 | isbn = 978-3-540-12687-4
 | year = 1983}}.</ref>

===Upward planar graphs===
An [[Upward planar drawing|upward planar graph]] is a [[directed acyclic graph]] that can be drawn in the plane with its edges as non-crossing curves that are consistently oriented in an upward direction. Not every planar directed acyclic graph is upward planar, and it is [[NP-complete]] to test whether a given graph is upward planar.

===Convex planar graphs===
A planar graph is said to be '''convex''' if all of its faces (including the outer face) are [[convex polygon]]s. Not all planar graphs have a convex embedding (e.g. the complete bipartite graph {{math|K{{sub|2,4}}}}). A sufficient condition that a graph can be drawn convexly is that it is a [[Subdivision (graph theory)|subdivision]] of a [[k-vertex-connected graph|3-vertex-connected]] planar graph. [[Tutte embedding|Tutte's spring theorem]] even states that for simple 3-vertex-connected planar graphs the position of the inner vertices can be chosen to be the average of its neighbors.

===Word-representable planar graphs===
[[Word-representable graph|Word-representable]] planar graphs include triangle-free planar graphs and, more generally, 3-colourable planar graphs,<ref name="HK|last=P16">{{cite journal |first1=M. |last1=Halldórsson |first2=S. |last2=Kitaev |first3=A. |last3=Pyatkin. |title=Semi-transitive orientations and word-representable graphs |journal=Discr. Appl. Math.  |volume=201  |issue= |pages=164–171  |doi= 10.1016/j.dam.2015.07.033|date=2016 |s2cid=26796091 |doi-access=free |url=https://strathprints.strath.ac.uk/54148/2/Halldorsson_etal_DAM_2015_Semi_transitive_orientations_and_word_representable.pdf }}</ref> as well as certain face subdivisions of triangular grid graphs,<ref name="CKS2016">{{cite journal |arxiv=1503.08002 |first1=T. Z. Q. |last1=Chen |first2=S. |last2=Kitaev |first3=B. Y. |last3=Sun |title=Word-representability of face subdivisions of triangular grid graphs |journal=Graphs and Combin |volume=32 |issue=5 |pages=1749–61 |date=2016 |doi= 10.1007/s00373-016-1693-z|s2cid=43817300 |url=}}</ref> and certain triangulations of grid-covered cylinder graphs.<ref name="CKS2016-2">{{cite journal |arxiv=1507.06749 |first1=T. Z. Q. |last1=Chen |first2=S. |last2=Kitaev |first3=B. Y. |last3=Sun |title=Word-representability of triangulations of grid-covered cylinder graphs |journal=Discr. Appl. Math. |volume=213 |issue= |pages=60–70 |date=2016 |doi= 10.1016/j.dam.2016.05.025|s2cid=26987743 |url=}}</ref>