Finding triangles for maximum planar subgraphs

Parinya Chalermsook*, Andreas Schmid

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Citations (Scopus)

Abstract

In the Maximum Planar Subgraph (Mps) problem, we are given a graph G, and our goal is to find a planar subgraph H with maximum number of edges. Besides being a basic problem in graph theory, Mps has many applications including, for instance, circuit design, factory layout, and graph drawing, so it has received a lot of attention from both theoretical and empirical literature. Since the problem is NP-hard, past research has focused on approximation algorithms. The current best known approximation ratio is 4/9 obtained two decades ago (Călinescu et al. SODA 1996) based on computing as many edge-disjoint triangles in an input graph as possible. The factor of 4/9 is also the limit of this “disjoint triangles” approach. This paper presents a new viewpoint that highlights the essences of known algorithmic results for Mps, as well as suggesting new directions for breaking the 4/9 barrier. In particular, we introduce the Maximum Planar Triangles (Mpt) problem: Given a graph G, compute a subgraph that admits a planar embedding with as many triangular faces as possible. Roughly speaking, any ρ-approximation algorithm for Mpt can easily be turned into a 1/3 + 2ρ/3 approximation for Mps. We illustrate the power of the Mpt framework by “rephrasing” some known approximation algorithms for Mps as approximation algorithms for Mpt (solving Mps as by-products). This motivates us to perform a further rigorous study on the approximability of Mpt and show the following results: – Mpt is NP-hard, giving a simplified NP-hardness proof for Mps as a by-product. – We propose a natural class of greedy algorithms that captures all known greedy algorithms that have appeared in the literature. We show that a very simple greedy rule gives better approximation ratio than all known greedy algorithms (but still worse than 4/9). Our greedy results, despite not improving the approximation factor, illustrate the advantage of overlapping triangles in the context of greedy algorithms. The Mpt viewpoint offers various new angles that might be useful in designing a better approximation algorithm for Mps.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings
Pages373-384
Number of pages12
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventInternational Conference and Workshops on Algorithms and Computation - Hsinchu, Taiwan, Republic of China
Duration: 29 Mar 201731 Mar 2017
Conference number: 11

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10167 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference and Workshops on Algorithms and Computation
Abbreviated titleWALCOM
Country/TerritoryTaiwan, Republic of China
CityHsinchu
Period29/03/201731/03/2017

Fingerprint

Dive into the research topics of 'Finding triangles for maximum planar subgraphs'. Together they form a unique fingerprint.

Cite this