Outerplanar graph

A maximal outerplanar graph and its 3-coloring.

In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges. Alternatively, a graph G is outerplanar if the graph formed from G by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph.^[1]

History

Outerplanar graphs were first studied and named by Chartrand & Harary (1967), in connection with the problem of determining the planarity of graphs formed by using a perfect matching to connect together two copies of a base graph (for instance, many of the generalized Petersen graphs are formed in this way from two copies of a cycle graph). As they showed, when the base graph is biconnected, a graph constructed in this way is planar if and only if its base graph is outerplanar and the matching forms a dihedral permutation of its outer cycle.

Forbidden graph characterizations

Outerplanar graphs have a forbidden graph characterization analogous to Kuratowski's theorem and Wagner's theorem for planar graphs: a graph is outerplanar if and only if it does not contain a subdivision of the complete graph K₄ or the complete bipartite graph K_2,3.^[2] Alternatively, a graph is outerplanar if and only if it does not contain K₄ or K_2,3 as a minor, a graph obtained from it by deleting and contracting edges.^[3]

A triangle-free graph is outerplanar if and only if it does not contain a subdivision of K_2,3.^[4]

Biconnectivity and Hamiltonicity

An outerplanar graph is biconnected if and only if the outer face of the graph forms a simple cycle without repeated vertices. An outerplanar graph is Hamiltonian if and only if it is biconnected; in this case, the outer face forms the unique Hamiltonian cycle.^[5] More generally, the size of the longest cycle in an outerplanar graph is the same as the number of vertices in its largest biconnected component. For this reason finding Hamiltonian cycles and longest cycles in outerplanar graphs may be solved in linear time, in contrast to the NP-completeness of these problems for arbitrary graphs.

Every maximal outerplanar graph satisfies a stronger condition than Hamiltonicity: it is node pancyclic, meaning that for every vertex v and every k in the range from three to the number of vertices in the graph, there is a length-k cycle containing v. A cycle of this length may be found by repeatedly removing a triangle that is connected to the rest of the graph by a single edge, such that the removed vertex is not v, until the outer face of the remaining graph has length k.^[6]

A planar graph is outerplanar if and only if each of its biconnected components is outerplanar.^[4]

Coloring

All loopless outerplanar graphs can be colored using only three colors;^[7] this fact features prominently in the simplified proof of Chvátal's art gallery theorem by Fisk (1978). A 3-coloring may be found in linear time by a greedy coloring algorithm that removes any vertex of degree at most two, colors the remaining graph recursively, and then adds back the removed vertex with a color different from the colors of its two neighbors.

According to Vizing's theorem, the chromatic index of any graph (the minimum number of colors needed to color its edges so that no two adjacent edges have the same color) is either the maximum degree of any vertex of the graph or one plus the maximum degree. However, in an outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a cycle of odd length.^[8] An edge coloring with an optimal number of colors can be found in linear time based on a breadth-first traversal of the weak dual tree.^[7]

Related families of graphs

A cactus graph. The cacti form a subclass of the outerplanar graphs.

Every outerplanar graph is a planar graph. Every outerplanar graph is also a subgraph of a series-parallel graph.^[9] However, not all planar graphs and series-parallel graphs are outerplanar: the complete graph K₄ is planar but neither series-parallel nor outerplanar, and the complete bipartite graph K_2,3 is planar and series-parallel but not outerplanar. Every forest, and every cactus graph is outerplanar.^[10]

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.^[11]

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.^[12]

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 planar graph is the visibility graph of a simple polygon.^[13] 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.^[14]

Other properties

Outerplanar graphs have degeneracy at most two: every subgraph of an outerplanar graph contains a vertex with degree at most two.^[15]

Outerplanar graphs have treewidth at most two, which implies that many graph optimization problems that are NP-complete for arbitrary graphs may be solved in polynomial time by dynamic programming when the input is outerplanar. More generally, k-outerplanar graphs have treewidth O(k).^[16]

