## 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, not necessarily connected, 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 upper bound on the number of necessary additional edges when 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 language | English (US) |
---|---|

Pages (from-to) | 401-425 |

Number of pages | 25 |

Journal | Algorithmica |

Volume | 76 |

Issue number | 2 |

DOIs | |

State | Published - Oct 1 2016 |

## Keywords

- Completion problems
- Disjoint paths
- Planar graphs

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics