The product-structure conjecture for k-independent crossing graphs
The product-structure conjecture for k-independent crossing graphs
Let be a nonnegative integer. A graph is -independent crossing if it has a topological drawing in which no edge is crossed by more than independent edges.
Product-structure conjecture for -independent crossing graphs. The class of -independent crossing graphs admits product structure.
This would extend the known product-structure results for planar and other beyond-planar graph classes. The paper applies the conjecture to canonical drawings of regular polygon intersection graphs, where bounded independent crossing is proved for , but the general product-structure assertion remains 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
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.