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:
“A parent who from his own childhood experience is convinced of the value of fairy tales will have no difficulty in answering his child’s questions; but an adult who thinks these tales are only a bunch of lies had better not try telling them; he won’t be able to related them in a way which would enrich the child’s life.”
—Bruno Bettelheim (20th century)
“Being dismantled before our eyes are not just individual programs that politicians cite as too expensive but the whole idea that society has a stake in the well-being of children down the block and the security of families on the other side of town. Whether or not kids eat well, are nurtured and have a roof over their heads is not just a consequence of how their parents behave. It is also a responsibility of society—but now apparently a diminishing one.”
—Richard B. Stolley (20th century)