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:
“So-called “austerity,” the stoic injunction, is the path towards universal destruction. It is the old, the fatal, competitive path. “Pull in your belt” is a slogan closely related to “gird up your loins,” or the guns-butter metaphor.”
—Wyndham Lewis (1882–1957)
“Peer pressure is not a monolithic force that presses adolescents into the same mold. . . . Adolescents generally choose friend whose values, attitudes, tastes, and families are similar to their own. In short, good kids rarely go bad because of their friends.”
—Laurence Steinberg (20th century)