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 question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)
“Whatever else American thinkers do, they psychologize, often brilliantly. The trouble is that psychology only takes us so far. The new interest in families has its merits, but it will have done us all a disservice if it turns us away from public issues to private matters. A vision of things that has no room for the inner life is bankrupt, but a psychology without social analysis or politics is both powerless and very lonely.”
—Joseph Featherstone (20th century)