Visualization of Spanners

Visualization of Spanners - The Applet

The applet can be used to visualize the geographic neighborhood graph and the theta-graph. The following functions are supported:

a point can be added by clicking the left mouse button.
five random points can be added by clicking the "+5"-button.
a point can be deleted by clicking the right mouse button.
a point can be moved by dragging the left mouse button.
the number of cones can be set.
show cones: by clicking on a point, the cones around this point are shown.
direction of edges: the definition of the spanners define directed graphs in a natural way. This option can be used to show the graphs as a directed or an undirected graph.

After selecting two points P and Q, the following options are offered.

spanner path P -> Q: Shows the spanner path from P to Q as constructed using the algorithm given in Section 2.2. The graph is considered as being directed.
spanner path Q -> P: Shows the spanner path from Q to P as constructed using the algorithm given in Section 2.2. The graph is considered as being directed.
shortest path P -> Q: Shows the shortest path from P to Q. The graph is considered as being directed.
shortest path Q -> P: Shows the shortest path from Q to P. The graph is considered as being directed.
shortest undirected path: Shows the shortest path between P and Q. The graph is considered as being undirected.

For each path, the applet gives the following information.

theoretical upper bound on stretch factor: The value of t = 1 / (1 - 2 sin(theta / 2)), where theta is equal to 2 pi divided by the number of cones.
stretch factor graph: The actual stretch factor of the graph.
stretch factor path: The length of the path divided by the Euclidean distance between P and Q.
path with maximum sf: shows two points whose stretch factor is maximum, together with the corresponding path

After clicking on "enter demo'', there are the following options.

create graph: By clicking on a point, it is shown how the edges starting at this point are found.
spanner path: After selecting two points P and Q, the algorithm that constructs a spanner between them is animated.
both algorithms can be visualized in "step mode'' (each click on the step button shows one step of the algorithm) or in "run mode'' (one click starts the entire algorithm).