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

About 2 years old · traced to

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.

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

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.