Bounded geometric thickness for unions of two forests
Let $G$ be a finite simple graph of arboricity at most $2$, that is, whose edge set can be partitioned into two forests. Its geometric thickness $\bar\theta(G)$ is the least number of edge colours in a straight-line drawing of $G$ in the plane with no two edges of the same colour crossing; all colours share the same vertex positions, vertices are distinct points, and no edge passes through a vertex other than its endpoints.
Duncan proved that every $n$-vertex graph of arboricity at most $2$ has geometric thickness $O(\log n)$. Jain, Ricci, Rollin and Schulz proved that $2$-degenerate graphs, which have arboricity at most $2$, have geometric thickness at most $4$, and that some $2$-degenerate graph has geometric thickness at least $3$. Eppstein constructed, for every $t$, graphs of thickness three with geometric thickness at least $t$.
Problem. Does there exist an absolute constant $C$ such that $\bar\theta(G) \le C$ for every graph $G$ of arboricity at most $2$?
Source: Jain, Ricci, Rollin and Schulz (2025), Section 4 (Conclusions); see also Duncan (2011), Section 4.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, arboricity, 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 = {2025},
pages = {94--123},
doi = {10.20382/jocg.v15i2a4},
eprint = {2302.14721},
archivePrefix = {arXiv},
}
@article{duncan2011,
author = {Duncan, Christian A.},
title = {On graph thickness, geometric thickness, and separator theorems},
journal = {Comput. Geom.},
volume = {44},
number = {2},
year = {2011},
pages = {95--99},
doi = {10.1016/j.comgeo.2010.09.005},
}
@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-arboricity-two-geometric-thickness,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Bounded geometric thickness for unions of two forests}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/592-arboricity-two-geometric-thickness.md},
note = {Entry 592 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-00847, "Bounded geometric thickness for unions of two forests", clopen.solutions.