Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 7
Spanners

1. The graph area. Add/remove points by clicking your mouse.

2. Pseudocode of the greedy algorithm. While the spanner is constructed, appropriate parts of the pseudo code are highlighted.

3. The control panel allows you to set t and start the construction of the t-spanner, in steps or in play mode.

4. The status bar will keep you informed of changes in the applet.

The greedy algorithm - Double applet

Twin graph areas makes it possible to experiment with different values of t on the same set of points. Points plottet in one graph area automatically appear i both areas, kepping the two sets alike.

Functionality like the above applet.

The greedy algorithm - Double applet

The greedy algorithm - Forced edges

Forcing edges to be part of the graph is not a problem using the greedy algorithm. In stead of starting with an empty set of edges, the forced edges are in the set from the beginning.

Functionality like the first applet, with the additional feature that edges can be forced to be in the spanner.

The greedy algorithm - Forced edges

Construction of the Θ-graph

Slideshow visualizing the construction of a Θ-graph.

Construction of the Θ-graph

The Θ-graph

Applet at the website of Petra Specht, University of Magdeburg, Germany.
Construction of Θ-graphs, demonstration of the Θ-walk, and demonstration of how changing the number of cones effect the graph http://isgnw2.cs.uni-magdeburg.de/~petra/TSpanner.html