The Θ-graph is a spanner constructed by extending edges from each vertex in several different directions. In general, adding edges in more directions will result in a lower stretch factor. When the number of directions has been decided, an upper bound can be made on the stretch factor. Thus the Θ-graph is a t-spanner with t depending on the number of directions.

Figure 8: The Θ-graph

The Θ-graph with marked cones for one of the vertices.

The scheme

The Θ-graph is based on the idea that, when you wish to go somewhere, it is sufficient to go in the general direction of the destination. As long as the route keeps taking you closer to your destination, you will reach it at some point.

The Θ-graph is constructed by dividing the space around each vertex into, say 10, different cone-shaped sub-spaces and adding an edge to one of the closest neighbour vertices in each sub-space. Using these edges it is always possible to travel in the general direction of a destination vertex.

Cones

The space around each vertex is divided into κ (kappa) equal-sized cones, κ being any whole number above 0. Each division is done by adding a ray emanating from the vertex. In each of the cones containing other vertices, an edge is added to one of these vertices. This process is repeated for every cone of every vertex.

For κ=2 the created graph is guaranteed to be a spanner, but only for κ≥9 is it certain that the travelling scheme outlined above keeps getting you closer to your destination.