Warning: Undefined variable $PHP_SELF in /customers/5/e/4/ca9mr3fcm/webroots/www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/5/e/4/ca9mr3fcm/webroots/www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/5/e/4/ca9mr3fcm/webroots/www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/5/e/4/ca9mr3fcm/webroots/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.
