The product-structure conjecture for k-independent crossing graphs

Let kk be a nonnegative integer. A graph is kk-independent crossing if it has a topological drawing in which no edge is crossed by more than kk independent edges.

Product-structure conjecture for kk-independent crossing graphs. The class of kk-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 αs(n)\alpha\geq s(n), 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

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.