Outerplanar Graph - Related Families of Graphs

Related Families of Graphs

Every outerplanar graph is a planar graph. Every outerplanar graph is also a subgraph of a series-parallel graph. However, not all planar graphs and series-parallel graphs are outerplanar: the complete graph K4 is planar but neither series-parallel nor outerplanar, and the complete bipartite graph K2,3 is planar and series-parallel but not outerplanar. Every forest, and every cactus graph is 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 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.

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.

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 2n − 3 edges, and every bounded face of a maximal outerplanar graph is a triangle. An outerplanar graph is a chordal graph if and only if it is maximal outerplanar. Every maximal outerplanar graph is the visibility graph of a simple polygon. Maximal outerplanar graphs are also formed as the graphs of polygon triangulations. They are examples of 2-trees, of series-parallel graphs, and of chordal graphs.

Every outerplanar graph is a circle graph, the intersection graph of a set of chords of a circle.

Read more about this topic:  Outerplanar Graph

Famous quotes containing the words related and/or families:

    One does not realize the historical sensation as a re-experiencing, but as an understanding that is closely related to the understanding of music, or rather of the world by means of music.
    Johan Huizinga (1872–1945)

    The man who promised to reinforce American families is now eager to pull the plug on Big Bird and Barney.
    Leslie Harris, U.S. political activist. As quoted in Newsweek magazine, p. 23 (December 19, 1994)