Hubbry Logo
Outerplanar graphOuterplanar graphMain
Open search
Outerplanar graph
Community hub
Outerplanar graph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Outerplanar graph
Outerplanar graph
Outerplanar graph
View on Wikipedia
from Wikipedia
A maximal outerplanar graph and its 3-coloring
The complete graph K4 is the smallest planar graph that is not outerplanar.

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants. They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2.

The outerplanar graphs are a subset of the planar graphs, the subgraphs of series–parallel graphs, and the circle graphs. The maximal outerplanar graphs, those to which no more edges can be added while preserving outerplanarity, are also chordal graphs and visibility graphs.

History

[edit]

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 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. Chartrand and Harary also proved an analogue of Kuratowski's theorem for outerplanar graphs, that a graph is outerplanar if and only if it does not contain a subdivision of one of the two graphs K4 or K2,3.

Definition and characterizations

[edit]

An outerplanar graph is an undirected graph that 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][2]

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.

Forbidden graphs

[edit]

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 K4 or the complete bipartite graph K2,3.[3] Alternatively, a graph is outerplanar if and only if it does not contain K4 or K2,3 as a minor, a graph obtained from it by deleting and contracting edges.[4]

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

Colin de Verdière invariant

[edit]

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.

Properties

[edit]

Biconnectivity and Hamiltonicity

[edit]

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.[6] 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.[7]

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

Coloring

[edit]

All loopless outerplanar graphs can be colored using only three colors;[8] 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 a connected outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a cycle of odd length.[9] 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.[8]

Other properties

[edit]

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

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

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

[edit]
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.[13] However, not all planar series–parallel graphs are outerplanar. The complete bipartite graph K2,3 is planar and series–parallel but not outerplanar. On the other hand, the complete graph K4 is planar but neither series–parallel nor outerplanar. Every forest and every cactus graph are outerplanar.[14]

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.[15]

There is a notion of degree of outerplanarity. 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.[16]

An outer-1-planar graph, analogously to 1-planar graphs can be drawn in a disk, with the vertices on the boundary of the disk, and with at most one crossing per edge.

Every maximal outerplanar graph is a chordal graph. Every maximal outerplanar graph is the visibility graph of a simple polygon.[17] 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.[18]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Outerplanar graph

View on Grokipedia
from Grokipedia
An is a graph that can be in the plane without edge crossings such that all vertices lie on the boundary of the outer face. Outerplanar graphs constitute a proper subclass of , distinguished by their stricter constraint that confines all vertices to a single face. They are characterized as the minor-closed family excluding the K4K_4 and the K2,3K_{2,3}. This forbidden minor characterization parallels Kuratowski's theorem for but applies to the more restricted outerplanar setting. Key structural properties include a maximum of 2n−32n - 3 edges for simple connected outerplanar graphs on n≥3n \geq 3 vertices, achieved precisely by maximal outerplanar graphs, which are triangulations of a with non-crossing diagonals. Outerplanar graphs are always 3-colorable and possess degeneracy and at most 2, enabling efficient algorithms for optimization problems on them. Biconnected outerplanar graphs are Hamiltonian, with the unique Hamiltonian cycle coinciding with the outer face boundary.

Definition and Basic Characterizations

Graphical Embedding Definition

An outerplanar graph is a that admits a planar in which all vertices on the boundary of the outer face, which is the unbounded face of the . This ensures that no vertex is strictly interior to the drawing, distinguishing outerplanar graphs as a proper subclass of . In such an outerplanar , the vertices on the boundary of the outer face; for 2-connected outerplanar graphs, this boundary is a simple cycle, with any additional edges serving as non-crossing chords within this cycle. These chords divide the interior of the cycle into regions without introducing crossings or relocating vertices away from the outer boundary, preserving the property that all vertices remain accessible on the exterior. For example, the CnC_n for n≥3n \geq 3 is outerplanar, as its natural places all vertices on the outer face with no interior elements. Adding a single chord between two non-adjacent vertices on this cycle maintains outerplanarity, provided the chord does not cross existing edges, thereby keeping all vertices on the outer face. Maximal outerplanar graphs represent the edge-maximal case within this class, where every face except the outer one is a , achieved by adding as many non-crossing chords as possible without violating the condition. In a maximal outerplanar with n≥3n \geq 3 vertices, the graph has exactly 2n−32n - 3 edges, and the outer face is bounded by a Hamiltonian cycle.

