I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.The number of vertices with no edges is small in comparison to the total number of vertices. No vertex has more than two edges connected to it.How can I convert this graph to a closed shape, so each vertex will have exactly two edges connected to it and there will be a path between any two vertices? I want to do it with minimum change in the total weight of all the edges.
Converting graphs to sets of paths
algorithms;graphs;graph traversal;weighted graphs