# Culling edges from a triangulation while maintaining a connected graph?

I'm working on a small project and I'm randomly generating "world maps", with nodes you can fast travel to along given routes.

The basics of this aren't complicated; throw random points on a 2D plane and run a Delaunay triangulation.

However, this leads to quite densely connected maps; there are convenient routes literally everywhere to everywhere.

Here's an example of a standard Delaunay triangulation to show what I mean. (Ignore the dotted lines, as these represent the Voronoi diagram which I'm not interested in.)

I'd like some places to be "harder" to get to, forcing along certain routes. I still need the graph to be connected; that is, there must be a route of edges from any given node to any other given node. But I'd like less "connection density".

Here's an example I've made by removing some edges at random from the above triangulation.

My current theory is to randomly cull edges from the triangulation, but this runs the risk of making the graph "disconnected"; creating nodes that cannot be reached.

Is there a better way to achieve this? I feel like randomly culling and then checking for connectivity every time is kind of inefficient.

• Please define what you mean in precise mathematical terms by a "fully connected graph"; MathWorld defines it as a synonym for "complete graph" which is clearly not what you are referring to. Commented Oct 16, 2023 at 9:53
• That's fair, I've added some clarification and some diagrams to help :) Sorry it's not in precise mathsy terms, I'm not a mathematician. I hope this helps. Commented Oct 16, 2023 at 10:45
• That would just be a connected graph. Commented Oct 16, 2023 at 10:49
• Maybe post it to gamedev.stackexchange.com ? They have more experience with random content generation in games. Commented Oct 16, 2023 at 10:52
• Could work with edge weights instead of deleting them, make them very "thin" or very "fat"? Commented Oct 16, 2023 at 14:10

Approach #1:

Start with all the nodes and no edges at all, then incrementally add nodes and edges to the graph until all nodes are connected.

Just start with an initial graph by one arbitrary edge between two nodes. The outer boundary of that graph are all nodes which currently do not belong to the graph, but have a connection in your Delauny triangulation to it by one edge. Pick one of the nodes of the boundary randomly, and one of the edges which can connect it to the graph, then add both to the current graph. Now repeat this procedure until your graph is complete.

If the graph is "not connected enough" for your purpose, you might add further edges afterwards randomly - for example, to reduce the number of dead ends.

Approach #2:

Start with no edges. Keep a list of all "connectivity components" (the nodes forming a connected subgraph). At the beginning, each component contains only one node.

Then, add edges randomly. When adding an edge between two nodes in different components, merge those two components - all the nodes are now connected. The number of components will be reduced by one in this case. When the total number of components reaches 1, the algorithm can stop.

Approach #3

Start with the full graph, cull edges randomly and then check for connectivity - but try to do this efficiently.

When you remove one edge between node A and B from a connected graph, you usually don't have to run a connectivity scan for the full graph. It is sufficient to test if there is still a route from A to B. For this, you may use something like the A* algorithm. As long as there is a route from A to B, you can expect the algorithm not having to visit all nodes and edges. When there is no such route, it will, however, have to visit all nodes inside the connectivity component where the starting point belongs to.

There is a loss function that this use case seeks to define.

Let "distance" measure the shortest path through the graph connecting a pair of nodes.

Let "distance ratio distribution" describe what that looks like across all node pairs, normalized by crow flies distance (L2 norm Euclidean distance). It is a measure of how inefficient the shortest graph path is, relative to the shortest flight of a crow. No node is more important than any other, since we choose them uniformly at random.

this leads to quite densely connected maps; there are convenient routes literally everywhere to everywhere.

Put another way, the distance ratio distribution is too compact. Its min, median, average, and max are all just slightly above unity. We have constructed a very small world planar graph.

I'd like some places to be "harder" to get to, ... I'd like less "connection density".

In a "large" Delaunay triangulation, essentially all nodes are interior nodes. Such nodes have degree >= 5. We will consider nodes of lesser degree to be peripheral nodes.

Controlling the degree of interior nodes impresses me as your central issue.

# build a graph

Mark nodes in your Delaunay triangulation as "peripheral" or "interior".

Choose a `max_degree` threshold parameter of degree `3`. The degree of most nodes will not exceed the threshold.

Initialize a new graph with no edges. Produce a set of connected components. We will stop adding edges when there's a single connected component. Keep track of number of nodes in each component.

Iterate over all peripheral nodes, assigning each one a single new edge. Merge connected components as you go.

Now loop until we have just one component. Choose a candidate (empty) edge at random, and examine its two nodes to see if we should add it. Perform several rejection tests, looping back if any test fails:

• both nodes are in same component? --> reject
• compare the sizes of each node's component
• equal sizes, and both nodes have degree >= max_degree? --> reject
• node in smaller component has degree >= max_degree? --> reject

The idea is there will be one growing giant "rich get richer" component that peripheral components will need to attach to. So as an escape valve, a few of its nodes may need a slightly elevated degree. We might limit them to `max_degree + 1`. Also, using probabilistic comparisons, against max_degree + random, would offer a further tuning knob.

Having connected all nodes in that way, you can now compute the distance ratio distribution to see if you're happy with it, choosing to start over if not.

Pick a geographically central node. Then you can compute average distance to peripheral nodes. You can also compute standard measures like graph diameter. Both of these will matter to your players if they have resource constraints like a fixed-size vehicle gas tank.