Forbidden Subgraph and Minor Characterizations

A graph is outerplanar if and only if it contains neither K4K_4 nor K2,3K_{2,3} as a minor. This characterization, analogous to Wagner's theorem for planar graphs, establishes outerplanarity as a minor-closed property, where the class of outerplanar graphs is precisely the graphs excluding these two specific forbidden minors. A minor of a graph GG is obtained by a sequence of edge deletions, vertex deletions, and edge contractions (merging adjacent vertices and removing self-loops and multiple edges). If a graph contains K4K_4 or K2,3K_{2,3} as a minor, it implies the presence of a configuration that cannot be embedded with all vertices on the outer face, as these operations preserve non-outerplanarity. Equivalently, outerplanar graphs are those without a subdivision of K4K_4 or K2,3K_{2,3} as a subgraph (topological minor). This subdivision-forbidden characterization is due to the fact that any such subdivision contracts to the forbidden minor, and the minimal obstructions are these two graphs. The K4K_4 on four vertices cannot be outerplanar because any planar embedding forms a tetrahedral structure with triangular faces, forcing at least one vertex to lie inside the outer face to avoid edge crossings. Similarly, the K2,3K_{2,3} with partitions of sizes 2 and 3 cannot be outerplanar; embedding the two degree-3 vertices on the outer face requires the three degree-2 vertices to separate them on the boundary cycle, but the crossing edges between the partitions inevitably create an internal vertex or edge intersection in the outer face. To see the necessity, note that both K4K_4 and K2,3K_{2,3} are non-outerplanar: K4K_4 requires an internal vertex in any , and K2,3K_{2,3} forces edges to cross or enclose a region excluding a vertex from the outer face. For sufficiency, the proof proceeds by induction on the number of vertices; assuming a minimal with a forbidden minor leads to a contradiction, as deleting or contracting an edge in the minor model reduces to a smaller non-outerplanar graph or violates planarity in the outer face.

Advanced Characterizations

Colin de Verdière Invariant

The Colin de Verdière invariant, denoted μ(G), of an undirected graph G with n vertices is defined as the maximum corank (nullity, or of the kernel) of any real symmetric n × n matrix M satisfying three specific conditions tied to the graph's structure. These conditions are: (M1) the off-diagonal entry M_{i,j} (for i ≠ j) is negative if {i,j} is an edge of G and zero otherwise, with no restrictions on the diagonal entries; (M2) M has exactly one negative eigenvalue, of multiplicity one, and all other eigenvalues are non-negative; and (M3) the strong Arnold property, which states that there does not exist a nonzero symmetric n × n matrix X such that X_{i,i} = 0 for all i, X_{i,j} = 0 whenever {i,j} is an edge of G, and M X = 0. A representative example of such a matrix M is one resembling the graph Laplacian, where the diagonal entries M_{i,i} equal the degree of vertex i and the off-diagonal entries are -1 for adjacent vertices (and zero otherwise); however, the invariant μ(G) is computed as the largest possible corank over all qualifying matrices M, not just this Laplacian form. This invariant captures algebraic properties linked to the graph's , with lower values indicating simpler structures amenable to planar-like embeddings. For outerplanar graphs, μ(G) ≤ 2, and this bound is tight, achieving equality for maximal outerplanar graphs such as polygons. In particular, cycle graphs C_n (for n ≥ 3), which are outerplanar, satisfy μ(C_n) = 2, and successively adding non-crossing chords up to a full outerplanar preserves μ(G) = 2. This characterization distinguishes outerplanar graphs spectrally from general planar graphs, which satisfy μ(G) ≤ 3 but can exceed 2. The invariant thus serves as a measure of "planarity-like" complexity, where outerplanar graphs exhibit the lowest nontrivial spectral multiplicity beyond forests (μ ≤ 1).

