FPT algorithms for plane completion problems

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

doi:10.4230/LIPIcs.MFCS.2016.26

FPT algorithms for plane completion problems

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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(Δ)² steps. Moreover, for the Plane Subgraph Completion problem we show that f(k) = 2^{O(k log k)}.

Original language	English (US)
Title of host publication	41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Editors	Anca Muscholl, Piotr Faliszewski, Rolf Niedermeier
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959770163
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2016.26
State	Published - Aug 1 2016
Event	41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krakow, Poland Duration: Aug 22 2016 → Aug 26 2016

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	58
ISSN (Print)	1868-8969

Conference

Conference	41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Country/Territory	Poland
City	Krakow
Period	8/22/16 → 8/26/16

Keywords

Completion problems
FPT
Plane graphs
Topological Isomorphism

ASJC Scopus subject areas

Software

Access to Document

10.4230/LIPIcs.MFCS.2016.26

Cite this

Chatzidimitriou, D., Giannopoulou, A. C., Maniatis, S., Requilé, C., Thilikos, D. M., & Zoros, D. (2016). FPT algorithms for plane completion problems. In A. Muscholl, P. Faliszewski, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 Article 26 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 58). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2016.26

FPT algorithms for plane completion problems. / Chatzidimitriou, Dimitris; Giannopoulou, Archontia C.; Maniatis, Spyridon et al.
41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. ed. / Anca Muscholl; Piotr Faliszewski; Rolf Niedermeier. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. 26 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 58).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chatzidimitriou, D, Giannopoulou, AC, Maniatis, S, Requilé, C, Thilikos, DM & Zoros, D 2016, FPT algorithms for plane completion problems. in A Muscholl, P Faliszewski & R Niedermeier (eds), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016., 26, Leibniz International Proceedings in Informatics, LIPIcs, vol. 58, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Krakow, Poland, 8/22/16. https://doi.org/10.4230/LIPIcs.MFCS.2016.26

Chatzidimitriou D, Giannopoulou AC, Maniatis S, Requilé C, Thilikos DM, Zoros D. FPT algorithms for plane completion problems. In Muscholl A, Faliszewski P, Niedermeier R, editors, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. 26. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2016.26

Chatzidimitriou, Dimitris ; Giannopoulou, Archontia C. ; Maniatis, Spyridon et al. / FPT algorithms for plane completion problems. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. editor / Anca Muscholl ; Piotr Faliszewski ; Rolf Niedermeier. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{dcf44cc95663401bac1ba94bda3077e0,

title = "FPT algorithms for plane completion problems",

abstract = "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).",

keywords = "Completion problems, FPT, Plane graphs, Topological Isomorphism",

author = "Dimitris Chatzidimitriou and Giannopoulou, {Archontia C.} and Spyridon Maniatis and Cl{\'e}ment Requil{\'e} and Thilikos, {Dimitrios M.} and Dimitris Zoros",

note = "Publisher Copyright: {\textcopyright} Yijia Chen and J{\"u}rg Flum.; 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 ; Conference date: 22-08-2016 Through 26-08-2016",

year = "2016",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.MFCS.2016.26",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Anca Muscholl and Piotr Faliszewski and Rolf Niedermeier",

booktitle = "41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016",

}

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

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 -

FPT algorithms for plane completion problems

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this