The no-product-structure conjecture below the independent-crossing threshold
Let be a positive integer, let be the threshold defined in the paper, and let be a parameter. Consider the class of intersection graphs of -free homothetic regular -gons.
The no-product-structure conjecture. For every , the class of intersection graphs of -free homothetic regular -gons does not have product structure.
The paper determines that arbitrarily many independent edges can cross a single edge in canonical drawings when , but the required construction ruling out product structure is known only in some cases and an alternative construction is suspected for the remaining cases.
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.