I am looking for information about the problem of identifying the heaviest minimal subset $F\subset E$ of the edgeset $E$ of a complete symmetric graph $G(V,E)$ with randomly weighted edges such that $G\setminus F$ has a given topology, e.g. is planar, and a triangulation, i.e. every remaining edge is an edge of a 3-cycle.
An exemplary problem would be to find a triangulation of a complete graph, whose vertices resemble points on a torus and edge weigths equal to euclidean distance, that allows for a planar embedding.
Being able to calculate the lightest planar triangulation of graphs with arbitrarily weighted edges would e.g. yield a meaningful definition of the planar convex hull of such graphs and thus yield an initial tour that can be expanded to a lightest Hamilton cycle by successive integration of vertices.