Treewidth and Partial k-Trees

The treewidth of a graph GG, denoted tw(G)\mathrm{tw}(G), is defined as the minimum width over all tree decompositions of GG, where a tree decomposition consists of a tree TT and a collection of subsets (bags) of vertices of GG assigned to each node of TT such that: (i) every vertex of GG appears in at least one bag, (ii) every edge of GG has both endpoints in some bag, and (iii) for each vertex, the nodes of TT whose bags contain it induce a connected subtree; the width of a decomposition is the size of the largest bag minus one. Outerplanar graphs have treewidth at most 2. For 2-connected outerplanar graphs, the treewidth is exactly 2, as they contain cycles and thus exceed the treewidth of 1 characteristic of forests. This bound arises from constructing a tree decomposition using the dual tree of the triangulated , where each bag corresponds to the three vertices of a triangular face, ensuring bags of size at most 3. Graphs of treewidth at most kk are precisely the partial kk-trees, defined as subgraphs of kk-trees (maximal graphs of treewidth kk, built recursively by starting with a of k+1k+1 vertices and repeatedly adding a vertex adjacent to an existing kk-). Thus, outerplanar graphs are partial 2-trees. They form a proper subclass of the 2-terminal series-parallel graphs, which coincide with all graphs of at most 2 (equivalently, K4K_4-minor-free graphs) and are constructed recursively via series and parallel compositions starting from edges. For example, a , which is outerplanar but acyclic, has 1. In contrast, a maximal (triangulated) outerplanar graph achieves exactly 2. As noted in the discussion of the Colin de Verdière invariant, this spectral parameter μ(G)\mu(G) also satisfies μ(G)≤2\mu(G) \leq 2 for outerplanar graphs and provides an upper bound correlating with .

History

Origins and Early Developments

The term "outerplanar graph" was coined by Gary Chartrand and Frank Harary in their 1967 paper on planar permutation graphs, where they defined it as a connected graph with at least three vertices that admits a planar embedding in which all vertices lie on the boundary of the exterior face. This introduction built directly on foundational studies of planar graphs, which had gained prominence in the mid-20th century through efforts to characterize embeddability and solve related combinatorial problems. Chartrand and Harary provided an initial characterization, proving that a graph is outerplanar it contains no subgraph homeomorphic to K4K_4 or K2,3K_{2,3}, establishing forbidden subdivision conditions as an early tool for identification. The primary motivation for this work arose from efforts to determine the planarity of specific graph constructions, particularly permutation graphs formed by connecting two labeled copies of a base graph according to a of vertices. Outerplanar graphs offered a natural subclass of planar graphs, simplifying analysis in areas such as —where planar embeddings model geographical divisions—and , where restricted embeddings aid in layout optimization for networks with series-parallel structures. These applications highlighted outerplanar graphs' utility in reducing the complexity of broader planar problems, as their embeddings confine all vertices to a single face, facilitating easier verification and manipulation compared to general planar graphs. In the 1970s, research expanded on these foundations, particularly through connections to series-parallel networks, of which outerplanar graphs form a subclass in their undirected form. Later, in , Sysło provided additional characterizations, including the minor-closed property excluding K4K_4 and K2,3K_{2,3}. A key development came from Valdés, E. Tarjan, and Eugene L. Lawler, who in presented methods for recognizing series-parallel digraphs using reduction techniques based on two-terminal series-parallel decompositions. Their approach, initially outlined at the 11th Annual ACM Symposium on Theory of Computing, provided a framework for linear-time processing of such graphs, linking outerplanarity recognition to efficient algorithms. Complementing this, Sandra L. Mitchell formalized a linear-time recognition algorithm for outerplanar and maximal outerplanar graphs in , using degree-based reductions and embedding verification to confirm outerplanarity in O(n+m)O(n + m) time, where nn is the number of vertices and mm the number of edges. These advancements marked the transition from theoretical characterizations to practical computational tools in the late .

