Fact-checked by Grok 2 weeks ago

Outerplanar graph

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

Definition and Basic Characterizations

Graphical Embedding Definition

An outerplanar graph is a planar graph that admits a planar embedding in which all vertices lie on the boundary of the outer face, which is the unbounded face of the embedding. This embedding ensures that no vertex is strictly interior to the drawing, distinguishing outerplanar graphs as a proper subclass of planar graphs. In such an outerplanar embedding, the vertices lie 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.^[6] 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 cycle graph C_n for n \geq 3 is outerplanar, as its natural embedding 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.^[7] Maximal outerplanar graphs represent the edge-maximal case within this class, where every face except the outer one is a triangle, achieved by adding as many non-crossing chords as possible without violating the embedding condition. In a maximal outerplanar embedding with n \geq 3 vertices, the graph has exactly $2n - 3 edges, and the outer face is bounded by a Hamiltonian cycle.^[8]

Forbidden Subgraph and Minor Characterizations

A graph is outerplanar if and only if it contains neither K_4 nor K_{2,3} as a minor.^[9] 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.^[10] A minor of a graph G 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 K_4 or K_{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.^[11] Equivalently, outerplanar graphs are those without a subdivision of K_4 or K_{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.^[9] The complete graph K_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.^[11] Similarly, the bipartite graph K_{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.^[11] To see the necessity, note that both K_4 and K_{2,3} are non-outerplanar: K_4 requires an internal vertex in any embedding, and K_{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 counterexample 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.^[9]^[11]

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 dimension 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.^[12]^[13] 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 spectral invariant captures algebraic properties linked to the graph's topology, with lower values indicating simpler structures amenable to planar-like embeddings.^[13] For outerplanar graphs, μ(G) ≤ 2, and this bound is tight, achieving equality for maximal outerplanar graphs such as triangulated 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 triangulation 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).^[12]^[13]

Treewidth and Partial k-Trees

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

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.^[16] 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 if and only if it contains no subgraph homeomorphic to K_4 or K_{2,3}, establishing forbidden subdivision conditions as an early tool for identification.^[16] 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 permutation of vertices.^[16] Outerplanar graphs offered a natural subclass of planar graphs, simplifying analysis in areas such as map coloring—where planar embeddings model geographical divisions—and circuit design, 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 1979, Sysło provided additional characterizations, including the minor-closed property excluding K_4 and K_{2,3}.^[3] A key development came from Jacobo Valdés, Robert E. Tarjan, and Eugene L. Lawler, who in 1979 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 decomposition algorithms. Complementing this, Sandra L. Mitchell formalized a linear-time recognition algorithm for outerplanar and maximal outerplanar graphs in 1979, using degree-based reductions and embedding verification to confirm outerplanarity in O(n + m) time, where n is the number of vertices and m the number of edges.^[17] These advancements marked the transition from theoretical characterizations to practical computational tools in the late 1970s.

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.^[18] 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 K_{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.^[19] 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.^[20] 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.^[21] 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.^[22] In the 1990s, research on upward outerplanar drawings advanced visibility representations; for example, Hutton and Lubiw (1996) 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.^[23] In terms of treewidth, 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 1980s, Dujmović, Morin, and Wood in the early 2000s 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 graph drawing 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 automorphism group using stabilizer formalism, enabling polynomial-time quantum algorithms for symmetry 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 treewidth 2, and such graphs cannot be 3-vertex-connected. The biconnected components of an outerplanar graph are themselves 2-connected outerplanar graphs, preserving the embedding properties of the original graph.^[24] 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.^[25] 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.^[26] Note that 2-connected outerplanar graphs are precisely the Hamiltonian ones among this family.^[26]

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.^[27] A representative example is a triangulated outerplanar graph on n \geq 3 vertices, embedded as a convex n-gon with non-crossing diagonals that triangulate the interior. The Hamiltonian cycle follows the boundary of the n-gon, while the internal diagonals connect non-adjacent boundary vertices to form n-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 algorithm 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 greedy coloring algorithm, 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).^[28] 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.^[29]

Edge Coloring

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

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.^[17] 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.^[18] 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.^[32] 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.^[33] 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.^[34] 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.^[35] 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 Ackermann function, by parallelizing the ear decomposition or PQ-tree reductions across concurrent threads while synchronizing boundary updates.^[36]

Optimization Algorithms

Outerplanar graphs possess a treewidth of at most 2, which enables the application of dynamic programming frameworks on tree decompositions to solve a wide range of optimization problems in linear time.^[37] This bounded treewidth 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.^[38] 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 algorithm uses dynamic programming along the outerplanar embedding or tree decomposition, computing the maximum cardinality by considering states for subsets of bag vertices in constant time per bag. Variants of the Steiner tree and minimum spanning tree problems also admit linear-time solutions on outerplanar graphs, leveraging their partial 2-tree nature. For the Steiner tree, a dynamic programming algorithm constructs the minimum-weight tree connecting a given subset of terminals by processing the graph's series-parallel decomposition, achieving O(n time complexity.^[39] Minimum spanning trees follow from standard linear-time methods like Kruskal's algorithm, adapted to the embedding for O(n performance without sorting overhead in sparse graphs.^[40] 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.^[41] In general, optimization problems that are NP-hard on planar graphs, such as the minimum dominating set, become solvable in polynomial time—and often linear time—on outerplanar graphs due to the bounded treewidth. For dominating set, a linear-time dynamic programming algorithm computes a minimum set by processing along the outer cycle and internal faces, selecting vertices to cover neighbors efficiently in O(n steps.^[42] This extends to other connectivity and covering problems, where the exact solution is found via constant-time state transitions on the tree decomposition.

Subclasses and Superclasses

Outerplanar graphs are a proper subclass of planar graphs, which are precisely the graphs with Colin de Verdière invariant \mu(G) \leq 3.^[43] 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.^[44] 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.^[45] Forests, the acyclic graphs, form a further subclass, since every tree admits an outerplanar embedding with all vertices on the outer face.^[46] 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.^[47] Outerplanar graphs have treewidth at most 2, while planar graphs admit unbounded treewidth.^[48] 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.^[49]

Comparisons with Other Planar Graphs

Outerplanar graphs form a strict subclass of planar graphs, characterized by the requirement that all vertices lie on the boundary of a single outer face in any planar embedding, precluding the presence of internal vertices that can exist in general planar graphs. 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, planar graph recognition, though also achievable in linear time via methods like Hopcroft and Tarjan's planarity testing, requires handling more complex embedding structures.^[50] 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.^[51] Outerplanar graphs also differ from apex graphs, which are obtained by adding a single vertex (the apex) adjacent to any subset of vertices in a planar graph 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.^[52]^[53]^[54] 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.^[55]

References

[1]
Outerplanar Graph -- from Wolfram MathWorld
An outerplanar graph is a graph that can be embedded in the plane such that all vertices lie on the outer face. Outerplanar graphs are planar and, by their ...
[2]
[PDF] Outer 1-Planar Graphs - Infosun
Apr 22, 2015 · This implies several structural properties. Every outerplanar graph has at least two vertices of degree two, which is utilized in a linear-time ...
[3]
Characterizations of outerplanar graphs - ScienceDirect.com
The paper presents several characterizations of outerplanar graphs, some of them are counterparts of the well-known characterizations of planar graphs.
[4]
[PDF] Vertex Degrees in Outerplanar Graphs - Douglas West's
For an outerplanar graph on n vertices, we determine the maximum number of ... Since β5(n) is roughly 2n/3, we should be able to augment the sum of the ...
[5]
Treewidth? - American Mathematical Society
The tree of triangles of an outerplanar graph has width two. Figure 1. An outerplanar graph (black) and a tree of triangles forming a tree-decomposition ...
[6]
[PDF] Double domination in maximal outerplanar graphs - arXiv
Jul 6, 2021 · A maximal outerplanar graph G can be embedded in the plane such that the boundary of the outer face is a Hamiltonian cycle and each inner face ...
[7]
[PDF] On the general position numbers of maximal outerplanar graphs
Sep 29, 2022 · A plane graph G is outerplanar if it has an embedding in the plane such that all vertices belong to the boundary of its outer face (the ...
[8]
[PDF] Symmetry breaking in planar and maximal outerplanar graphs - arXiv
Jan 25, 2018 · Every maximal outerplanar graph with n vertices has exactly 2n − 3 edges, and every bounded face of a maximal outerplanar graph is a triangle.
[9]
[PDF] Planar Permutation Graphs - Numdam
graph is considered outerplanar if all its components are. Of course every outerplanar nonseparable graph is hamiltonian. It is easy to see that all graphs with ...
[10]
[PDF] Planar Graphs
Show that a graph is outerplanar if and only if it contains neither K4 nor K2,3 as a minor. 24. Show that a 2-connected plane graph is bipartite if and only ...
[11]
[PDF] FORBIDDEN GRAPH MINORS Contents 1. Introduction 2 2 ...
Since planarity is minor closed, it is sufficient to show that a minor of an outerplanar graph will have all vertices incident to one face. It is clear that.
[12]
[PDF] Sur un Nouvel Invariant des Graphes et un Critere de Planariti!
Sur un Nouvel Invariant des Graphes et ... Un probleme bien nature1 et rtsolu par. Kuratowski [KI] est de trouver une caracterisation des graphes planaires.
[13]
[PDF] the colin de verdiere graph parameter
Moreover, planarity of graphs can be characterized by this invariant: µ( G) :S 3 if and only if G is planar. More recently it was shown in [20] that p.( G) :::; ...
[14]
[PDF] A Tourist Guide through Treewidth - Acta Cybernetica
Both Lagergren and Arnborg [91] and Bodlaender and Kloks [31,82] give such an algorithm, using an involved application of the technique, discussed in section 4.
[15]
[PDF] The Tutte polynomial characterizes simple outerplanar graphs
Generally speaking, classes of graphs defined in terms of forbidden minors are not characterized by the Tutte polynomial. For example there are planar ...
[16]
[PDF] Planar Permutation Graphs - Numdam
Gary CHARTRAND and Frank HARARY. INTRODUCTION. Ann. Inst. Henri Poincaré,. Vol. III, n° 4, 1967, p. 438. Section B : Calcul des Probabilités et Statistique ...Missing: 1969 | Show results with:1969
[17]
Linear algorithms to recognize outerplanar and maximal outerplanar ...
Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Author links open overlay panel. Sandra L. Mitchell. Show more. Add to Mendeley.
[18]
The Recognition of Series Parallel Digraphs - SIAM.org
The Recognition of Series Parallel Digraphs. Authors: Jacobo Valdes, Robert E. Tarjan, and Eugene L. LawlerAuthors Info & Affiliations. https://doi.org ...
[19]
Arboricity and Subgraph Listing Algorithms - SIAM.org
In this paper we introduce a new simple strategy into edge-searching of a graph, which is useful to the various subgraph listing problems.
[20]
[PDF] efficient vertex- and edge-coloring of outerplanar graphs
subclass of series-parallel graphs, restricted to a outerplanar graphs. A ... subgraph of an outerplanar graph is outerplanar. applying the Szekeres ...<|control11|><|separator|>
[21]
Upward Planar Drawing of Single-Source Acyclic Digraphs - SIAM.org
This paper presents an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a ...
[22]
Embedding Outerplanar Graphs in Small Books - SIAM.org
The significance for VLSI design is that any outerplanar graph can be implemented in small area in a fault-tolerant fashion. MSC codes. 05C45 · 68Q35 · 94C15 ...
[23]
[PDF] Embedding k-Outerplanar Graphs into `1 - People @EECS
The first main idea in the paper is to identify a subclass of 2-outerplanar graphs that are easier to embed, namely Halin graphs. Informally, a “Halin graph” is ...
[24]
[PDF] Parallel Open Ear Decomposition with Applications to Graph ...
Jan 20, 1992 · In this section we describe an algorithm for testing three-vertex connectivity (or tri- connectivity) of a biconnected graph using an open ear ...
[25]
[PDF] An Ear Decomposition of a Graph
Aug 30, 2024 · Also the distributed ear decomposition algorithm can be used to test if a biconnected network is outerplanar using O(n) messages in O(n) time, ...
[26]
https://arxiv.org/pdf/2508.10077
[27]
[PDF] Hamiltonian Paths and Cycles in Planar Graphs - Computer Science
Theorem 3. The number of Hamiltonian paths in any outerplanar graph with n vertices is O(nαn). Furthermore, there exists a maximal outerplanar graph.
[28]
[PDF] Graph Theory (III)
Jan 18, 2020 · A 1-hamiltonian graph which is not Hamilton-connected (Exercise 18.1 ... maximal outerplanar, 293 outerplanar, 258 plane graph, 244.
[29]
[PDF] 1 Coloring planar graphs
Oct 13, 2021 · Since outerplanar graphs form a hereditary family, this shows that outerpla- ... Every outerplanar graph is 3-colorable. In the Art gallery ...Missing: original | Show results with:original
[30]
[PDF] Generalized Colorings of Planar Graphs
(Borodin) A planar graph has a proper 5-coloring such that there is no 2-colored cycle. A3 Two-Color Theorems. We noted that outerplanar graphs are 3-colorable.
[31]
List Edge-Colorings of Series-Parallel Graphs
Sep 17, 1999 · List Edge-Colorings of Series-Parallel Graphs · Martin Juvan · Bojan Mohar · Robin Thomas.
[32]
Efficient Vertex- and Edge-Coloring of Outerplanar Graphs - SIAM.org
We also establish algorithmically the value of the chromatic index of an outerplanar graph. Our algorithms are based on systematic coloring of elements ( ...<|control11|><|separator|>
[33]
[PDF] A linear-time certifying algorithm for recognizing generalized series ...
In this paper, we study the recognition of three classes of graphs: series- parallel graphs, outerplanar graphs and generalized series-parallel graphs. All of ...
[34]
[PDF] Planarity Testing and Embedding - Brown CS
If all the vertices are incident to the outer face, the planar drawing is called outerplanar and the graph admitting it is an outerplanar graph. Given a planar ...
[35]
[PDF] Graph minors, decompositions and algorithms
Apr 15, 2024 · A graph G is outerplanar if and only if none of K4 and K2,3 is its minor. Proof. Firstly, K4 and K2,3 are two minor-minimal non-outerplanar ...
[36]
[PDF] The Left-Right Planarity Test
Apr 14, 2011 · If the root is incident to the outer face, the lowest vertex of their union is contained in the outer of the two cycles. of one cycle that is ...
[37]
[PDF] a-simple-near-optimal-parallel-algorithm-for-recognizing ... - SciSpace
In this paper, we propose a simple near optimal parallel algorithm for recognizing whether a given graph G is outerplanar in O(log n) time using O(na(l, n)/log ...Missing: 2020s | Show results with:2020s
[38]
[PDF] Treewidth
A planar graph is outerplanar if it has a planar embedding where every vertex is on the infinite face. Fact. Every outerplanar graph has treewidth at most 2. ⇒ ...
[39]
[PDF] Treewidth I
Treewidth is the least integer k such that a graph is a partial k-tree, or the most general search for a tree structure inside a graph.
[40]
Approximation algorithms for NP-complete problems on planar graphs
For general planar graphs, if the problem is a maximization problem, such as maximum independent set, this technique gives for each k a linear time algorithm ...<|separator|>
[41]
Baker's Approximation Scheme for k-Outerplanar Graphs
Oct 6, 2024 · Approximation Algorithms: These algorithms yield solutions that are close to optimal within a guaranteed ratio, often expressed as OPTA≤(1+ ...
[42]
Steiner trees, partial 2–trees, and minimum IFI networks - Wald - 1983
Minimum isolated failure immune networks are shown to be 2–trees. Further, subgraphs of 2-trees are shown to be exactly those graphs which contain no ...<|control11|><|separator|>
[43]
I/O-Optimal Algorithms for Outerplanar Graphs Anil Maheshwari ...
I/O-Optimal Algorithms for Outerplanar. Graphs. Anil Maheshwari. Carleton ... We present linear-I/O algorithms for fundamental graph problems on em- bedded ...
[44]
Area-efficient planar straight-line drawings of outerplanar graphs
We show that an outerplanar graph G with degree d admits a planar straight-line grid drawing with area O ( dn 1.48 ) in O ( n ) time.
[45]
On dominating sets of maximal outerplanar and planar graphs
Jan 10, 2016 · A set D ⊆ V ( G ) of a graph G is a dominating set if every vertex v ∈ V ( G ) is either in D or adjacent to a vertex in D . The domination ...Missing: remain | Show results with:remain<|control11|><|separator|>
[46]
[PDF] Posets and Planar Graphs - TU Berlin
This characterization of outerplanar graphs is closely related to the celebrated result of W. Schnyder [16] who proved that a graph is planar if and only if its.
[47]
[PDF] Maximal outerplanar graphs as chordal graphs, path-neighborhood ...
May 2, 2011 · An outerplanar graph is a planar graph that has a plane embedding such that all vertices lie on the outer cycle. A maximal outerplanar graph is ...
[48]
[PDF] Pathwidth of outerplanar graphs - Hal-Inria
May 19, 2006 · The caterpillars are the only trees of pathwidth 1: every caterpillar has surely pathwidth 1, and if a tree T is not a caterpillar, then it ...
[49]
[PDF] arXiv:2405.03278v1 [cs.DS] 6 May 2024
May 6, 2024 · Outerplanar graphs are planar graphs that can be embedded in the plane so that edges do not intersect each other and additionally, each vertex ...
[50]
[PDF] On the maximum number of cycles in outerplanar and series-parallel ...
It is well known that outerplanar graphs are series-parallel, but not conversely.Missing: subclass | Show results with:subclass
[51]
[PDF] Bounding the Treewidth of Outer k-Planar Graphs via Triangulations
Abstract. The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in ...
[52]
outerplanar - Graph Classes
Definition: A graph is outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face.
[53]
Recognizing outerplanar graphs in linear time - SpringerLink
This paper describes a linear time algorithm to determine whether an arbitrary graph is outerplanar. The algorithm uses an edge coloring technique and ...
[54]
[PDF] Graph modification problems with forbidden minors - LIRMM
Nov 4, 2022 · If C = series-parallel graphs, then C = exc(K4). If C = outerplanar graphs, then C = exc(K4,K2,3). If C = planar graphs, then C = exc(K5,K3,3).<|separator|>
[55]
[PDF] Area-efficient graph layouts (for VLSI) - People | MIT CSAIL
Aug 13, 1980 · Outerplanar graphs are triangulations of polygons, perhaps with some edges removed. The author has been able to prove a 1-separator theorem for ...
[56]
Excluded-Minor Characterization of Apex-Outerplanar Graphs
Jul 28, 2015 · A graph is outerplanar if it can be embedded in the plane (with no edges crossing) with all vertices incident to one common face. We say that a ...
[57]
[PDF] Computing Cartograms with Optimal Complexity - arXiv
Dec 30, 2011 · In our paper and in most of the other papers cited here, “planar graph” refers to an inner-triangulated planar graph with a simple outer-face; ...
[58]
[2311.09364] The Structure of Metrizable Graphs - arXiv
Nov 15, 2023 · In particular, we show that every metrizable graph with 11 vertices or more is outerplanar plus one vertex. Subjects: Combinatorics (math.CO).