2026-08-07T10:29:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21109 2024-09-23T09:13:17Z ddc:004 open_access

Local Optimization Algorithms for Maximum Planar Subgraph Călinescu, Gruia Uniyal, Sumedha planar graph maximum subgraph approximation algorithm matroid parity local optimization Consider the NP-hard problem of, given a simple graph G, to find a planar subgraph of G with the maximum number of edges. This is called the Maximum Planar Subgraph problem and the best known approximation is 4/9 and is obtained by sophisticated Graphic Matroid Parity algorithms. Here we show that applying a local optimization phase to the output of this known algorithm improves this approximation ratio by a small {ε} = 1/747 > 0. This is the first improvement in approximation ratio in more than a quarter century. The analysis relies on a more refined extremal bound on the Lovász cactus number in planar graphs, compared to the earlier (tight) bound of [Gruia Călinescu et al., 1998; Chalermsook et al., 2019]. A second local optimization algorithm achieves a tight ratio of 5/12 for Maximum Planar Subgraph without using Graphic Matroid Parity. We also show that applying a greedy algorithm before this second optimization algorithm improves its ratio to at least 91/216 < 4/9. The motivation for not using Graphic Matroid Parity is that it requires sophisticated algorithms that are not considered practical by previous work. The best previously published [Chalermsook and Schmid, 2017] approximation ratio without Graphic Matroid Parity is 13/33 < 5/12. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gruia Călinescu and Sumedha Uniyal 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.38 urn:nbn:de:0030-drops-211090 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.38 eng https://creativecommons.org/licenses/by/4.0/legalcode