Planar Disjoint-Paths Completion

DOI10.1007/978-3-642-28050-4_7zbMath1352.68090arXiv1511.04952OpenAlexW1530613230MaRDI QIDQ2891339

Isolde Adler, Dimitrios M. Thilikos, Stavros G. Kolliopoulos

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.04952

zbMATH Keywords

planar graphscompletion problemsdisjoint paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Irrelevant vertices for the planar disjoint paths problem ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Tight Bounds for Linkages in Planar Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of DNA physical mapping
• Graph minors. XIII: The disjoint paths problem
• A shorter proof of the graph minor algorithm
• Tight Bounds for Linkages in Planar Graphs
• Computing the Minimum Fill-In is NP-Complete
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Finding topological subgraphs is fixed-parameter tractable