License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6441/
Go to the corresponding LIPIcs Volume Portal

Chatzidimitriou, Dimitris ; Giannopoulou, Archontia C. ; Maniatis, Spyridon ; Requilé, Clément ; Thilikos, Dimitrios M. ; Zoros, Dimitris

FPT Algorithms for Plane Completion Problems

pdf-format:
LIPIcs-MFCS-2016-26.pdf (0.6 MB)

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
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI