Contraction-Bidimensionality of Geometric Intersection Graphs

DOI10.4230/LIPIcs.IPEC.2017.5zbMath1448.05048OpenAlexW2795000954MaRDI QIDQ5111864

Dimitrios M. Thilikos, Julien Baste

Publication date: 27 May 2020

Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.5

zbMATH Keywords

string graphsbidimensionalitygeometric intersection graphsgrid-exlusion theorem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Related Items

A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Bidimensionality and Kernels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new proof of the flat wall theorem
• Linearity of grid minors in treewidth with applications through bidimensionality
• Graph minors. V. Excluding a planar graph
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• Tree-width and planar minors
• Contraction obstructions for treewidth
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Optimizing the Graph Minors Weak Structure Theorem
• Graph Minors and Parameterized Algorithm Design
• Dynamic Programming for H-minor-free Graphs
• Bidimensionality of Geometric Intersection Graphs
• Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
• Polynomial Bounds for the Grid-Minor Theorem
• String graphs and separators
• The Bidimensional Theory of Bounded-Genus Graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Contraction Bidimensionality: The Accurate Picture
• Graph minors. II. Algorithmic aspects of tree-width
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Bidimensionality and Geometric Graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Dynamic programming for graphs on surfaces
• Graph Drawing
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
• LATIN 2004: Theoretical Informatics