Editing Outerplanar graph (section)

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