2026-08-10T21:59:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9989 2024-03-06T10:45:17Z ddc:004 open_access

Approximation Algorithms for Facial Cycles in Planar Embeddings Da Lozzo, Giordano Rutter, Ignaz Planar Embeddings Facial Cycles Complexity Approximation Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giordano Da Lozzo and Ignaz Rutter 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.41 urn:nbn:de:0030-drops-99895 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.41 eng https://creativecommons.org/licenses/by/3.0/legalcode