Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions

2005/01/01 by Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Combinatorics #Computer science #Cycle basis #Discrete mathematics #Divide and conquer algorithms #Graph #Hamiltonian path #Mathematics #Maximum cut #Optimization and Search Problems #Parameterized complexity #Planar #Planar graph

paper · doi:10.1007/11561071_11

crossref issued 2005/01/01 · crossref published 2005/01/01 · crossref published-print 2005/01/01 · openalex publication_date 2005/01/01 · crossref created 2005/10/06 · crossref deposited 2021/04/27 · openalex created_date 2025/10/10 · crossref indexed 2026/06/29 · openalex updated_date 2026/07/29

Citations

• Geometric separator theorems and applications
• Applications of a Planar Separator Theorem
• Call routing and the ratcatcher
• A Separator Theorem for Planar Graphs
• Graph minors. X. Obstructions to tree-decomposition
• Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
• New upper bounds on the decomposability of planar graphs
• Quickly Excluding a Planar Graph
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Tour Merging via Branch-Decomposition
• Parameterized Complexity

Cited by

• Planar separator theorem [wikipedia]