TY - GEN

T1 - Planar disjoint-paths completion

AU - Adler, Isolde

AU - Kolliopoulos, Stavros G.

AU - Thilikos, Dimitrios M.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Completion Problems

KW - Disjoint Paths

KW - Planar Graphs

UR - http://www.scopus.com/inward/record.url?scp=84858376541&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858376541&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28050-4_7

DO - 10.1007/978-3-642-28050-4_7

M3 - Conference contribution

AN - SCOPUS:84858376541

SN - 9783642280498

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 80

EP - 93

BT - Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Revised Selected Papers

T2 - 6th International Symposium on Parameterized and Exact Computation, IPEC 2011

Y2 - 6 September 2011 through 8 September 2011

ER -