Three or four layers for 2-degenerate graphs
The geometric thickness $\bar\theta(G)$ of a finite simple graph $G$ is the least number of colours in an edge colouring of some straight-line drawing of $G$ in the plane with no two edges of the same colour crossing; vertices are drawn as distinct points, no edge passes through a vertex other than its endpoints, and all colours share the same vertex positions.
Eppstein asked whether $2$-degenerate graphs have bounded geometric thickness and whether some $2$-degenerate graph has geometric thickness greater than $2$. Jain, Ricci, Rollin and Schulz proved that every $2$-degenerate graph has a straight-line drawing whose edges split into four plane forests, so $\bar\theta(G) \le 4$, and that some $2$-degenerate graph has $\bar\theta(G) \ge 3$. They also proved $\bar\theta(G) \le 3$, with three plane forests, for a subclass of $2$-degenerate graphs they call monotone, which contains their example.
Problem. Is $\bar\theta(G) \le 3$ for every $2$-degenerate graph $G$? Equivalently, does a $2$-degenerate graph of geometric thickness $4$ exist?
Source: Jain, Ricci, Rollin and Schulz (2025), Section 4, after Eppstein's questions on 2-inductive graphs (2004).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, degenerate graphs, geometric thickness
References
@article{jain2025,
author = {Jain, Rahul and Ricci, Marco and Rollin, Jonathan and Schulz, Andr{\'e}},
title = {On the geometric thickness of 2-degenerate graphs},
journal = {J. Comput. Geom.},
volume = {15},
number = {2},
year = {2024},
pages = {94--123},
doi = {10.20382/jocg.v15i2a4},
eprint = {2302.14721},
archivePrefix = {arXiv},
}
@incollection{eppstein2004separating,
author = {Eppstein, David},
title = {Separating thickness from geometric thickness},
booktitle = {Towards a Theory of Geometric Graphs},
editor = {Pach, J{\'a}nos},
series = {Contemp. Math.},
volume = {342},
publisher = {Amer. Math. Soc.},
address = {Providence, RI},
year = {2004},
pages = {75--86},
doi = {10.1090/conm/342/06132},
eprint = {math/0204252},
archivePrefix = {arXiv},
}
@misc{aim-geometric-thickness-two-degenerate,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Three or four layers for 2-degenerate graphs}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/591-geometric-thickness-two-degenerate.md},
note = {Entry 591 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00869, "Three or four layers for 2-degenerate graphs", clopen.solutions.