A linear threshold for extracting a segment grid
Let $G_k$ be the arrangement of $k$ horizontal segments crossing $k$ vertical segments. An arrangement of red and blue straight-line segments is combinatorially equivalent to $G_k$ if the embedded plane graph obtained by subdividing the segments at their crossings is isomorphic to that of $G_k$, with colors, cyclic orders at vertices and the unbounded face preserved; this is stronger than every red segment crossing every blue one. Jain, Ricci, Rollin and Schulz showed that $k 2^{k-1}$ pairwise disjoint red segments and $k$ pairwise disjoint blue segments, each red crossing each blue, contain $k$ red and $k$ blue segments combinatorially equivalent to $G_k$, and used this to construct $2$-degenerate graphs of geometric thickness at least $3$.
Problem. Let $k \ge 1$, and let $3k$ pairwise disjoint red straight-line segments and $3k$ pairwise disjoint blue straight-line segments in the plane be such that every red segment crosses every blue segment in their relative interiors. Must there be $k$ red and $k$ blue segments among them whose arrangement is combinatorially equivalent to $G_k$?
Source: Jain, Ricci, Rollin and Schulz (2025), Section 4, Question 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- AIM Open Applied Problems, geometric thickness, segment arrangements
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},
}
@misc{aim-red-blue-segment-grid,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A linear threshold for extracting a segment grid}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/593-red-blue-segment-grid.md},
note = {Entry 593 at commit 24edaad, 2026-10-15},
}
Resolution claims
For every integer \(k\geq1\), an arrangement of \(3k\) disjoint red straight-line segments and \(3k\) disjoint blue straight-line segments, with every red--blue pair crossing in both relative interiors, contains \(k\) segments of each color forming an embedded rectangular grid. This answers Question 1 of Jain, Ricci, Rollin and Schulz. The equivalence preserves the entire subdivided segment paths, their cyclic orders and …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Needs verification → Solution claimed | — | Recorded here: AIM @ 24edaad, paper/segment_grids.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00830, "A linear threshold for extracting a segment grid", clopen.solutions.