The Bidimensional Theory of Bounded-Genus Graphs

DOI10.1137/040616929MaRDI QIDQ3440261zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Dimitrios M. Thilikos, Mohammad T. 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

treewidthgraph minorsgridsgraphs on surfacesgraph contractions

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2004
• A separator theorem for graphs of bounded genus
• \(\ell^2\)-Betti numbers and the genus of a graph
• scientific article; zbMATH DE number 3939383
• On the number of genus embeddings of complete bipartite graphs
• On the number of genus embeddings of complete bipartite graphs
• On the orientable genus of graphs with bounded nonorientable genus
• Varieties of graphoids and Birkoff's theorem for graphs
• scientific article; zbMATH DE number 1501715
• Bounding the cop number of a graph by its genus

Cited in

(29)

• Bidimensional Parameters and Local Treewidth
• Computational study on bidimensionality theory based algorithm for longest path problem
• Confronting intractability via parameters
• Linearity of grid minors in treewidth with applications through bidimensionality
• To approximate treewidth, use treelength!
• Contraction bidimensionality of geometric intersection graphs
• Bidimensionality and parameterized algorithms (invited talk)
• Contraction obstructions for treewidth
• Parameterized complexity of perfectly matched sets
• scientific article; zbMATH DE number 6297701 (Why is no real title available?)
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Contraction-bidimensionality of geometric intersection graphs
• A Retrospective on (Meta) Kernelization
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Stronger ILPs for the Graph Genus Problem.
• Graph minors and parameterized algorithm design
• Algorithmic Graph Minors and Bidimensionality
• Mathematical Foundations of Computer Science 2004
• Bidimensionality of geometric intersection graphs
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
• Graph Drawing
• Contraction Bidimensionality: The Accurate Picture
• Subexponential parameterized algorithms
• What's next? Future directions in parameterized complexity
• Dynamic programming for graphs on surfaces
• Bidimensionality and kernels
• Approximation algorithms via contraction decomposition

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3440261)