Graphs with Distance Guarantees

Abstract

One goal in network design is the construction of sparse networks that guarantee short distances with respect to some given distance requirements. By this, it can be guaranteed, for example, that delays that are incurred by link faults are bounded. An appropriate graph-theoretic model for this is the concept of k-spanners: Given a graph G, a k-spanner of G is a spanning subgraph S, such that the distance between any two vertices in S is at most k times longer than the distance in G. Research in this area has mainly concentrated on two aspects: minimum k-spanners, i.e., k-spanners that contain the fewest edges among all k-spanners, and tree k-spanners, i.e., spanners that are trees. In this thesis, we use k-spanners to model further desirable properties from network design (such as reliability) within a graph-theoretic framework. Our main emphasis is on sparse graphs that guarantee short distances, and we are interested in simple structures and fault-tolerance.