Contraction bidimensionality of geometric intersection graphs

DOI10.1007/s00453-021-00912-wOpenAlexW4220976255MaRDI QIDQ832527

Julien Baste, Dimitrios M. Thilikos

Publication date: 25 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8548/

zbMATH Keywords

treewidthparameterized algorithmsbidimensionality

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• 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
• Towards tight(er) bounds for the excluded grid theorem
• Tree-width and planar minors
• Contraction obstructions for treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by 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
• String graphs and separators
• Easy problems for tree-decomposable graphs
• 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
• Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes
• Contraction-Bidimensionality of Geometric Intersection Graphs
• Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
• Bidimensional Parameters and Local Treewidth
• Bidimensionality and Parameterized Algorithms (Invited Talk)
• 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

This page was built for publication: Contraction bidimensionality of geometric intersection graphs