The no-product-structure conjecture below the independent-crossing threshold
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.
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.