TY - GEN

T1 - FPT algorithms for plane completion problems

AU - Chatzidimitriou, Dimitris

AU - Giannopoulou, Archontia C.

AU - Maniatis, Spyridon

AU - Requilé, Clément

AU - Thilikos, Dimitrios M.

AU - Zoros, Dimitris

N1 - Publisher Copyright:
© Yijia Chen and Jürg Flum.

PY - 2016/8/1

Y1 - 2016/8/1

N2 - The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph T and a connected plane (multi)graph Δ, whether it is possible to add edges in T without violating the planarity of its embedding so that it contains some subgraph (resp. Topological minor) that is topologically isomorphic to Δ. We give FPT algorithms that solve both problems in f(E(Δ)) E(Δ)2 steps. Moreover, for the Plane Subgraph Completion problem we show that f(k) = 2O(k log k).

AB - The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph T and a connected plane (multi)graph Δ, whether it is possible to add edges in T without violating the planarity of its embedding so that it contains some subgraph (resp. Topological minor) that is topologically isomorphic to Δ. We give FPT algorithms that solve both problems in f(E(Δ)) E(Δ)2 steps. Moreover, for the Plane Subgraph Completion problem we show that f(k) = 2O(k log k).

KW - Completion problems

KW - FPT

KW - Plane graphs

KW - Topological Isomorphism

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

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

U2 - 10.4230/LIPIcs.MFCS.2016.26

DO - 10.4230/LIPIcs.MFCS.2016.26

M3 - Conference contribution

AN - SCOPUS:85012937858

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

A2 - Muscholl, Anca

A2 - Faliszewski, Piotr

A2 - Niedermeier, Rolf

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

Y2 - 22 August 2016 through 26 August 2016

ER -