Polynomial row-treewidth conjecture for string graphs on fixed surfaces

Let GG be a string graph drawn in a surface of fixed Euler genus gg, and let Δ\Delta be the maximum degree of GG. Polynomial row-treewidth conjecture. The row treewidth of GG is at most f(Δ,g)f(\Delta,g) for some polynomial function ff. The conjecture seeks to improve the paper's exponential or larger bounds for string graphs of bounded maximum degree; the source treats it as an open problem.

Sources & referencesView supporting material

Primary source

Nikolai Karol, “String Graphs: Product Structure and Localised Representations”, arXiv:2511.15156 (2025).

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.