Cheap and Secure Web Hosting Provider : See Now

[Solved]: Heaviest planar subgraph

, , No Comments
Problem Detail: 

Consider the following problem.

Given: A complete graph with real non-negative weights on the edges.

Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.)

Note: The maximum-weight subgraph will be a triangulation; if the complete graph is on $n$ vertices, it will have $m=3n-6$ edges.

Question: What is the best available algorithm for this problem? What is its time-complexity?

Asked By : Helen F.

Answered By : Juho

This is NP-hard even for weighted complete graphs. For an easy algorithm, you can compute a maximum-weight spanning tree: negate the edge weights and run Kruskal's algorithm. This gives you a performance ratio of 1/3 (a spanning tree has $n-1$ edges, and as you note, a maximum planar subgraph can contain at most $3n-6$ edges). As far as I know, the algorithm in [1] which has a performance ratio at least 25/72 and at most 5/12 has not been considerably improved upon (but see what newer papers reference it).

For complete graphs whose edge weights obey the triangle inequality, the performance ratio of the algorithm in [1] is at least 3/8. The algorithm, I think, is rather involved and can be made to run in $O(m^{3/2}n \log^6 n)$ time on general graphs. There are some simpler variants the authors present as well with different performance ratios, and possibly better runtimes.

[1] Calinescu, G., Fernandes, C. G., Karloff, H., & Zelikovsky, A. (2003). A new approximation algorithm for finding heavy planar subgraphs. Algorithmica, 36(2), 179-205.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback