HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Generating graphs such as found on Sedgewick's Algorithms book on the MST chapters

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
suchthebookgraphsalgorithmsgeneratingfoundmstchapterssedgewick

Problem

I always wondered what the algorithm might be to generate graphs such as those found on Sedgewick's algorithms books (consider the picture on the left):

Could any one point me to the name (or algorithm) that creates such a graph over a 2D region? I am not interested in how to draw it or display it (or in any library).

From all I can see the (x, y) points are probably just randomly generated, but the edges between vertices don't seem to be randomly connecting any two vertices. Maybe the closer two veritces are the bigger the odds of a connection existing between them is?

Thanks

Solution

It appears to be a random geometric graph. Points are placed at random within an area, according to some distribution, and an edge is added between every pair of points whose distance is less than some threshold.

A common case is to distribute the points uniformly at random within the unit square and add edges between all pairs of vertices that are at distance at most $d$ from each other, for some constant $d$. In other cases, the threshold might depend on the number of vertices.

Context

StackExchange Computer Science Q#45033, answer score: 6

Revisions (0)

No revisions yet.