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):

enter image description here

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?



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.


Perhaps they generate points at random, and have a fraction of the arcs to "at distance $d$" nodes, or even some probability of a link that (strongly) decreases with distance. You'd have to experiment (and probably they fooled around until some "pleasant" image resulted). Or it is maybe a sliver of a larger graph (say roads between cities). If I was writing a book, I certainly would try several approaches (as the ones I suggest) and select the "nicest" one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.