Polynomial row-treewidth conjecture for string graphs on fixed surfaces
Polynomial row-treewidth conjecture for string graphs on fixed surfaces
Let be a string graph drawn in a surface of fixed Euler genus , and let be the maximum degree of . Polynomial row-treewidth conjecture. The row treewidth of is at most for some polynomial function . 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
Sign in to submit a solution.
No solutions have been posted yet.