The canonical-drawing characterization of product structure for regular polygon intersection graphs
Let be a positive integer, let be a parameter, and consider the class of intersection graphs of -free homothetic regular -gons. A canonical drawing is a drawing associated with such an intersection representation, and a drawing is -independent crossing if no edge is crossed by more than independent edges.
The canonical-drawing characterization. The class of intersection graphs of -free homothetic regular -gons admits product structure if and only if their canonical drawings are -independent crossing for a global constant , possibly depending on .
This conjecture proposes that product structure is exactly captured by bounded independent crossing in the canonical drawings; the paper establishes bounded independent crossing in one parameter regime but leaves the converse characterization open.
References
Primary source
Laura Merker, Lena Scherzer, Samuel Schneider and Torsten Ueckerdt, “Intersection Graphs with and without Product Structure”, arXiv:2409.01732 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.