Every outerplanar graph can be represented as an intersection graph of axis-aligned rectangles in the plane, so outerplanar graphs have boxicity at most two.^[17]

A graph is outerplanar if and only if its Colin de Verdière graph invariant is at most two. The graphs characterized in a similar way by having Colin de Verdière invariant at most one, three, or four are respectively the linear forests, planar graphs, and linklessly embeddable graphs.

Notes

1. ^ Felsner (2004).
2. ^ Chartrand & Harary (1967); Sysło (1979); Brandstädt, Le & Spinrad (1999), Proposition 7.3.1, p. 117; Felsner (2004).
3. ^ Diestel (2000).
4. ^ ^{a b} Sysło (1979).
5. ^ Chartrand & Harary (1967); Sysło (1979).
6. ^ Li, Corneil & Mendelsohn (2000), Proposition 2.5.
7. ^ ^{a b} Proskurowski & Sysło (1986).
8. ^ Fiorini (1975).
9. ^ Brandstädt, Le & Spinrad (1999), p. 174.
10. ^ Brandstädt, Le & Spinrad (1999), p. 169.
11. ^ Sysło & Proskurowski (1983).
12. ^ Kane & Basu (1976); Sysło (1979).
13. ^ El-Gindy (1985); Lin & Skiena (1995); Brandstädt, Le & Spinrad (1999), Theorem 4.10.3, p. 65.
14. ^ Wessel & Pöschel (1985); Unger (1988).
15. ^ Lick & White (1970).
16. ^ Baker (1994).
17. ^ Scheinerman (1984); Brandstädt, Le & Spinrad (1999), p. 54.

References

• Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM 41 (1): 153–180, doi:10.1145/174644.174650 .
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
• Chartrand, Gary; Harary, Frank (1967), "Planar permutation graphs", Annales de l'institut Henri Poincaré (B) Probabilités et Statistiques 3 (4): 433–438, http://www.numdam.org/item?id=AIHPB_1967__3_4_433_0 .
• Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, 173, Springer-Verlag, p. 107, ISBN 0387989765 .
• El-Gindy, H. (1985), Hierarchical decomposition of polygons with applications, Ph.D. thesis, McGill University . As cited by Brandstädt, Le & Spinrad (1999).
• Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 9783528069728 .
• Fiorini, Stanley (1975), "On the chromatic index of outerplanar graphs", Journal of Combinatorial Theory, Series B 18 (1): 35–38, doi:10.1016/0095-8956(75)90060-X .
• Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B 24: 374, doi:10.1016/0095-8956(78)90059-X .
• Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society 38: 215–219, MR0389672 .
• Kane, Vinay G.; Basu, Sanat K. (1976), "On the depth of a planar graph", Discrete Mathematics 14 (1): 63–67, doi:10.1016/0012-365X(76)90006-6 .
• Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225, doi:10.1016/S0166-218X(99)00163-8 .
• Lick, Don R.; White, Arthur T. (1970), "k-degenerate graphs", Canadian Journal of Mathematics 22: 1082–1096, http://www.smc.math.ca/cjm/v22/p1082 .
• Lin, Yaw-Ling; Skiena, Steven S. (1995), "Complexity aspects of visibility graphs", International Journal of Computational Geometry and Applications 5 (3): 289–312, doi:10.1142/S0218195995000179 .
• Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Efficient vertex-and edge-coloring of outerplanar graphs", SIAM Journal on Algebraic and Discrete Methods 7: 131–136, doi:10.1137/0607016 .
• Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of a Graph, Ph.D. thesis, Princeton University . As cited by Brandstädt, Le & Spinrad (1999).
• Sysło, Maciej M. (1979), "Characterizations of outerplanar graphs", Discrete Mathematics 26 (1): 47–53, doi:10.1016/0012-365X(79)90060-8 .
• Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635 .
• Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832 .
• Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst, Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, 73, B.G. Teubner, pp. 207–210 . As cited by Unger (1988).

External links

• Outerplanar graphs, Information System on Graph Classes and Their Inclusions
• Weisstein, Eric W., "Outplanar Graph" from MathWorld.