Editing Outerplanar graph

{{Short description|Non-crossing graph with vertices on outer face}}
[[File:Triangulation 3-coloring.svg|thumb|A maximal outerplanar graph and its 3-coloring]]
[[File:Finite-3-regular-graph-4-vertices.png|thumb|The [[complete graph]] K<sub>4</sub> is the smallest planar graph that is not outerplanar.]]
In [[graph theory]], an '''outerplanar graph''' is a graph that has a [[planar graph|planar drawing]] for which all vertices belong to the outer face of the drawing.

Outerplanar graphs may be characterized (analogously to [[Wagner's theorem]] for planar graphs) by the two [[forbidden minor]]s {{math|''K''<sub>4</sub>}} and {{math|''K''<sub>2,3</sub>}}, or by their [[Colin de Verdière graph invariant]]s.
They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has [[Degeneracy (graph theory)|degeneracy]] and [[treewidth]] at most&nbsp;2.

The outerplanar graphs are a subset of the [[planar graph]]s, the subgraphs of [[series–parallel graph]]s, and the [[circle graph]]s. The '''maximal outerplanar graphs''', those to which no more edges can be added while preserving outerplanarity, are also [[chordal graph]]s and [[visibility graph]]s.

==History==
Outerplanar graphs were first studied and named by {{harvtxt|Chartrand|Harary|1967}}, in connection with the problem of determining the planarity of graphs formed by using a [[perfect matching]] to connect two copies of a base graph (for instance, many of the [[generalized Petersen graph]]s are formed in this way from two copies of a [[cycle graph]]). As they showed, when the base graph is [[biconnected graph|biconnected]], a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a [[dihedral group|dihedral]] permutation of its outer cycle. Chartrand and Harary also proved an analogue of [[Kuratowski's theorem]] for outerplanar graphs, that a graph is outerplanar if and only if it does not contain a [[Homeomorphism (graph theory)|subdivision]] of one of the two graphs ''K''<sub>4</sub> or ''K''<sub>2,3</sub>.

==Definition and characterizations==
An outerplanar graph is an [[undirected graph]] that can be [[graph embedding|drawn]] in the [[Euclidean plane|plane]] without [[crossing number (graph theory)|crossings]] in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges. Alternatively, a graph ''G'' is outerplanar if the graph formed from ''G'' by adding a new vertex, with edges connecting it to all the other vertices, is a [[planar graph]].<ref>{{harvtxt|Wiegers|1986}}</ref><ref>{{harvtxt|Felsner|2004}}.</ref>

A '''maximal outerplanar graph''' is an outerplanar graph that cannot have any additional edges added to it while preserving outerplanarity. Every maximal outerplanar graph with ''n'' vertices has exactly 2''n''&nbsp;&minus;&nbsp;3 edges, and every bounded face of a maximal outerplanar graph is a triangle.

===Forbidden graphs===
Outerplanar graphs have a [[forbidden graph characterization]] analogous to [[Kuratowski's theorem]] and [[Wagner's theorem]] for planar graphs: a graph is outerplanar if and only if it does not contain a [[Homeomorphism (graph theory)|subdivision]] of the [[complete graph]] ''K''<sub>4</sub> or the [[complete bipartite graph]] ''K''<sub>2,3</sub>.<ref>{{harvtxt|Chartrand|Harary|1967}}; {{harvtxt|Sysło|1979}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Proposition 7.3.1, p. 117; {{harvtxt|Felsner|2004}}.</ref> Alternatively, a graph is outerplanar if and only if it does not contain ''K''<sub>4</sub> or ''K''<sub>2,3</sub> as a [[minor (graph theory)|minor]], a graph obtained from it by deleting and contracting edges.<ref>{{harvtxt|Diestel|2000}}.</ref>

A [[triangle-free graph]] is outerplanar if and only if it does not contain a subdivision of ''K''<sub>2,3</sub>.<ref name="s79"/>

===Colin de Verdière invariant===
A graph is outerplanar if and only if its [[Colin de Verdière graph invariant]] is at most two. The graphs characterized in a similar way by having Colin de Verdière invariant at most one, three, or four are respectively the linear forests, [[planar graph]]s, and
[[linkless embedding|linklessly embeddable graphs]].

==Properties==

===Biconnectivity and Hamiltonicity===
An outerplanar graph is [[biconnected graph|biconnected]] if and only if the outer face of the graph forms a [[cycle (graph theory)|simple cycle]] without repeated vertices. An outerplanar graph is [[Hamiltonian cycle|Hamiltonian]] if and only if it is biconnected; in this case, the outer face forms the unique Hamiltonian cycle.<ref>{{harvtxt|Chartrand|Harary|1967}}; {{harvtxt|Sysło|1979}}.</ref> More generally, the size of the longest cycle in an outerplanar graph is the same as the number of vertices in its largest [[biconnected component]]. For this reason finding Hamiltonian cycles and longest cycles in outerplanar graphs may be solved in [[linear time]], in contrast to the [[NP-complete]]ness of these problems for arbitrary graphs.

Every maximal outerplanar graph satisfies a stronger condition than Hamiltonicity: it is [[pancyclic graph|node pancyclic]], meaning that for every vertex ''v'' and every ''k'' in the range from three to the number of vertices in the graph, there is a length-''k'' cycle containing ''v''. A cycle of this length may be found by repeatedly removing a triangle that is connected to the rest of the graph by a single edge, such that the removed vertex is not ''v'', until the outer face of the remaining graph has length ''k''.<ref>{{harvtxt|Li|Corneil|Mendelsohn|2000}}, Proposition 2.5.</ref>

A planar graph is outerplanar if and only if each of its biconnected components is outerplanar.<ref name="s79">{{harvtxt|Sysło|1979}}.</ref>

===Coloring===
All loopless outerplanar graphs can be [[graph coloring|colored]] using only three colors;<ref name="ps86">{{harvtxt|Proskurowski|Sysło|1986}}.</ref> this fact features prominently in the simplified proof of [[Václav Chvátal|Chvátal's]] [[art gallery theorem]] by {{harvtxt|Fisk|1978}}. A 3-coloring may be found in [[linear time]] by a [[greedy coloring]] algorithm that removes any vertex of [[degree (graph theory)|degree]] at most two, colors the remaining graph recursively, and then adds back the removed vertex with a color different from the colors of its two neighbors.

According to [[Vizing's theorem]], the [[chromatic index]] of any graph (the minimum number of colors needed to color its edges so that no two adjacent edges have the same color) is either the maximum [[degree (graph theory)|degree]] of any vertex of the graph or one plus the maximum degree. However, in a connected outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a [[cycle (graph theory)|cycle]] of odd length.<ref>{{harvtxt|Fiorini|1975}}.</ref> An edge coloring with an optimal number of colors can be found in linear time based on a [[breadth first search|breadth-first traversal]] of the weak dual tree.<ref name="ps86"/>

===Other properties===
Outerplanar graphs have [[degeneracy (graph theory)|degeneracy]] at most two: every subgraph of an outerplanar graph contains a vertex with degree at most two.<ref>{{harvtxt|Lick|White|1970}}.</ref>

Outerplanar graphs have [[treewidth]] at most two, which implies that many graph optimization problems that are [[NP-complete]] for arbitrary graphs may be solved in [[polynomial time]] by [[dynamic programming]] when the input is outerplanar. More generally, ''k''-outerplanar graphs have treewidth O(''k'').<ref>{{harvtxt|Baker|1994}}.</ref>

Every outerplanar graph can be represented as an [[intersection graph]] of axis-aligned rectangles in the plane, so outerplanar graphs have [[boxicity]] at most two.<ref>{{harvtxt|Scheinerman|1984}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 54.</ref>

==Related families of graphs==
[[File:Cactus graph.svg|thumb|A [[cactus graph]]. The cacti form a subclass of the outerplanar graphs.]]
Every outerplanar graph is a [[planar graph]]. Every outerplanar graph is also a subgraph of a [[series–parallel graph]].<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 174.</ref> However, not all planar series–parallel graphs are outerplanar. The [[complete bipartite graph]] ''K''<sub>2,3</sub> is planar and series–parallel but not outerplanar. On the other hand, the [[complete graph]] ''K''<sub>4</sub> is planar but neither series–parallel nor outerplanar. Every [[tree (graph theory)|forest]] and every [[cactus graph]] are outerplanar.<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 169.</ref>

The [[planar dual|weak planar dual]] graph of an embedded outerplanar graph (the graph that has a vertex for every bounded face of the embedding, and an edge for every pair of adjacent bounded faces) is a forest, and the weak planar dual of a [[Halin graph]] is an outerplanar graph. A planar graph is outerplanar if and only if its weak dual is a forest, and it is Halin if and only if its weak dual is biconnected and outerplanar.<ref>{{harvtxt|Sysło|Proskurowski|1983}}.</ref>

There is a notion of degree of outerplanarity.  A 1-outerplanar embedding of a graph is the same as an outerplanar embedding.  For ''k''&nbsp;&gt;&nbsp;1 a planar embedding is said to be [[K-outerplanar graph|''k''-outerplanar]] if removing the vertices on the outer face results in a (''k''&nbsp;&minus;&nbsp;1)-outerplanar embedding.  
A graph is ''k''-outerplanar if it has a ''k''-outerplanar embedding.<ref>{{harvtxt|Kane|Basu|1976}}; {{harvtxt|Sysło|1979}}.</ref>

An [[1-planar graph#Generalizations and related concepts|outer-1-planar graph]], analogously to [[1-planar graph]]s can be drawn in a disk, with the vertices on the boundary of the disk, and with at most one crossing per edge.

Every maximal outerplanar graph is a [[chordal graph]]. Every maximal outerplanar graph is the [[visibility graph]] of a [[simple polygon]].<ref>{{harvtxt|El-Gindy|1985}}; {{harvtxt|Lin|Skiena|1995}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, Theorem 4.10.3, p. 65.</ref> Maximal outerplanar graphs are also formed as the graphs of [[polygon triangulation]]s. They are examples of [[k-tree|2-trees]], of [[series–parallel graph]]s, and of [[chordal graph]]s.

Every outerplanar graph is a [[circle graph]], the [[intersection graph]] of a set of chords of a circle.<ref>{{harvtxt|Wessel|Pöschel|1985}}; {{harvtxt|Unger|1988}}.</ref>

==Notes==
{{reflist|colwidth=30em}}

==References==
{{refbegin|colwidth=30em}}
*{{citation
 | last = Baker | first = Brenda S. | authorlink = Brenda Baker
 | doi = 10.1145/174644.174650
 | issue = 1
 | journal = [[Journal of the ACM]]
 | pages = 153–180
 | title = Approximation algorithms for NP-complete problems on planar graphs
 | volume = 41
 | year = 1994| s2cid = 9706753 | doi-access = free
 }}.
*{{citation
 | last1 = Boza | first1 = Luis
 | last2 = Fedriani | first2 = Eugenio M.
 | last3 = Núñez | first3 = Juan
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | pages = 79–91
 | title = The problem of outer embeddings in pseudosurfaces
 | volume = 71
 | year = 2004}}.
*{{citation
 | last1 = Boza | first1 = Luis
 | last2 = Fedriani | first2 = Eugenio M.
 | last3 = Núñez | first3 = Juan
 | journal = [[Ars Combinatoria (journal)|Ars Combinatoria]]
 | pages = 65–77
 | title = Obstruction sets for outer-bananas-surface graphs
 | volume = 73
 | year = 2004}}.
*{{citation
 | last1 = Boza | first1 = Luis
 | last2 = Fedriani | first2 = Eugenio M.
 | last3 = Núñez | first3 = Juan
 | journal = [[Acta Mathematica Hungarica]]
 | pages = 307–313
 | title = Uncountable graphs with all their vertices in one face
 | volume = 112
 | year = 2006 | issue = 4
 | doi=10.1007/s10474-006-0082-0 | doi-access= | hdl = 11441/163886
 | s2cid = 123241658
 }}.
*{{citation
 | last1 = Boza | first1 = Luis
 | last2 = Fedriani | first2 = Eugenio M.
 | last3 = Núñez | first3 = Juan
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 3359–3367
 | title = Outer-embeddability in certain pseudosurfaces arising from three spheres
 | volume = 310
 | year = 2010 | issue = 23
 | doi=10.1016/j.disc.2010.07.027| doi-access = free
 }}.
*{{citation
 | last1 = Brandstädt
 | first1 = Andreas
 | author1-link = Andreas Brandstädt
 | last2 = Le
 | first2 = Van Bang
 | last3 = Spinrad
 | first3 = Jeremy
 | title = Graph Classes: A Survey
 | series = SIAM Monographs on Discrete Mathematics and Applications
 | publisher = [[Society for Industrial and Applied Mathematics]]
 | year = 1999
 | isbn = 0-89871-432-X
 | url-access = registration
 | url = https://archive.org/details/graphclassessurv0000bran
 }}.
*{{citation
 | last1 = Chartrand | first1 = Gary | authorlink = Gary Chartrand
 | last2 = Harary | first2 = Frank | author2-link = Frank Harary
 | issue = 4
 | journal = Annales de l'Institut Henri Poincaré B
 | mr = 0227041
 | pages = 433–438
 | title = Planar permutation graphs
 | url = http://www.numdam.org/item?id=AIHPB_1967__3_4_433_0
 | volume = 3
 | year = 1967}}.
*{{citation
 | last = Diestel | first = Reinhard
 | isbn = 0-387-98976-5
 | page = 107
 | publisher = Springer-Verlag
 | series = [[Graduate Texts in Mathematics]]
 | title = Graph Theory
 | volume = 173
 | year = 2000}}.
*{{citation
 | last = El-Gindy | first = H.
 | publisher = [[McGill University]]
 | series = Ph.D. thesis
 | title = Hierarchical decomposition of polygons with applications
 | year = 1985}}. As cited by {{harvtxt|Brandstädt|Le|Spinrad|1999}}.
*{{citation
 | last = Felsner | first = Stefan
 | isbn = 978-3-528-06972-8
 | page = 6
 | publisher = Vieweg+Teubner Verlag
 | title = Geometric graphs and arrangements: some chapters from combinational geometry
 | year = 2004}}.
*{{citation
 | last = Fiorini | first = Stanley
 | doi = 10.1016/0095-8956(75)90060-X
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | pages = 35–38
 | title = On the chromatic index of outerplanar graphs
 | volume = 18
 | year = 1975| doi-access = free
 }}.
*{{citation
 | last = Fisk | first = Steve
 | doi = 10.1016/0095-8956(78)90059-X
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | page = 374
 | title = A short proof of Chvátal's watchman theorem
 | volume = 24
 | year = 1978| issue = 3
 | doi-access = 
 }}.
*{{citation
 | last1 = Fleischner | first1 = Herbert J.
 | last2 = Geller | first2 = D. P.
 | last3 = Harary | first3 = Frank | author3-link = Frank Harary
 | mr = 0389672
 | journal = Journal of the Indian Mathematical Society
 | pages = 215–219
 | title = Outerplanar graphs and weak duals
 | volume = 38
 | year = 1974}}.
*{{citation
 | last1 = Kane | first1 = Vinay G.
 | last2 = Basu | first2 = Sanat K.
 | doi = 10.1016/0012-365X(76)90006-6
 | issue = 1
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 63–67
 | title = On the depth of a planar graph
 | volume = 14
 | year = 1976| doi-access = free
 }}.
*{{citation
 | last1 = Li | first1 = Ming-Chu
 | last2 = Corneil | first2 = Derek G. | author2-link = Derek Corneil
 | last3 = Mendelsohn | first3 = Eric
 | doi = 10.1016/S0166-218X(99)00163-8
 | issue = 3
 | journal = [[Discrete Applied Mathematics]]
 | pages = 219–225
 | title = Pancyclicity and NP-completeness in planar graphs
 | volume = 98
 | year = 2000| doi-access = free
 }}.
*{{citation
 | last1 = Lick | first1 = Don R.
 | last2 = White | first2 = Arthur T.
 | journal = [[Canadian Journal of Mathematics]]
 | pages = 1082–1096
 | title = {{mvar|k}}-degenerate graphs
 | url = http://www.smc.math.ca/cjm/v22/p1082
 | volume = 22
 | year = 1970
 | issue = 5
 | doi=10.4153/CJM-1970-125-1| s2cid = 124609794
 | doi-access = free
 }}.
*{{citation
 | last1 = Lin | first1 = Yaw-Ling
 | last2 = Skiena | first2 = Steven S. | author2-link = Steven Skiena
 | doi = 10.1142/S0218195995000179
 | issue = 3
 | journal = [[International Journal of Computational Geometry and Applications]]
 | pages = 289–312
 | title = Complexity aspects of visibility graphs
 | volume = 5
 | year = 1995}}.
*{{citation
 | last1 = Proskurowski | first1 = Andrzej
 | last2 = Sysło | first2 = Maciej M.
 | doi = 10.1137/0607016
 | journal = SIAM Journal on Algebraic and Discrete Methods
 | pages = 131–136
 | title = Efficient vertex-and edge-coloring of outerplanar graphs
 | volume = 7
 | year = 1986}}.
*{{citation
 | last = Scheinerman | first = E. R. | authorlink = Ed Scheinerman
 | publisher = [[Princeton University]]
 | series = Ph.D. thesis
 | title = Intersection Classes and Multiple Intersection Parameters of a Graph
 | year = 1984}}. As cited by {{harvtxt|Brandstädt|Le|Spinrad|1999}}.
*{{citation
 | last = Sysło | first = Maciej M.
 | doi = 10.1016/0012-365X(79)90060-8
 | issue = 1
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 47–53
 | title = Characterizations of outerplanar graphs
 | volume = 26
 | year = 1979| doi-access = 
 }}.
*{{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}}.
*{{citation
 | last = Unger | first = Walter
 | contribution = On the {{mvar|k}}-colouring of circle-graphs
 | doi = 10.1007/BFb0035832
 | pages = 61–72
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = Proc. 5th [[Symposium on Theoretical Aspects of Computer Science]] (STACS '88)
 | volume = 294
 | year = 1988| isbn = 3-540-18834-7
 }}.
*{{citation
 | last1 = Wessel | first1 = W.
 | last2 = Pöschel | first2 = R.
 | contribution = On circle graphs
 | editor-last = Sachs | editor-first = Horst | editor-link = Horst Sachs
 | pages = 207–210
 | publisher = B.G. Teubner
 | series = Teubner-Texte zur Mathematik
 | title = Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984
 | volume = 73
 | year = 1985}}. As cited by {{harvtxt|Unger|1988}}.
*{{citation
 | last = Wiegers | first = Manfred | title = Graph-Theoretic Concepts in Computer Science | authorlink = Wiegers
 | doi = 10.1007/3-540-17218-1_57
 | series = [[Lecture Notes in Computer Science]]
 | pages = 165–176
 | chapter = Recognizing Outerplanar Graphs in Linear Time
 | volume = 246
 | year = 1986 | doi-access = free
 | isbn = 978-3-540-17218-5 }}.
{{refend}}

==External links==
*[http://www.graphclasses.org/classes/gc_110.html Outerplanar graphs] at the [http://www.graphclasses.org Information System on Graph Classes and Their Inclusions]
*{{mathworld|title=Outplanar Graph|urlname=OutplanarGraph}}

[[Category:Planar graphs]]
[[Category:Graph families]]