The Bidimensional Theory of Bounded-Genus Graphs
From MaRDI portal
Publication:3440261
DOI10.1137/040616929zbMATH Open1117.05100OpenAlexW1993074114MaRDI QIDQ3440261FDOQ3440261
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
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 (30)
- Computational study on bidimensionality theory based algorithm for longest path problem
- A Retrospective on (Meta) Kernelization
- Contraction bidimensionality of geometric intersection graphs
- Bidimensional Parameters and Local Treewidth
- Title not available (Why is that?)
- Linearity of grid minors in treewidth with applications through bidimensionality
- Algorithmic Graph Minors and Bidimensionality
- Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
- What's next? Future directions in parameterized complexity
- Graph minors and parameterized algorithm design
- Contraction Bidimensionality: The Accurate Picture
- Bidimensionality and parameterized algorithms (invited talk)
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Bidimensionality of geometric intersection graphs
- The parameterized complexity of graph cyclability
- Mathematical Foundations of Computer Science 2004
- Contraction obstructions for treewidth
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Title not available (Why is that?)
- Parameterized complexity of perfectly matched sets
- Stronger ILPs for the Graph Genus Problem.
- Approximation algorithms via contraction decomposition
- To approximate treewidth, use treelength!
- Title not available (Why is that?)
- Graph Drawing
- Contraction-Bidimensionality of Geometric Intersection Graphs
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Dynamic programming for graphs on surfaces
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)
