Fast minor testing in planar graphs
From MaRDI portal
Publication:1759679
DOI10.1007/s00453-011-9563-9zbMath1254.05185OpenAlexW1994533463WikidataQ56235104 ScholiaQ56235104MaRDI QIDQ1759679
Dimitrios M. Thilikos, Ignasi Sau, Frederic Dorn, Isolde Adler, Fedor V. Fomin
Publication date: 21 November 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904515/file/Minor-planar.pdf
algorithmdynamic programmingplanar graphsmodelparameterized complexitygraph minorsbranchwidthminor containment problem
Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Minor embedding in broken chimera and derived graphs is NP-complete
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Subexponential parameterized algorithms
- Graph minors. XX: Wagner's conjecture
- Treewidth lower bounds with brambles
- Linearity of grid minors in treewidth with applications through bidimensionality
- Call routing and the ratcatcher
- Quickly excluding a planar graph
- On search, decision, and the efficiency of polynomial-time algorithms
- On random planar graphs, the number of planar graphs and their triangulations
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Graph minors. XIII: The disjoint paths problem
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- A shorter proof of the graph minor algorithm
- Planar Subgraph Isomorphism Revisited
- A Census of Planar Triangulations
- Faster Parameterized Algorithms for Minor Containment
- Fast Minor Testing in Planar Graphs
- Dynamic Programming for Graphs on Surfaces
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Applications of a Planar Separator Theorem
- Approximation algorithms for NP-complete problems on planar graphs
- Color-coding
- Branch decompositions and minor containment
- On Hamilton cycles in certain planar graphs
- Hadwiger's conjecture is decidable
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
