I need to determine the minimum overlay trees (MSTs) of very large, complete graphs, whose edge weights can be calculated from the data associated with the vertices.

In the plane Euclidean case, for example, the weights of the edges correspond to the Euclidean distances between the points to which the adjacent vertices correspond; in this case, the peak of the MST can not be greater than 6 and it would therefore be sufficient to calculate the MST in the subgraph $ S subseteq G $ this is induced by the 6 edges of the least weight adjacent to each vertex, although this is inferior to calculate the MST of the graph induced by the Delaunay triangulation of the set of points.

Now, my idea would be to assume a reasonable upper limit $ k on the degree of peaks of graphs STS with edge weights that can be calculated deterministically from the information associated with vertices and take and attempt to compute the MST in the subgraph induced by sets of the $ k the shortest edges adjacent to the individual vertices; this would reduce the storage requirements of $ O (n ^ 2) $ at $ O (n) $.

The case where the peak of an STD is greater than the hypothesis assumed $ k can be detected when calculating the MST and, if a vertex "exhausts" adjacent edges, the next $ k the shortest adjacent edges can be determined $ O (n) $ time and added to S to maintain the current algorithm.

**Question:**

Has the problem of STD determination in very large graphs, with deterministically calculated edge weights from vertex data, already been studied and what (free) online resources can be recommended?