{"id":"arxiv/2602.06516","url":"https://arxiv.org/abs/2602.06516","tags":["math.CO","cs.DM"],"score":0,"title":"Quickly excluding an annotated planar graph","domain":"math.CO","source":"arxiv","authors":["Maximilian Gorsky","Evangelos Protopapas","Sebastian Wiederrecht"],"reviews":0,"subject":"math.CO","summary":"We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common generalisation of both treewidth and the face-cover-number of vertex sets in planar graphs. As such, it plays a crucial role in extensions of Courcelle's Theorem to $H$-minor-free graphs. Recently, bidimensionality and similar parameters have emerged as key for extensions of known parameterized algorithms for problems defined on a terminal set $R$. A prominent example for such a problem is Steiner Tree, which admits…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-06","reactions":{}}