Planar disjoint-paths completion

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce Planar Disjoint Paths Completion, a completion counterpart of the Disjoint Paths problem, and study its parameterized complexity. The problem can be stated as follows: given a plane graph G, k pairs of terminals, and a face F of G, find a minimum-size set of edges, if one exists, to be added inside F so that the embedding remains planar and the pairs become connected by k disjoint paths in the augmented network. Our results are twofold: first, we give an explicit bound on the number of necessary additional edges if a solution exists. This bound is a function of k, independent of the size of G. Second, we show that the problem is fixed-parameter tractable, in particular, it can be solved in time f(k)•n 2.

Original languageEnglish (US)
Title of host publicationParameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers
Pages80-93
Number of pages14
DOIs
StatePublished - 2012
Event6th International Symposium on Parameterized and Exact Computation, IPEC 2011 - Saarbrucken, Germany
Duration: Sep 6 2011Sep 8 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7112 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Symposium on Parameterized and Exact Computation, IPEC 2011
Country/TerritoryGermany
CitySaarbrucken
Period9/6/119/8/11

Keywords

  • Completion Problems
  • Disjoint Paths
  • Planar Graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Planar disjoint-paths completion'. Together they form a unique fingerprint.

Cite this