The canonical-drawing characterization of product structure for regular polygon intersection graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.