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:
“The custard is setting; meanwhile
I not only have my own history to worry about
But am forced to fret over insufficient details related to large
Unfinished concepts that can never bring themselves to the point
Of being, with or without my help, if any were forthcoming.”
—John Ashbery (b. 1927)
“Affection, indulgence, and humor alike are powerless against the instinct of children to rebel. It is essential to their minds and their wills as exercise is to their bodies. If they have no reasons, they will invent them, like nations bound on war. It is hard to imagine families limp enough always to be at peace. Wherever there is character there will be conflict. The best that children and parents can hope for is that the wounds of their conflict may not be too deep or too lasting.”
—New York State Division of Youth Newsletter (20th century)