The no-product-structure conjecture below the independent-crossing threshold

Let nn be a positive integer, let s(n)s(n) be the threshold defined in the paper, and let α\alpha be a parameter. Consider the class of intersection graphs of α\alpha-free homothetic regular nn-gons.

The no-product-structure conjecture. For every α<s(n)\alpha < s(n), the class of intersection graphs of α\alpha-free homothetic regular nn-gons does not have product structure.

The paper determines that arbitrarily many independent edges can cross a single edge in canonical drawings when α<s(n)\alpha<s(n), but the required construction ruling out product structure is known only in some cases and an alternative construction is suspected for the remaining cases.

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.