The canonical-drawing characterization of product structure for regular polygon intersection graphs

Let nn be a positive integer, let α\alpha be a parameter, and consider the class of intersection graphs of α\alpha-free homothetic regular nn-gons. A canonical drawing is a drawing associated with such an intersection representation, and a drawing is kk-independent crossing if no edge is crossed by more than kk independent edges.

The canonical-drawing characterization. The class of intersection graphs of α\alpha-free homothetic regular nn-gons admits product structure if and only if their canonical drawings are kk-independent crossing for a global constant kk, possibly depending on nn.

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

Never refreshed

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.