# Outerplanar graph
An **outerplanar graph** is a graph that can be drawn in the plane without edge crossings so that all vertices lie on the same face, the outer face[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [2](https://www.graphclasses.org/classes/gc_110.html). Every outerplanar graph is planar, but the requirement that all vertices lie on the outer face is a genuine restriction: the complete graph K4 is not outerplanar[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf). The class is often used as a first non-trivial test case for results about all planar graphs, because it is small enough to analyze completely while still displaying the phenomena of interest[3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/).
| Key fact | Detail |
|---|---|
| Definition | Crossing-free plane embedding with all vertices on one (outer) face[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [2](https://www.graphclasses.org/classes/gc_110.html) |
| Forbidden minors | Outerplanar if and only if it has no minor isomorphic to K4 or K2,3[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [4](https://www.math.lsu.edu/~ding/paper40.pdf) |
| Book thickness | Exactly the graphs of pagenumber (book thickness) one[5](https://www.emis.de/ft/51060) |
| Treewidth | At most two; an important subclass of the series-parallel graphs, which are precisely the graphs of treewidth at most two[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) |
| Coloring | Every connected outerplane graph with at least two vertices has list chromatic number between 2 and 3[6](https://dl.acm.org/doi/abs/10.1006/eujc.2000.0430) |
| Weak dual | A forest; a tree when the graph is biconnected[7](https://irma.math.unistra.fr/~sereni/Articles/CHS07.pdf) |
| Recognition | Linear-time algorithms exist for recognizing and embedding outerplanar graphs[7](https://irma.math.unistra.fr/~sereni/Articles/CHS07.pdf) |
| Enumeration | Labeled count grows as h·n^(−5/2)·σ^(−n)·n! with σ ≈ 0.136593[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) |
## Definition and basic properties
Outerplanarity means that a graph can be drawn in the plane without any edge crossings while keeping every vertex on a single face.[2](https://www.graphclasses.org/classes/gc_110.html) For k > 1, a graph counts as k-outerplanar when it can be drawn in the plane so that, once the outer face's vertices are deleted, every component left over is (k−1)-outerplanar.[8](https://arxiv.org/html/2506.08151v2)
The class sits inside the planar graphs and serves as a proving ground: structural and algorithmic results established for outerplanar graphs frequently guide what to expect for planar graphs in general[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/).
## History
The concept enters the literature with **Gary Chartrand and Frank Harary's** 1967 paper "Planar permutation graphs", published in the *Annales de l'institut Henri Poincaré*, Section B 3(4):433–438[9](https://dl.acm.org/doi/10.1007/s10618-009-0162-1); outerplanar graphs also appear in Harary's classical book[10](https://ajc.maths.uq.edu.au/download/52/ajc_v52_p185.pdf). A later episode shows the limits of early optimism: Chartrand, Geller, and Hedetniemi conjectured that every planar graph can be edge-partitioned into two outerplanar subgraphs, and this conjecture was refuted in the *Journal of Combinatorial Theory*, Series B[11](https://www.sciencedirect.com/science/article/pii/S009589569690043X).
## Characterizations
The central characterization is by forbidden minors. A graph is outerplanar if and only if it contains no minor isomorphic to K4 or K2,3, equivalently no subdivision of either graph as a subgraph; the obstruction set is exactly ob(O) = {K4, K2,3}[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [4](https://www.math.lsu.edu/~ding/paper40.pdf).
Outerplanar graphs admit several further characterizations, some of them counterparts of well-known characterizations of planar graphs, and these provide efficient tools for outerplanarity testing, coding (isomorphism testing), and counting[5](https://www.emis.de/ft/51060). The forbidden-subgraph form (no subdivision of K4 or K2,3) and the forbidden-minor form coincide[4](https://www.math.lsu.edu/~ding/paper40.pdf).
## Structural properties
**Duals and treewidth.** The weak dual of an outerplanar graph, formed by taking one vertex per bounded face and joining vertices whose faces share an edge, is a forest; when the graph is biconnected, the weak dual is a tree[7](https://irma.math.unistra.fr/~sereni/Articles/CHS07.pdf). Bodlaender and Fomin proved a duality for biconnected outerplanar graphs G without loops or multiple edges: pw(G*) ≤ pw(G) ≤ 2·pw(G*) + 2, where pw denotes pathwidth and G* the dual[7](https://irma.math.unistra.fr/~sereni/Articles/CHS07.pdf).
Outerplanar graphs have treewidth at most two and form an important subclass of the series-parallel graphs, which are precisely the graphs of treewidth at most two[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf). In the same direction, every simple two-connected series-parallel graph that excludes a fixed minor H admits a tree-decomposition whose torsos are either outerplanar graphs or planar duals of outerplanar graphs[12](https://web.math.princeton.edu/~pds/papers/RS1/paper.pdf).
**Degrees.** Extremal results pin down how many vertices of large degree an outerplanar graph can have: for k ≥ 6 and n ≥ k + 2, the extremal function is βk(n) = ⌊(n − 6)/(k − 4)⌋, and a related parameter is bounded by ⌊2(n − 4)/3⌋, except one less when n ≡ 1 mod 6[13](https://www.dwest.web.illinois.edu/pubs/outerpl.pdf).
## Coloring
Every connected outerplane graph G with at least two vertices (an outerplanar graph with a fixed outer embedding) satisfies 2 ≤ l(G) ≤ 3 for its list chromatic number, and l(G) = 2 if and only if G is bipartite with at most one cycle[6](https://dl.acm.org/doi/abs/10.1006/eujc.2000.0430). So three colors always suffice even when each vertex has its own list of three available colors.
For random instances the answer is essentially always three: the probability that the chromatic number of a random outerplanar graph differs from three converges to zero exponentially fast[3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/).
[Edge coloring](https://www.edgepedia.org/edge-coloring) behaves similarly well. For a connected outerplane graph G with at least one edge, the list chromatic index l'(G) equals Δ(G) + 1 if and only if G is an odd cycle, which proves the well-known list edge coloring conjecture for outerplane graphs[6](https://dl.acm.org/doi/abs/10.1006/eujc.2000.0430). For the strong chromatic index, which colors edges so that any two edges that share an endpoint, or are both adjacent to a third edge, receive different colors, every outerplanar graph G with maximum degree Δ ≥ 3 has χ'_s(G) ≤ 3Δ − 3, a tight bound, and every bipartite outerplanar graph satisfies χ'_s(G) ≤ 2Δ[14](https://www.mdpi.com/2075-1680/11/4/168).
## Maximal outerplanar graphs
A maximal outerplanar graph is one to which no edge can be added while preserving outerplanarity. In such a graph the edges not on the outer cycle form a triangulation of that cycle, and the outer cycle is a [Hamiltonian cycle](https://www.edgepedia.org/hamiltonian-cycle)[10](https://ajc.maths.uq.edu.au/download/52/ajc_v52_p185.pdf). Any maximal outerplanar graph can be constructed inductively by starting with a smaller such graph and inserting a new degree-2 vertex next to the two endpoints of one edge on the outer face.[15](https://mathoverflow.net/questions/491362/enumeration-and-data-collection-of-maximal-outerplanar-graphs)
The counts are tabulated as OEIS sequence A000207; the number of maximal outerplanar graphs on 20 vertices is 11,944,614, computable via a generating function in the OEIS entry[15](https://mathoverflow.net/questions/491362/enumeration-and-data-collection-of-maximal-outerplanar-graphs).
## Recognition and algorithms
Linear-time algorithms to recognize outerplanar graphs and produce a witnessing embedding are known[7](https://irma.math.unistra.fr/~sereni/Articles/CHS07.pdf). The equivalence with book embeddings gives another route: a book embedding places all vertices on a line, the spine, with edges assigned to half-plane pages so that edges on the same page do not cross, and outerplanar graphs are exactly the graphs of book thickness one[2](https://www.graphclasses.org/classes/gc_110.html) • [5](https://www.emis.de/ft/51060).
Not every one-page question stays easy. Although graphs of stack number 1 are exactly the outerplanar graphs, deciding whether a given outerplanar graph has queue number 1 is NP-hard[16](https://arxiv.org/abs/2607.24297).
## How it compares with related graph classes
The inclusions run: outerplanar graphs ⊂ series-parallel graphs = graphs of treewidth at most two ⊂ planar graphs[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf). The book-embedding view separates the class cleanly from its neighbors: one page suffices for outerplanar graphs[5](https://www.emis.de/ft/51060). A related parameter measures how far a graph is from the class: the vertex outerplanar deletion number is the minimum size of a vertex subset X such that removing X leaves an outerplanar graph[2](https://www.graphclasses.org/classes/gc_110.html).
## By the numbers: enumeration and random outerplanar graphs
The class has a complete asymptotic theory. The number h_n of labeled outerplanar graphs on n vertices satisfies h_n ∼ h·n^(−5/2)·σ^(−n)·n! with σ ≈ 0.136593[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf). For unlabeled graphs, the count grows as g·n^(−5/2)·ρ^(−n) with g ≈ 0.00909941 and ρ^(−1) ≈ 7.50360, and the exact number on n vertices is computable in polynomial time[3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/). Two-connected outerplanar graphs have exponential growth rate 3 + 2√2 ≈ 5.82843 with constant d ≈ 0.00596026, connected ones have constant c ≈ 0.00760471, and bipartite outerplanar graphs grow with rate ≈ 4.57717[3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/).
The number of edges in a random outerplanar graph on n vertices is asymptotically Gaussian, so it is sharply concentrated around its mean[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/). The two main analyses disagree on the constant: the DMTCS study reports mean κ ≈ 1.616734n with variance λ ≈ 0.553479n[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf), while the [Electronic Journal of Combinatorics](https://www.edgepedia.org/electronic-journal-of-combinatorics) study of unlabeled graphs reports mean ≈ 1.54894n with variance ≈ 0.227504n, and gives ≈ 1.70711n for the two-connected case[3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/). Both analyses agree that a random outerplanar graph has linearly many edges[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf) • [3](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/).
For data structures, the class is compact: outerplanar graphs can be encoded with 3n bits, so the number of them on n vertices is at most 8^n[1](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf).
## Applications
In applied data mining, outerplanar graphs support frequent subgraph mining because well-behaved outerplanar graphs have only polynomially many simple cycles, keeping the search space manageable[9](https://dl.acm.org/doi/10.1007/s10618-009-0162-1).
## Generalizations and recent developments
The natural relaxation allows crossings bounded by a parameter k. An **outer k-planar graph** has all vertices on one face and each edge crossing at most k others. Recent work has mapped this class thoroughly. Outer k-planar graphs are ⌊3.5·√k⌋-degenerate and hence colorable with ⌊3.5·√k⌋ + 1 colors; every one has a balanced vertex separator of size at most 2k + 3; and since every outer k-planar graph has treewidth O(k), Courcelle's theorem implies that closed outer k-planarity is linear-time testable[17](https://www.cgt-journal.org/index.php/cgt/article/view/61).
A 2025 paper sharpened the treewidth picture for outer min-k-planar graphs, improving the upper bound from 3k + 1 to 3·⌊k/2⌋ + 4 and the separation-number bound from 2k + 1 to 2·⌊k/2⌋ + 4, with both multiplicative constants optimal; it also constructed an infinite family of outer k-planar graphs with treewidth at least 1.5k + 0.5, showing the constant 1.5 in the upper bound 1.5k + 2 cannot be improved[8](https://arxiv.org/html/2506.08151v2). On edge counts, work presented at SoCG 2025 shows any outer k-planar graph with n vertices has at most 4.1·√k·n edges, with a tighter bound (k + 3)(n − 2) for k ≤ 3 that is tight for k ∈ {1, 2}[18](https://drops.dagstuhl.de/storage/00lipics/lipics-vol332-socg2025/LIPIcs.SoCG.2025.65/LIPIcs.SoCG.2025.65.pdf).
Directed versions advanced too: directed acyclic outerplanar graphs have constant stack number, answering positively a 1999 conjecture of Heath, Pemmaraju, and Trenk, and consequently all upward outerplanar graphs have constant stack number[19](https://theoretics.episciences.org/16759). On the degree-sequence side, a 2024 paper gives a polynomial-time algorithm that produces a 2-page book embedding realization for any degree sequence in a family containing all outerplanaric sequences; if the given sequence has a 1-page (outerplanar) realization, the algorithm produces a 2-page realization for it[20](https://www.sciencedirect.com/science/article/abs/pii/S0022000024000837).
## References
1. [On the number of series-parallel and outerplanar graphs, DMTCS](https://emis.dsd.sztaki.hu/journals/DMTCS/pdfpapers/dmAE0174.pdf)
2. [Information System on Graph Classes and their Inclusions: outerplanar graphs](https://www.graphclasses.org/classes/gc_110.html)
3. [Enumeration and asymptotic properties of unlabeled outerplanar graphs, Electronic Journal of Combinatorics](https://www.combinatorics.org/ojs/index.php/eljc/article/download/v14i1r66/pdf/)
4. [Obstruction set paper, Ding, LSU](https://www.math.lsu.edu/~ding/paper40.pdf)
5. [Characterizations of outerplanar graphs, EMIS](https://www.emis.de/ft/51060)
6. [Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs, European Journal of Combinatorics](https://dl.acm.org/doi/abs/10.1006/eujc.2000.0430)
7. [Pathwidth of outerplanar graphs](https://irma.math.unistra.fr/~sereni/Articles/CHS07.pdf)
8. [Treewidth of Outer k-Planar Graphs, arXiv 2025](https://arxiv.org/html/2506.08151v2)
9. [Frequent subgraph mining in outerplanar graphs, Data Mining and Knowledge Discovery](https://dl.acm.org/doi/10.1007/s10618-009-0162-1)
10. [Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs, Australasian Journal of Combinatorics](https://ajc.maths.uq.edu.au/download/52/ajc_v52_p185.pdf)
11. [Outerplanar Partitions of Planar Graphs, Journal of Combinatorial Theory, Series B](https://www.sciencedirect.com/science/article/pii/S009589569690043X)
12. [Rough structure. I. Exclusion among series-parallel graphs](https://web.math.princeton.edu/~pds/papers/RS1/paper.pdf)
13. [Vertex Degrees in Outerplanar Graphs](https://www.dwest.web.illinois.edu/pubs/outerpl.pdf)
14. [Strong Chromatic Index of Outerplanar Graphs, MDPI Symmetry](https://www.mdpi.com/2075-1680/11/4/168)
15. [Enumeration and data collection of maximal outerplanar graphs, MathOverflow](https://mathoverflow.net/questions/491362/enumeration-and-data-collection-of-maximal-outerplanar-graphs)
16. [On the Recognition of Outerplanar Graphs with Queue Number 1, arXiv](https://arxiv.org/abs/2607.24297)
17. [Beyond Outerplanarity, Computing in Geometry and Topology](https://www.cgt-journal.org/index.php/cgt/article/view/61)
18. [Recognizing 2-Layer and Outer k-Planar Graphs, SoCG 2025, LIPIcs](https://drops.dagstuhl.de/storage/00lipics/lipics-vol332-socg2025/LIPIcs.SoCG.2025.65/LIPIcs.SoCG.2025.65.pdf)
19. [Directed Acyclic Outerplanar Graphs Have Constant Stack Number, Theoretics](https://theoretics.episciences.org/16759)
20. [Approximate realizations for outerplanaric degree sequences, JCSS 2024](https://www.sciencedirect.com/science/article/abs/pii/S0022000024000837)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory subfields and named results › Geometric graph theory*
*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license