# Thickness (graph theory)
**Thickness** is a graph-theoretic parameter that measures how far a graph is from being planar: the thickness of a graph \( G \), usually written \( \theta(G) \) or \( t(G) \), is the minimum number of planar subgraphs into which the edge set of \( G \) can be partitioned, or equivalently the minimum number of planar layers needed to draw all edges so that no two edges in the same layer cross.[1](https://mathworld.wolfram.com/GraphThickness.html) • [2](https://eccc.weizmann.ac.il/resources/pdf/Thesis-Jayalal.pdf) A planar graph has thickness 1, and every nonplanar graph has thickness at least 2.[1](https://mathworld.wolfram.com/GraphThickness.html)
| Key fact | Detail |
|---|---|
| Definition | Minimum number of planar subgraphs whose union is \( G \); equivalently, minimum number of planar layers in a drawing with arbitrary-curve edges[1](https://mathworld.wolfram.com/GraphThickness.html) • [2](https://eccc.weizmann.ac.il/resources/pdf/Thesis-Jayalal.pdf) |
| Basic values | \( \theta(G) = 1 \) exactly for planar graphs; nonplanar graphs have \( \theta(G) \ge 2 \); graphs of thickness 1 or 2 are called biplanar[1](https://mathworld.wolfram.com/GraphThickness.html) |
| Complexity | Computing the thickness of a graph is NP-complete (Mansfeld 1983)[1](https://mathworld.wolfram.com/GraphThickness.html) |
| Lower bound | \( \theta(G) \ge \lceil m/(3n-6) \rceil \) for \( n \ge 3 \) vertices and \( m \) edges[1](https://mathworld.wolfram.com/GraphThickness.html) |
| Complete graphs | \( \theta(K_n) = \lfloor (n+7)/6 \rfloor \), except \( \theta(K_9) = \theta(K_{10}) = 3 \) (Vasak 1976; Alekseev and Gonchakov 1976)[1](https://mathworld.wolfram.com/GraphThickness.html) |
| General upper bound | \( \theta(G) \le \lfloor 5/6 + \sqrt{2m/9 - 23/36} \rfloor \) for \( m \ge 3 \) edges[3](https://www.sciencedirect.com/science/article/pii/S0166218X25004160) |
| Variants | Geometric thickness (straight-line edges), book thickness (vertices on a spine), outerthickness (outerplanar layers)[2](https://eccc.weizmann.ac.il/resources/pdf/Thesis-Jayalal.pdf) • [4](https://mathworld.wolfram.com/BookThickness.html) • [5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol374-icalp2026/html/LIPIcs.ICALP.2026.137/LIPIcs.ICALP.2026.137.html) |
## Definition and basic properties
The parameter is defined through a decomposition of the edge set. Given a graph \( G \), one seeks the smallest integer \( t \) such that \( G \) can be decomposed into \( t \) planar subgraphs; each edge is assigned to exactly one layer, all layers share the original vertex set, and each layer must be planar under the usual graph convention.[3](https://www.sciencedirect.com/science/article/pii/S0166218X25004160) In drawing terms, the thickness is the minimum number of layers in a planar drawing of \( G \) in which each edge belongs to a single layer, no two edges in the same layer cross, and edges may be drawn as arbitrary curves.[2](https://eccc.weizmann.ac.il/resources/pdf/Thesis-Jayalal.pdf)
The parameter is therefore a measure of how close a graph is to being planar.[6](https://arxiv.org/abs/1708.04773) A graph that is the union of two planar graphs, meaning a graph of thickness 1 or 2, is called a biplanar graph.[1](https://mathworld.wolfram.com/GraphThickness.html)
## Bounds
Because a planar graph on \( n \ge 3 \) vertices has at most \( 3n - 6 \) edges, each planar layer can carry at most that many edges, which yields the standard lower bound
\[ \theta(G) \ge \left\lceil \frac{m}{3n-6} \right\rceil, \]
where \( m \) is the number of edges and \( n \ge 3 \) the number of vertices.[1](https://mathworld.wolfram.com/GraphThickness.html) The bound is not always tight: for the complete graph \( K_9 \), which has \( m = 36 \) and \( n = 9 \), it gives \( \lceil 36/21 \rceil = 2 \), while the actual thickness is 3.[1](https://mathworld.wolfram.com/GraphThickness.html) A related bound for triangle-free connected simple graphs replaces the planar edge bound with \( e_i \le 2v_i - 4 \), giving a lower bound of \( \lceil e/(2v-4) \rceil \).[7](https://www.vaia.com/en-us/textbooks/math/discrete-mathematics-and-its-applications-8-edition/chapter-10/problem-34-the-thickness-of-a-simple-graph-g-is-the-smallest/)
On the upper side, a 2025 result proves that for any graph with \( m \ge 3 \) edges,
\[ \theta(G) \le \left\lfloor \frac{5}{6} + \sqrt{\frac{2m}{9} - \frac{23}{36}} \right\rfloor, \]
which improves the previously known general bound.[3](https://www.sciencedirect.com/science/article/pii/S0166218X25004160) In 1991, Dean et al. conjectured the stronger statement that the thickness of a graph with \( m \) edges is at most \( \sqrt{m/16} + O(1) \); the 2025 work confirms the conjecture for graphs of girth at least 5, and proves \( \theta(G) < 1 + \sqrt[s]{m/2} \) for girth \( g \ge 6 \), where \( s = \lfloor g/2 \rfloor \).[3](https://www.sciencedirect.com/science/article/pii/S0166218X25004160)
Thickness is connected to crossing parameters as well: Brooks' theorem implies that a graph's thickness exceeds its local crossing number by no more than one (Kainen 1973; Thomassen 1988).[1](https://mathworld.wolfram.com/GraphThickness.html)
## Complete graphs
The thickness of the complete graph \( K_n \) is known exactly:
\[ \theta(K_n) = \left\lfloor \frac{n+7}{6} \right\rfloor, \]
with the exceptions \( \theta(K_9) = \theta(K_{10}) = 3 \); the result is credited to Vasak (1976) and Alekseev and Gonchakov (1976).[1](https://mathworld.wolfram.com/GraphThickness.html) For \( n = 1, 2, \ldots \) the values therefore run 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, and so on.[1](https://mathworld.wolfram.com/GraphThickness.html) The case \( K_9 \) can be seen constructively: its 36 edges decompose into three planar subgraphs, and this decomposition is minimal.[1](https://mathworld.wolfram.com/GraphThickness.html)
## Computational complexity
Deciding the thickness of a graph is NP-complete, a result due to Mansfeld (1983).[1](https://mathworld.wolfram.com/GraphThickness.html) Related minimization problems are also hard: determining the outerthickness of a graph, the minimum number of parts in an edge partition such that each part induces an outerplanar subgraph, is NP-hard.[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol374-icalp2026/html/LIPIcs.ICALP.2026.137/LIPIcs.ICALP.2026.137.html) Structural tools remain useful despite the hardness. Tutte introduced the notion of a \( t \)-minimal graph with respect to thickness: a graph \( G \) is \( t \)-minimal if \( \theta(G) = t \) and the thickness of every proper subgraph of \( G \) is less than \( t \).[3](https://www.sciencedirect.com/science/article/pii/S0166218X25004160)
## Variants
Several refinements of thickness restrict how the layers are drawn.
**Geometric thickness.** The geometric thickness \( \bar{\theta}(G) \) is the minimum number of layers in a planar drawing in which every edge must be a straight line segment, with each edge assigned to one layer and no two edges of a layer crossing.[2](https://eccc.weizmann.ac.il/resources/pdf/Thesis-Jayalal.pdf) • [8](https://www.sciencedirect.com/science/article/pii/S0012365X03002401) Although geometric thickness can surpass ordinary thickness, the two measures do not always track each other on the same graph families: in contrast to what happens for complete graphs, certain complete bipartite graphs on arbitrarily many vertices have geometric thickness equal to their standard thickness.[9](https://arxiv.org/abs/math/9910185) In a variant permitting a single bend per edge, Wood proved that any graph with n vertices and m edges has a drawing in which the vertices sit on a grid, every edge makes no more than one bend, and edges sharing a layer never intersect; a Las Vegas algorithm produces this drawing.[8](https://www.sciencedirect.com/science/article/pii/S0012365X03002401)
**Book thickness.** The book thickness, also called pagenumber, page-number, stacknumber, or fixed outerthickness, is the minimum number of pages possible for a book embedding, an embedding on a collection of half-planes (pages) sharing a common boundary line (spine) with all vertices on the spine and no crossing edges.[4](https://mathworld.wolfram.com/BookThickness.html) • [10](https://graphclasses.org/classes/par_32.html) Its values are characterized for small numbers: a graph has book thickness 0 exactly when it has no edges, book thickness 1 exactly when it is non-empty and outerplanar, and book thickness at most 2 exactly when it is subhamiltonian; in particular, book thickness exactly 2 holds for subhamiltonian graphs that are not outerplanar.[4](https://mathworld.wolfram.com/BookThickness.html) Bernhart and Kainen (1979) gave the constraint \( \lceil (m-n)/(m-3) \rceil \le \mathrm{bt}(G) \le \lfloor n/2 \rfloor \) for a graph with \( n \) vertices and \( m \) edges.[4](https://mathworld.wolfram.com/BookThickness.html)
**Outerthickness.** Introduced by Guy (1974), this parameter of a graph \( G \) counts how few classes an edge partition of \( G \) can have while every class forms an outerplanar subgraph — in other words, a planar graph that can be drawn with all its vertices on the outer face.[5](https://drops.dagstuhl.de/storage/00lipics/lipics-vol374-icalp2026/html/LIPIcs.ICALP.2026.137/LIPIcs.ICALP.2026.137.html)
**Other directions.** Thickness has been investigated on other surfaces, partitioning the edge set into subgraphs embeddable on a surface of a given genus.[11](https://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf) A complementary parameter, antithickness, measures how close a graph is to being a thrackle, in the same drawing-based framework in which thickness measures closeness to planarity.[6](https://arxiv.org/abs/1708.04773) Thickness also connects to drawing with few bends: graphs with linear arboricity \( k \) can be drawn on \( k \) planar layers with bend complexity \( 3(k-1)n/(4k-2) \) bends per edge, and a graph of thickness 1 can be drawn on a single layer with bend complexity 0 by Fáry's theorem.[12](https://epubs.siam.org/doi/abs/10.1137/16M1110042)
## References
1. [Graph Thickness, Wolfram MathWorld](https://mathworld.wolfram.com/GraphThickness.html)
2. [Preliminaries on thickness and geometric thickness, ECCC thesis chapter](https://eccc.weizmann.ac.il/resources/pdf/Thesis-Jayalal.pdf)
3. [The thickness of a graph with constraint on girth, Discrete Applied Mathematics (2025)](https://www.sciencedirect.com/science/article/pii/S0166218X25004160)
4. [Book Thickness, Wolfram MathWorld](https://mathworld.wolfram.com/BookThickness.html)
5. [Determining the Outerthickness of Graphs Is NP-Hard, LIPIcs ICALP 2026](https://drops.dagstuhl.de/storage/00lipics/lipics-vol374-icalp2026/html/LIPIcs.ICALP.2026.137/LIPIcs.ICALP.2026.137.html)
6. [Thickness and Antithickness of Graphs, arXiv:1708.04773](https://arxiv.org/abs/1708.04773)
7. [Discrete Mathematics and Its Applications, Chapter 10, Problem 34, Vaia](https://www.vaia.com/en-us/textbooks/math/discrete-mathematics-and-its-applications-8-edition/chapter-10/problem-34-the-thickness-of-a-simple-graph-g-is-the-smallest/)
8. [Geometric thickness in a grid, D. R. Wood, Discrete Mathematics 273 (2003)](https://www.sciencedirect.com/science/article/pii/S0012365X03002401)
9. [Geometric Thickness of Complete Graphs, arXiv:math/9910185](https://arxiv.org/abs/math/9910185)
10. [Book thickness parameter, Information System on Graph Classes](https://graphclasses.org/classes/par_32.html)
11. [Survey on graph thickness, Archdeacon, University of Szeged](https://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf)
12. [Relating Graph Thickness to Planar Layers and Bend Complexity, SIAM Journal on Discrete Mathematics](https://epubs.siam.org/doi/abs/10.1137/16M1110042)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph invariants and parameters › Genus, crossing, and embedding invariants*
*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