Question: I have a graph where each node has a spatial position given by (x,y), and the edges between the nodes are only connected if the euclidean distance between each node is sqrt(2) or less. Here's my example: import networkx G=nx.Graph() G.add_node(1,pos=(1,1)) G.add_node(2,pos=(2,2)) G.add_node(3,pos=(1,2)) G.add_node(4,pos=(1,4)) G.add_node(5,pos=(2,5)) G.add_node(6,pos=(4,2)) G.add_node(7,pos=(5,2)) G.add_node(8,pos=(5,3)) # Connect component one G.add_edge(1,2) G.add_edge(1,3) G.add_edge(2,3) # Connect component two G.add_edge(6,7) # Connect component three G.add_edge(6,8) G.add_edge(7,8) G.add_edge(4,5) pos=nx.get_node_attributes(G,'pos') nx.draw(G,pos)   My question is, how can I determine the optimal position and number of additional nodes such that the graph components are connected, whilst ensuring that any additional node is always within sqrt(2) of an existing node?

Answer: I am quite convinced that this problem is NP-hard. The closest problem I know is the geometric Steiner tree problem with octilinear metric. I have two, rather quick-and-dirty, suggestions. Both are heuristic. 1st idea: Formulate the problem as an Euclidean Steiner tree problem (https://en.wikipedia.org/wiki/Steiner_tree_problem#Euclidean_Steiner_tree), where you consider just the nodes of your problem and forget about the edges at first. Solve the problem by using GeoSteiner: http://www.geosteiner.com/ This should quickly give you a solution for problems with 10000 or more nodes (if you need to solve bigger problems, you can write the problem out with GeoSteiner after the full-Steiner tree generation and use https://scipjack.zib.de/). There is no Python interface, but just write your problem to a plain text file, the syntax is quite easy. Afterward, put additional nodes into the solution provided by GeoSteiner such that the \sqrt(2) condition is satisfied. Finally, you need to do some clean-up to get rid of redundant edges, because the solution will not take into account that you already have edges in your original problem. Take all the edges and nodes that you have computed so far and define a weighted graph by giving all of your original edges weight 0 and all of the newly added edges weight 1. Consider a Steiner tree problem in graphs (https://en.wikipedia.org/wiki/Steiner_tree_problem#Steiner_tree_in_graphs_and_variants) on this weighted graph, where the terminal set corresponds to your original nodes. Solve this Steiner tree problem with SCIP-Jack: https://scipjack.zib.de/. 2nd idea: Consider your problem directly as a Steiner tree problem in graphs as follows: Each of the original edges is assigned weight 0, consider all original nodes as terminals. Add additional nodes and edges at distance at most \sqrt(2) from each other. For example, you could put a big rectangle around all your connected components and from each node add recursively additional 8 nodes in an angle at degrees 0,45,90,... at a distance of sqrt(2) and with edge of weight 1 in the Steiner tree problem in graphs, as long as they are within the rectangle. If one of these nodes is within distance sqrt(2) of one of your original nodes, connect them directly with an edge of weight 1. Solve the corresponding Steiner tree problem in graphs with SCIP-Jack.