Key Contributions and Milestones

In the late 1970s, a significant milestone in the study of outerplanar graphs was the development of linear-time recognition algorithms. Valdes, Tarjan, and Lawler presented an algorithm for recognizing series-parallel graphs, a superclass that includes outerplanar graphs, achieving O(n) time complexity through reduction to a canonical decomposition using ear decomposition techniques. This work laid the foundation for efficient testing of outerplanarity, as outerplanar graphs can be identified as a special case of series-parallel structures with no K2,3K_{2,3} minor. Subsequent refinements extended this to direct recognition of outerplanar graphs; for instance, Chiba, Nishizeki, Abe, and Ozawa introduced a linear-time method for subgraph listing in outerplanar graphs, enabling O(n) recognition by verifying the absence of forbidden minors via edge-searching strategies. The 1980s saw deepening of structural characterizations, particularly through spectral invariants. Heath (1987) developed embedding techniques for outerplanar graphs in small books (with constant pages), supporting fault-tolerant VLSI layouts allowing implementation in O(n) area with bounded wire lengths. While early formulations of graph invariants explored connections to planarity, the Colin de Verdière invariant μ(G), introduced in 1990 but building on 1980s spectral ideas, provided a precise characterization: a graph is outerplanar if and only if μ(G) ≤ 2. This invariant, defined as the maximum corank of certain symmetric matrices associated with the graph, highlighted the low complexity of outerplanar embeddings and influenced applications in quantum and algebraic graph theory. Related work in the 1980s, such as efficient coloring algorithms, confirmed and extended the foundational result that outerplanar graphs are 3-colorable, with a linear-time vertex-coloring algorithm exploiting the dual tree structure to achieve optimal coloring in O(n) time. In the 1990s, research on upward outerplanar drawings advanced visibility representations; for example, Hutton and Lubiw () developed algorithms for single-source acyclic outerplanar digraphs that produced straight-line upward planar embeddings in linear time, enhancing layered graph layouts for software visualization. In terms of , outerplanar graphs were established to have treewidth at most 2, a bound that underscores their partial 2-tree nature. Although early bounds appeared in the , Dujmović, Morin, and Wood in the early refined related separator theorems for layered treewidth, showing that outerplanar graphs admit decompositions into graphs of treewidth 2 and bounded layer number, facilitating approximation algorithms for optimization problems. Post-2000 developments connected outerplanar graphs to practical applications in and VLSI design. In the 2020s, minor refinements emerged in quantum graph algorithms for outerplanar subclasses. A 2024 result demonstrated that outerplanar graphs satisfy conditions for efficient computation of the quantum using stabilizer formalism, enabling polynomial-time quantum algorithms for detection without major breakthroughs in broader graph problems. As a 1970s milestone, early Hamiltonicity results for outerplanar graphs were established via dynamic programming on dual trees, paving the way for these advancements.

Structural Properties

Biconnectivity and Connectivity

Outerplanar graphs have vertex connectivity at most 2, as they form a subclass of graphs with 2, and such graphs cannot be 3-vertex-connected. The biconnected components of an outerplanar graph are themselves 2-connected outerplanar graphs, preserving the properties of the original graph. In a biconnected outerplanar graph, there are no bridges, consistent with the definition of biconnectivity implying 2-edge-connectivity. Furthermore, every 2-connected outerplanar graph admits an open ear decomposition that begins with a cycle and proceeds by adding paths (ears) between existing vertices. This decomposition highlights the series-parallel structure inherent to outerplanar graphs and facilitates algorithmic applications such as recognition and optimization. Trees provide a simple example of 1-connected outerplanar graphs, as they can be embedded with all vertices on the outer face and no cycles. Adding chords between non-adjacent vertices on this embedding can yield a 2-connected outerplanar graph, such as a cycle itself. Note that 2-connected outerplanar graphs are precisely the Hamiltonian ones among this family.

