Polynomial-time branchwidth conjecture for graphs embeddable in the torus and projective plane
Polynomial-time branchwidth conjecture for graphs embeddable in the torus and projective plane
Let be a graph that can be embedded both in the torus and in the projective plane. Consider graphs excluding as a minor.
Polynomial-time branchwidth conjecture. Branchwidth can be computed in polynomial time on -minor-free graphs.
Exact polynomial-time computation of branchwidth is known for graph classes excluding a single-crossing graph as a minor, while the corresponding question for graphs excluding a graph embeddable in both the torus and the projective plane remains open.
Sources & referencesView supporting material
Primary source
Dimitrios M. Thilikos and Sebastian Wiederrecht, “Approximating branchwidth on parametric extensions of planarity”, arXiv:2304.04517 (2026).
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.