Tight Bounds for Linkages in Planar Graphs

DOI10.1007/978-3-642-22006-7_10zbMath1333.05280OpenAlexW167453680MaRDI QIDQ3012796

Dimitrios M. Thilikos, Philipp Klaus Krause, Saket Saurabh, Daniel Lokshtanov, Isolde Adler, Stavros G. Kolliopoulos

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_10

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Planar Disjoint-Paths Completion ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Planar disjoint-paths completion ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ Kernel bounds for path and cycle problems ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Explicit bounds for graph minors ⋮ The Parameterized Complexity of Graph Cyclability ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ A lower bound on the tree-width of graphs with irrelevant vertices ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graph minors. XXI. graphs with unique linkages
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem
• Lower bounds on the pathwidth of some grid-like graphs
• A shorter proof of the graph minor algorithm
• Odd cycle packing
• Planar Disjoint-Paths Completion
• Domination Problems in Nowhere-Dense Classes
• The Induced Disjoint Paths Problem
• Induced Packing of Odd Cycles in a Planar Graph
• Finding k Disjoint Paths in a Directed Planar Graph

This page was built for publication: Tight Bounds for Linkages in Planar Graphs