Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.26
URN: urn:nbn:de:0030-drops-64418
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6441/
Chatzidimitriou, Dimitris ; Giannopoulou, Archontia C. ; Maniatis, Spyridon ; Requilé, Clément ; Thilikos, Dimitrios M. ; Zoros, Dimitris
FPT Algorithms for Plane Completion Problems
| pdf-format: |
|
Abstract
The Plane Subgraph (resp. Topological Minor) Completion problem asks, given a (possibly disconnected) plane (multi)graph Gamma and a connected plane (multi)graph Delta, whether it is possible to add edges in Gamma without violating the planarity of its embedding so that it contains some subgraph (resp. topological minor) that is topologically isomorphic to Delta. We give FPT algorithms that solve both problems in f(|E(Delta)|)*|E(\Gamma)|^{2} steps. Moreover, for the Plane Subgraph Completion problem we show that f(k)=2^{O(k*log(k))}.
BibTeX - Entry
@InProceedings{chatzidimitriou_et_al:LIPIcs:2016:6441,
author = {Dimitris Chatzidimitriou and Archontia C. Giannopoulou and Spyridon Maniatis and Cl{\'e}ment Requil{\'e} and Dimitrios M. Thilikos and Dimitris Zoros},
title = {{FPT Algorithms for Plane Completion Problems}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {26:1--26:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6441},
URN = {urn:nbn:de:0030-drops-64418},
doi = {10.4230/LIPIcs.MFCS.2016.26},
annote = {Keywords: completion problems, FPT, plane graphs, topological isomorphism}
}
| Keywords: | completion problems, FPT, plane graphs, topological isomorphism | |
| Seminar: | 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 19.08.2016 |
