![Finite-3-regular-graph-4-vertices](https://upload.wikimedia.org/wikipedia/commons/1/1d/Finite-3-regular-graph-4-vertices.png)
In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, an outerplanar graph is a graph that has a
planar drawing for which all vertices belong to the outer face of the drawing.
Outerplanar graphs may be characterized (analogously to
Wagner's theorem
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on fi ...
for planar graphs) by the two
forbidden minor
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
s and , or by their
Colin de Verdière graph invariant Colin de Verdière's invariant is a graph parameter \mu(G) for any graph ''G,'' introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.
D ...
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 and
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
at most 2.
The outerplanar graphs are a subset of the
planar graphs, the subgraphs of
series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
s, and the
circle graphs. The maximal outerplanar graphs, those to which no more edges can be added while preserving outerplanarity, are also
chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
s and
visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge rep ...
s.
History
Outerplanar graphs were first studied and named by , in connection with the problem of determining the planarity of graphs formed by using a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...
to connect two copies of a base graph (for instance, many of the
generalized Petersen graph
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways ...
s are formed in this way from two copies of a
cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
). As they showed, when the base graph is
biconnected, a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a
dihedral permutation of its outer cycle. Chartrand and Harary also proved an analogue of
Kuratowski's theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdi ...
for outerplanar graphs, that a graph is outerplanar if and only if it does not contain a
subdivision of one of the two graphs ''K''
4 or ''K''
2,3.
Definition and characterizations
An outerplanar graph is an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
that can be
drawn in the
plane
Plane(s) most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
Plane or planes may also refer to:
Biology
* Plane (tree) or ''Platanus'', wetland native plant
* ''Planes' ...
without
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.
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'' − 3 edges, and every bounded face of a maximal outerplanar graph is a triangle.
Forbidden graphs
Outerplanar graphs have a
forbidden graph characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
analogous to
Kuratowski's theorem
In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdi ...
and
Wagner's theorem
In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on fi ...
for planar graphs: a graph is outerplanar if and only if it does not contain a
subdivision of the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
''K''
4 or the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
''K''
2,3. Alternatively, a graph is outerplanar if and only if it does not contain ''K''
4 or ''K''
2,3 as a
minor, a graph obtained from it by deleting and contracting edges.
A
triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...
is outerplanar if and only if it does not contain a subdivision of ''K''
2,3.
Colin de Verdière invariant
A graph is outerplanar if and only if its
Colin de Verdière graph invariant Colin de Verdière's invariant is a graph parameter \mu(G) for any graph ''G,'' introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.
D ...
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 graphs, and
linklessly embeddable graphs.
Properties
Biconnectivity and Hamiltonicity
An outerplanar graph is
biconnected if and only if the outer face of the graph forms a
simple cycle without repeated vertices. An outerplanar graph is
Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
if and only if it is biconnected; in this case, the outer face forms the unique Hamiltonian cycle. 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
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks a ...
. For this reason finding Hamiltonian cycles and longest cycles in outerplanar graphs may be solved in
linear time, in contrast to the
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
ness of these problems for arbitrary graphs.
Every maximal outerplanar graph satisfies a stronger condition than Hamiltonicity: it is
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''.
A planar graph is outerplanar if and only if each of its biconnected components is outerplanar.
[.]
Coloring
All loopless outerplanar graphs can be
colored
''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in Sout ...
using only three colors;
[.] this fact features prominently in the simplified proof of
Chvátal's art gallery theorem
Art is a diverse range of human activity, and resulting product, that involves creative or imaginative talent expressive of technical proficiency, beauty, emotional power, or conceptual ideas.
There is no generally agreed definition of what ...
by . A 3-coloring may be found in
linear time by a
greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...
algorithm that removes any vertex of
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 In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree of the graph.
At least colors are always necessary, so the undirected gra ...
, the
chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...
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 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 of odd length. An edge coloring with an optimal number of colors can be found in linear time based on a
breadth-first traversal of the weak dual tree.
Other properties
Outerplanar graphs have
degeneracy at most two: every subgraph of an outerplanar graph contains a vertex with degree at most two.
Outerplanar graphs have
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
at most two, which implies that many graph optimization problems that are
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
for arbitrary graphs may be solved in
polynomial time by
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. ...
when the input is outerplanar. More generally, ''k''-outerplanar graphs have treewidth O(''k'').
Every outerplanar graph can be represented as an
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of axis-aligned rectangles in the plane, so outerplanar graphs have
boxicity
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there mu ...
at most two.
Related families of graphs
![Cactus graph](https://upload.wikimedia.org/wikipedia/commons/2/2f/Cactus_graph.svg)
Every outerplanar graph is a
planar graph. Every outerplanar graph is also a subgraph of a
series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
. However, not all planar series–parallel graphs are outerplanar. The
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
''K''
2,3 is planar and series–parallel but not outerplanar. On the other hand, the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
''K''
4 is planar but neither series–parallel nor outerplanar. Every
forest
A forest is an area of land dominated by trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological function. The United Nations' ...
and every
cactus graph
In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ...
are outerplanar.
The
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
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.
The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none o ...
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.
There is a notion of degree of outerplanarity. A 1-outerplanar embedding of a graph is the same as an outerplanar embedding. For ''k'' > 1 a planar embedding is said to be
''k''-outerplanar if removing the vertices on the outer face results in a (''k'' − 1)-outerplanar embedding.
A graph is ''k''-outerplanar if it has a ''k''-outerplanar embedding.
An
outer-1-planar graph, analogously to
1-planar graph
In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. If a 1-planar graph, one of the most natural ...
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
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
. Every maximal outerplanar graph is the
visibility graph In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge rep ...
of a
simple polygon
In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If ...
. Maximal outerplanar graphs are also formed as the graphs of
polygon triangulations. They are examples of
2-trees, of
series–parallel graph
In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and t ...
s, and of
chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced c ...
s.
Every outerplanar graph is a
circle graph, the
intersection graph
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
of a set of chords of a circle.
[; .]
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*. As cited by .
*.
*.
*.
*.
*.
*.
*.
*.
*.
*. As cited by .
*.
*.
*.
*. As cited by .
External links
Outerplanar graphsat th
Information System on Graph Classes and Their Inclusions*{{mathworld, title=Outplanar Graph, urlname=OutplanarGraph
Planar graphs
Graph families