Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Heaviest planar subgraph

, ,
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.

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.