Contraction-bidimensionality of geometric intersection graphs
From MaRDI portal
Publication:5111864
DOI10.4230/LIPICS.IPEC.2017.5zbMATH Open1448.05048OpenAlexW2795000954MaRDI QIDQ5111864FDOQ5111864
Authors: Julien Baste, Dimitrios M. Thilikos 
Publication date: 27 May 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.5
Recommendations
Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)
Cites Work
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Graph minors. V. Excluding a planar graph
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
- Graph minors. II. Algorithmic aspects of tree-width
- Bidimensionality and kernels
- Tree-width and planar minors
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Title not available (Why is that?)
- Contraction Bidimensionality: The Accurate Picture
- Contraction obstructions for treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Title not available (Why is that?)
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- The Bidimensional Theory of Bounded-Genus Graphs
- LATIN 2004: Theoretical Informatics
- Title not available (Why is that?)
- Graph Drawing
- Optimizing the graph minors weak structure theorem
- A new proof of the flat wall theorem
- Graph minors and parameterized algorithm design
- Dynamic Programming for H-minor-free Graphs
- Bidimensionality of Geometric Intersection Graphs
- String graphs and separators
- Dynamic programming for graphs on surfaces
- Title not available (Why is that?)
- Polynomial Bounds for the Grid-Minor Theorem
Cited In (7)
- A Retrospective on (Meta) Kernelization
- Title not available (Why is that?)
- Contraction bidimensionality of geometric intersection graphs
- Bidimensionality and Kernels
- Tractabilities and intractabilities on geometric intersection graphs
- A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
- Title not available (Why is that?)
This page was built for publication: Contraction-bidimensionality of geometric intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111864)