Hamiltonicity and Cycles

Every 2-connected outerplanar graph is Hamiltonian, and the Hamiltonian cycle is precisely the cycle bounding the outer face in the outerplanar embedding. This follows from the structural characterization of such graphs, where the embedding places all vertices on the outer face boundary, forming a cycle that includes every vertex, with all other edges as non-crossing chords inside this cycle. Biconnected outerplanar graphs possess a unique Hamiltonian cycle, which coincides with the outer boundary cycle. Any other potential cycle would either cross edges in the embedding or fail to include all vertices, due to the non-crossing chord structure that prevents alternative spanning cycles without violating planarity or the outerplanar property. Maximal outerplanar graphs, which are triangulated outerplanar graphs with every internal face a triangle, are 1-Hamiltonian: the deletion of any single vertex leaves a graph that remains Hamiltonian. This property arises from the recursive construction of maximal outerplanar graphs, where removing a vertex (typically of degree 2 in the construction) yields another maximal outerplanar graph on the remaining vertices, preserving the Hamiltonian outer boundary cycle. A representative example is a triangulated outerplanar graph on n≥3n \geq 3 vertices, embedded as a convex nn-gon with non-crossing diagonals that triangulate the interior. The Hamiltonian cycle follows the boundary of the nn-gon, while the internal diagonals connect non-adjacent boundary vertices to form n−2n-2 triangular faces inside.

Coloring and Chromatic Properties

Vertex Coloring

