2026-07-23T10:09:41Z https://drops.dagstuhl.de/oai

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

A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs Chalermsook, Parinya Schmid, Andreas Uniyal, Sumedha Graph Drawing Matroid Matching Maximum Planar Subgraph Local Search Algorithms A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parinya Chalermsook and Andreas Schmid and Sumedha Uniyal 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.19 urn:nbn:de:0030-drops-102583 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.19 eng https://creativecommons.org/licenses/by/3.0/legalcode