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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.