The Bidimensional Theory of Bounded-Genus Graphs

DOI10.1137/040616929zbMath1117.05100OpenAlexW1993074114MaRDI QIDQ3440261

Erik D. Demaine, Dimitrios M. Thilikos, Mohammad Taghi Hajiaghayi

Publication date: 22 May 2007

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/040616929

zbMATH Keywords

treewidthgridsgraph minorsgraphs on surfacesgraph contractions

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (18)

A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Graph Minors and Parameterized Algorithm Design ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Unnamed Item ⋮ Parameterized complexity of perfectly matched sets ⋮ Approximation algorithms via contraction decomposition ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Subexponential parameterized algorithms ⋮ Confronting intractability via parameters ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ To Approximate Treewidth, Use Treelength! ⋮ Contraction obstructions for treewidth ⋮ The Parameterized Complexity of Graph Cyclability ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs ⋮ Dynamic programming for graphs on surfaces

This page was built for publication: The Bidimensional Theory of Bounded-Genus Graphs