Polynomial-time branchwidth conjecture for graphs embeddable in the torus and projective plane

Let HH be a graph that can be embedded both in the torus and in the projective plane. Consider graphs excluding HH as a minor.

Polynomial-time branchwidth conjecture. Branchwidth can be computed in polynomial time on HH-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

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.