# Reduce the number of edges of a graph, keeping it connected

I'm designing a game with random generated dungeons. I'd like to view this as a connected, undirected graph in which nodes are rooms and edges are doors or corridors. Then I choose a "side" node as the dungeon entrance, I calculate the distance between this entrance and all other nodes, and decide that one of the farthest nodes is the "goal" of the dungeon (the location of the treasure, boss, princess, etc.).

I saw 2 ways to generate the final dungeon topography:

• Generate first a random graph, then try to fill the 2d world with rooms at random locations, respecting the edge connections. I figured this would be sometimes difficult because the room generation could be "locked" trying to fit rooms in impossible places.
• Generate first rooms, placing them randomly where they fit, then map the result to nodes and edges. I decided to try this.

My idea consists in :

• First generate a big room that would contain the whole dungeon.
• Put a wall inside the big room, at a random location, dividing the big room into 2 smaller rooms of different area.
• Then I continue to divide each room into 2, until they are too small, or the total number of room reach a maximum (or any other condition). Each new room is a node.
• Once finished, I check each room and find all adjacent other rooms, marking the 2 nodes as connected by an edge.

That way I ensure that all rooms have a possible location in the 2D world, and are correctly mapped by a connected graph.

My problem is that there are too many doors and corridors connecting the rooms.

So I'd like an algorithm that reduces the number of edges of a connected undirected graph, but keeping it connected (all nodes stay reachable) in the end.

• Your idea is basically a binary search tree, if you want to know. I used it; it does make rather nice dungeons and is easy. :) Commented Nov 22, 2010 at 19:01
• FYI: A complete graph has edges between all pairs of vertices, so (assuming duplicate edges are not allowed) you can't remove any edges and still have a complete graph. The right term is a connected graph. Commented Nov 22, 2010 at 20:16
• Binary search tree, connected graph, right. I'm so bad with conventional name of things.
– Splo
Commented Nov 23, 2010 at 8:53