Suppose a graph must be drawn inside a fixed rectangle with as few edge crossings as possible. Each vertex needs a position, the drawing must be valid, and its cost is the number of crossings. Random sampling tackles this optimization problem by generating complete drawings independently and keeping the cheapest valid one. section 16.0 section 16.1.1
Given a graph, drawing width and height, and a target number of valid runs:
- Choose a random x and y coordinate for every vertex. section 16.1.1
- Reject drawings in which vertices overlap or an edge passes through a vertex that is not its endpoint. Try again until the target number of valid drawings has been evaluated. section 16.1.1
- Count edge intersections in each valid drawing. Save the drawing whenever its count beats the best so far, then return the saved drawing. section 16.1.1
Listing 16.1 Random sampling for minimum crossing number embedding
function randomEmbedding(graph, W, H, runs) #1
kBest ← inf #2
for i in {1..runs} do #3
embedding ← [] #4
for j in {0..|graph.vertices|-1} do #5
x ← random(0, W) #6
y ← random(0, H)
embedding[j] ← (x,y) #7
if not validateEmbedding(embedding, graph) then #8
i--
else
k ← edgeIntersections(graph, embedding) #9
if k < kBest then #10
kBest ← k
embeddingBest ← embedding
return embeddingBest #11
The pseudocode shows the complete generate–validate–score–retain loop, including how an invalid draw does not consume a valid run. section 16.1.1
This is a heuristic, not a guarantee of the minimum crossing count. More independent attempts improve the chance of finding a good drawing, but may revisit the same candidate; a large solution space can remain difficult to search. Unlike local optimization, sampling does not adjust a candidate after generating it. Its selection rule needs a cost for each candidate, not a smooth path toward lower cost. section 16.2.3 section 16.2
For n vertices and m edges, the shown validation checks vertex pairs and edge–vertex combinations; counting crossings checks edge pairs. Thus, apart from the context-dependent geometry tests, each attempt takes O(n² + mn + m²) time. The coordinate array and saved best drawing use O(n) additional space. Rejection can require extra attempts, so a target of R valid runs does not impose a fixed bound on total attempts. section 16.1.1
The same idea can supply random proposed moves inside a larger search algorithm. Pure random moves in simulated annealing can reach distant regions, but may need many attempts to find a downhill transition; local sampling can instead test nearby changes. Those methods add an update process that standalone sampling does not have. section 17.1.4 section 18.4.3
