This is my home work problem but i dont have any clue how to proceed with this A “geometric graph” is a special type of graph where the nodes are points on a 2- dimensional surface and edges are straight lines joining pairs of nodes. Show that the minimum spanning tree of such graphs cannot have edges that cross each other (other than at their endpoints).
I have this answer from my algorithm's TA for the same question, let me know if it helps:
The idea is that, if a path contains two edges that cross each other, we can replace those crossing edge with some other edge to get a smaller path.
For example, if there are two edges ac and bd that cross each other, we can replace them with edge ab and cd and get smaller path length.
In geometric graph there is an edge between every pair of vertexes, they also follow triangle inequality.