Heaviest planar subgraph

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.

StackExchange Computer Science Q#40703, answer score: 6