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

Graphs are mathematical constructs consisting of vertices and edges.

Many computational problems can be expressed as graph problems. For example, planning a route between subway stations translates into finding a path between to vertices of a graph. Another example is planning pipe lines between oil rigs, which corresponds to creating a graph connecting a set of vertices.

Figure 1: Graphs representing real life scenarios

The Copenhagen metro system, expressed as a graph.

Why is this clever?

You may be familiar with algorithms for solving shortest path or minimum spanning tree problems. The benefits of this kind of translation of real-life problems into graph problems include access to a wide range of effective algorithms. Graph representations thus allow for fast and reliable problem solving.

The t-spanner

This site is dedicated the a special kind of graph, namely the t-spanner.
The t-spanner is used to solve problems where a set of vertices need to be connected in such a way, that the shortest path between any two vertices is bounded.

This site will introduces some of the algorithms needed to construct t-spanners, as well as examples of real life problems where the t-spanner is useful.

The t-spanner is primarily used to model geometric objects. For simplicity, this presentation considers vertices to be points in a two dimensional space. The described algorithms do, however, work equally well in other dimensions.

As the graph represents a geometric object, the weight of an edge between two vertices equals the euclidian distance between them.