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.ISAAC.2018.41
URN: urn:nbn:de:0030-drops-99895
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9989/
Go to the corresponding LIPIcs Volume Portal

Da Lozzo, Giordano ; Rutter, Ignaz

Approximation Algorithms for Facial Cycles in Planar Embeddings

pdf-format:
LIPIcs-ISAAC-2018-41.pdf (0.6 MB)

Abstract

Consider the following combinatorial problem: Given a planar graph G and a set of simple cycles C in G, find a planar embedding E of G such that the number of cycles in C that bound a face in E is maximized. This problem, called Max Facial C-Cycles, was first studied by Mutzel and Weiskircher [IPCO '99, http://dx.doi.org/10.1007/3-540-48777-8_27) and then proved NP-hard by Woeginger [Oper. Res. Lett., 2002, http://dx.doi.org/10.1016/S0167-6377(02)00119-0].
We establish a tight border of tractability for Max Facial C-Cycles in biconnected planar graphs by giving conditions under which the problem is NP-hard and showing that strengthening any of these conditions makes the problem polynomial-time solvable. Our main results are approximation algorithms for Max Facial C-Cycles. Namely, we give a 2-approximation for series-parallel graphs and a (4+epsilon)-approximation for biconnected planar graphs. Remarkably, this provides one of the first approximation algorithms for constrained embedding problems.

BibTeX - Entry

@InProceedings{dalozzo_et_al:LIPIcs:2018:9989,
  author =	{Giordano Da Lozzo and Ignaz Rutter},
  title =	{{Approximation Algorithms for Facial Cycles in Planar Embeddings}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{41:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9989},
  URN =		{urn:nbn:de:0030-drops-99895},
  doi =		{10.4230/LIPIcs.ISAAC.2018.41},
  annote =	{Keywords: Planar Embeddings, Facial Cycles, Complexity, Approximation Algorithms}
}

Keywords: Planar Embeddings, Facial Cycles, Complexity, Approximation Algorithms
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

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