Outerplanar graphs have a chromatic number of at most 3, meaning they are 3-colorable. This can be proved constructively by an inductive that first colors the vertices of the outer cycle using at most 3 colors, as the cycle requires either 2 colors (if even length) or 3 colors (if odd length), and then colors internal vertices sequentially, assigning to each a color different from its at most two previously colored neighbors on the boundary or adjacent internals. Maximal outerplanar graphs, which are triangulations with all vertices on the outer face, achieve exactly chromatic number 3, as they contain triangles (requiring at least 3 colors) while remaining 3-colorable by the general result. A , applied in an order that respects the outerplanar embedding (such as processing vertices from the outer cycle inward), uses at most 3 colors and runs in O(n time, where n is the number of vertices, due to the 2-degeneracy of outerplanar graphs (every subgraph has a vertex of degree at most 2). A special case consists of bipartite outerplanar graphs, which lack odd cycles and thus have chromatic number 2; examples include even cycles embedded as the outer boundary with tree-like attachments.

Edge Coloring

The edge chromatic number of an outerplanar graph GG, denoted χ′(G)\chi'(G), is equal to its maximum degree Δ(G)\Delta(G). Outerplanar graphs belong to the class of series-parallel graphs and thus are Class 1 graphs, admitting a proper with exactly Δ(G)\Delta(G) colors. This contrasts with some simple graphs that require Δ(G)+1\Delta(G) + 1 colors due to structural features like certain odd cycles or high connectivity, but the outerplanar and absence of K4K_4 or K2,3K_{2,3} minors ensure no such overcoloring is needed. A representative example is the star graph K1,nK_{1,n}, which is outerplanar with Δ(K1,n)=n\Delta(K_{1,n}) = n and χ′(K1,n)=n\chi'(K_{1,n}) = n, as the central vertex's incident edges must all receive distinct colors. Note that outerplanar graphs, including maximal ones, can exhibit arbitrarily high degrees, yet remain Δ\Delta-edge-colorable. Efficient algorithms exploit the outerplanar structure, such as the associated dual or embedding, to achieve a Δ\Delta-edge-coloring via greedy methods that color edges sequentially around faces or along the outer boundary. These algorithms run in linear time relative to the number of vertices and edges, which is O(n)O(n) for outerplanar graphs.

Algorithmic Aspects

Recognition and Testing

An efficient algorithm for recognizing outerplanar graphs runs in linear time, O(n), where n is the number of vertices, and was originally developed by Sandra L. Mitchell in 1979. This method uses graph traversal techniques to verify outerplanarity. Since outerplanar graphs are a subclass of series-parallel graphs, recognition algorithms for series-parallel graphs, such as the one by Valdes, Tarjan, and Lawler (1982) using PQ-trees, can also be adapted to identify structures underpinning outerplanar graphs. This involves constructing a decomposition that verifies the graph's compatibility with outerplanar embeddings by successively reducing subgraphs while maintaining the representation of permissible vertex orders on the outer face. Alternative linear-time approaches employ open ear decompositions, where the graph is iteratively broken down into ears (paths attached at endpoints to the current structure), ensuring no internal chords violate outerplanarity; such decompositions can be computed via depth-first search in O(n) time and certified for outerplanarity by checking that each ear adheres to the outer boundary constraint. One standard procedure begins with an optional planarity test, such as the Boyer-Myrvold algorithm running in O(n) time, to filter non-planar inputs, followed by computing a combinatorial embedding and verifying that all vertices lie on the outer face using a depth-first search (DFS) or breadth-first search (BFS) traversal of the dual graph to confirm no internal faces enclose vertices exclusively. A common practical method adds an auxiliary vertex connected to all original vertices, tests the resulting graph for planarity (e.g., using left-right planarity test), and verifies the embedding if planar. If the graph passes planarity, the verification step examines the embedding's facial cycles, ensuring the unbounded face incidents every vertex, which can be done in O(n) time by iterating over the adjacency lists in the embedding representation. The left-right planarity test—originally for general planarity—can be adapted for outerplanarity by this auxiliary vertex approach, achievable in O(n) time. Outerplanar graphs are precisely those without K_4 or K_{2,3} as minors, and testing for these forbidden minors can be performed efficiently in O(n) time using decomposition techniques that contract and delete edges while tracking potential minor formations via bounded search trees tailored to these small forbidden configurations. This minor-checking approach leverages the fixed size of the forbidden subgraphs, allowing a constant-time kernel per vertex through parallelizable contractions in the decomposition process. More recent developments include parallel algorithms for recognition on the PRAM model, achieving O(log n) time using O(n α(n)/log n) processors, where α(n) is the inverse , by parallelizing the ear or PQ-tree reductions across concurrent threads while synchronizing boundary updates.

Optimization Algorithms

Outerplanar graphs possess a treewidth of at most 2, which enables the application of dynamic programming frameworks on tree to solve a wide range of optimization problems in linear time. This bounded exploits the series-parallel structure inherent to outerplanar graphs, allowing subproblems to be computed efficiently along the decomposition bags, each of size at most 3. Seminal results demonstrate that problems like the traveling salesman problem (TSP) and maximum independent set, which are NP-hard on general graphs, can be resolved exactly in O(n) time using such dynamic programming approaches tailored to the treewidth bound. For the maximum independent set problem specifically, a linear-time uses dynamic programming along the outerplanar or , computing the maximum by considering states for of bag vertices in constant time per bag. Variants of the Steiner and minimum spanning problems also admit linear-time solutions on outerplanar graphs, leveraging their partial 2-tree nature. For the Steiner , a dynamic programming constructs the minimum-weight connecting a given of terminals by processing the graph's series-parallel , achieving O(n time . Minimum spanning follow from standard linear-time methods like , adapted to the for O(n performance without sorting overhead in sparse graphs. Straight-line drawings of outerplanar graphs can be computed in O(n time, placing all vertices on a circle to form a convex outer face while ensuring no crossings. Algorithms achieve this by incrementally adding vertices to the boundary in embedding order, assigning coordinates that maintain planarity and straight edges, resulting in O(d n^{1.48}) area grid drawings, where d is the maximum degree. In general, optimization problems that are NP-hard on planar graphs, such as the minimum , become solvable in polynomial time—and often linear time—on outerplanar graphs due to the bounded . For , a linear-time dynamic programming computes a minimum set by processing along the outer cycle and internal faces, selecting vertices to cover neighbors efficiently in O(n steps. This extends to other connectivity and covering problems, where the exact solution is found via constant-time state transitions on the .

Subclasses and Superclasses

Outerplanar graphs are a proper subclass of planar graphs, which are precisely the graphs with Colin de Verdière invariant μ(G)≤3\mu(G) \leq 3. Within the class of outerplanar graphs, key subclasses include maximal outerplanar graphs, which are triangulated outerplanar graphs in which no additional edge can be added without violating outerplanarity, resulting in every bounded face being a triangle. Another subclass consists of caterpillar trees, defined as trees in which all vertices lie within distance 1 of a central path; these are outerplanar as a special case of trees. Forests, the acyclic graphs, form a further subclass, since every tree admits an outerplanar embedding with all vertices on the outer face. Superclasses of outerplanar graphs include the planar graphs and the series-parallel graphs, the latter being the partial 2-trees or 2-terminal series-parallel networks that contain all outerplanar graphs as a proper subclass. Outerplanar graphs have at most 2, while planar graphs admit unbounded . Representative examples illustrate these relations: cycles are the minimal 2-connected outerplanar graphs, as they are biconnected and any proper subgraph is not; trees, in contrast, represent the 1-connected subclass of outerplanar graphs.

Comparisons with Other Planar Graphs

Outerplanar graphs form a strict subclass of s, characterized by the requirement that all vertices lie on the boundary of a single outer face in any , precluding the presence of internal vertices that can exist in general . This structural constraint simplifies various computational problems; for instance, while both classes admit linear-time recognition algorithms, the algorithm for outerplanar graphs leverages the outer face property more directly, often using degree-two vertex elimination or edge-coloring techniques. In contrast, recognition, though also achievable in linear time via methods like Hopcroft and Tarjan's , requires handling more complex structures. Compared to series-parallel graphs, which are precisely the K_4-minor-free graphs, outerplanar graphs represent a proper subclass defined by the additional exclusion of K_{2,3} minors. All outerplanar graphs are series-parallel and can be embedded as outerplanar series-parallel networks, but the converse fails: for example, K_{2,3} is series-parallel yet non-outerplanar due to its inability to place all vertices on a single outer face without crossings. This distinction arises because series-parallel graphs allow embeddings with internal structures that violate the outerplanarity condition, such as chords creating separated inner faces. Outerplanar graphs also differ from apex graphs, which are obtained by adding a single vertex (the apex) adjacent to any of vertices in a and thus may not be planar themselves. While both outerplanar and general planar graphs forbid K_5 and K_{3,3} minors, apex-outerplanar graphs—those becoming outerplanar upon apex removal—extend outerplanarity to a minor-closed family with forbidden minors including K_4, K_{2,3}, and certain apex-augmented configurations. In applications, outerplanar graphs find use in VLSI design for efficient linear-area layouts due to their separator properties, whereas general planar graphs are more commonly applied in cartographic modeling of maps and terrains where internal vertices represent enclosed regions. Key property differences further highlight these contrasts: outerplanar graphs are 3-colorable, a tighter bound than the 4-colorability of planar graphs established by the four-color theorem. Regarding Hamiltonicity, every biconnected outerplanar graph admits a Hamiltonian cycle along its outer face, solvable in polynomial time, whereas determining Hamiltonicity in general planar graphs is NP-complete. Recent studies on hybrid classes, such as metrizable graphs, reveal that those with at least 11 vertices are precisely outerplanar plus one vertex, bridging outerplanarity with broader metric structures in graph theory.

References

  1. https://mathworld.wolfram.com/OuterplanarGraph.html
  2. https://www.infosun.fim.uni-passau.de/~chris/down/Outer1Planar.pdf
  3. https://www.sciencedirect.com/science/article/pii/0012365X79900608
  4. https://dwest.web.illinois.edu/pubs/outerpl.pdf
  5. https://www.ams.org/journals/notices/202502/rnoti-p172.pdf
  6. https://arxiv.org/pdf/2107.02796
  7. https://arxiv.org/pdf/2209.14476
  8. https://arxiv.org/pdf/1801.08448
  9. https://www.numdam.org/article/AIHPB_1967__3_4_433_0.pdf
  10. https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch4.pdf
  11. https://www.whitman.edu/Documents/Academics/Mathematics/2019/Olds-Guichard.pdf
  12. http://www-fourier.univ-grenoble-alpes.fr/~ycolver/All-Articles/90a.pdf
  13. https://ir.cwi.nl/pub/1257/1257D.pdf
  14. https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3417/3402
  15. https://web.mat.upc.edu/anna.de.mier/paperots/OP6.pdf
  16. https://www.numdam.org/item/AIHPB_1967__3_4_433_0.pdf
  17. https://www.sciencedirect.com/science/article/pii/0020019079900759
  18. https://epubs.siam.org/doi/10.1137/0211023
  19. https://epubs.siam.org/doi/10.1137/0214017
  20. https://epubs.siam.org/doi/10.1137/0608018
  21. https://doi.org/10.1007/BFb0000194
  22. https://www.cs.uoregon.edu/Reports/TR-1982-005.pdf
  23. https://epubs.siam.org/doi/10.1137/S0097539792235906
  24. https://ics-archive.science.uu.nl/research/techreps/repo/CS-1991/1991-47.pdf
  25. https://ijmcr.in/index.php/ijmcr/article/download/797/636/
  26. https://arxiv.org/pdf/2508.10077
  27. https://scholarworks.smith.edu/cgi/viewcontent.cgi?article=1312&context=csc_facpubs
  28. https://oc.g-scop.grenoble-inp.fr/esperet/teaching/gsd-2021-10-13.pdf
  29. https://people.computing.clemson.edu/~goddard/handouts/math9540/SUMMARY/AA.pdf
  30. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v6i1r42
  31. https://epubs.siam.org/doi/10.1137/0607016
  32. https://peter.myweb.cs.uwindsor.ca/meta-index/G10-Generialized-SP-%28REVISED%29.pdf
  33. https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/planarity.pdf
  34. https://www.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf
  35. https://kam.mff.cuni.cz/~fiala/tw.pdf
  36. https://scispace.com/pdf/a-simple-near-optimal-parallel-algorithm-for-recognizing-2ofb2b1aai.pdf
  37. https://www.cs.bme.hu/~dmarx/papers/krakow2015-slides5.pdf
  38. https://www.irif.fr/~habib/Documents/treewidth1.pdf
  39. https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230130202
  40. http://www.scs.carleton.ca/~maheshwa/papers/em-outerplanar.pdf
  41. https://www.sciencedirect.com/science/article/pii/S0166218X06004331
  42. https://www.sciencedirect.com/science/article/pii/S0166218X15003108
  43. https://page.math.tu-berlin.de/~felsner/Paper/ppg-rev.pdf
  44. https://repub.eur.nl/pub/23560/EI2011-16.pdf
  45. https://inria.hal.science/inria-00070220v1/document
  46. https://arxiv.org/pdf/2405.03278
  47. https://web.mat.upc.edu/anna.de.mier/paperots/cycles_def2.pdf
  48. https://drops.dagstuhl.de/storage/00lipics/lipics-vol320-gd2024/LIPIcs.GD.2024.14/LIPIcs.GD.2024.14.pdf
  49. https://www.graphclasses.org/classes/gc_110.html
  50. https://link.springer.com/chapter/10.1007/3-540-17218-1_57
  51. https://www.lirmm.fr/~sau/talks/UFC22-Ignasi.pdf
  52. https://people.csail.mit.edu/cel/resume/papers/AreaEffGraphVLSI.pdf
  53. https://link.springer.com/article/10.1007/s00373-015-1611-9
  54. https://arxiv.org/pdf/1201.0066
  55. https://arxiv.org/abs/2311.09364
Add your contribution
Related Hubs
User Avatar
No comments yet.