TOPICS
Search

Outerplanar Graph


An outerplanar graph is a graph that can be embedded in the plane such that all vertices lie on the outer face. Outerplanar graphs are planar and, by their definition, connected graphs.

The complete graph K_4 and complete bipartite graph K_(2,3) are planar, but not outerplanar (West 2000, p. 240). In fact, a graph is outerplanar iff it contains no subgraph homeomorphic to the complete graph K_4 or complete bipartite graph K_(2,3) (Skiena 1990, p. 251, with K_5 corrected to K_4).

A graph is outerplanar iff the graph formed by adding a new vertex connected to each of the original vertices is a planar graph (Felsner 2004).

An outerplanar graph on n>2 vertices is Hamiltonian iff it is biconnected, in which case the vertices of outer face comprise a unique Hamiltonian cycle.

Every outerplanar graph is 3-colorable.


See also

Planar Graph

Explore with Wolfram|Alpha

References

Felsner, S. Geometric Graphs and Arrangements: Some Chapters from Combinational Geometry. Wiesbaden, Germany: Vieweg+Teubner Verlag, p. 6, 2004.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 239-240, 2000.

Cite this as:

Weisstein, Eric W. "Outerplanar Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/OuterplanarGraph.html

Subject classifications