I/O-efficient algorithms for shortest path related problems

In this thesis, we study I/O-efficient algorithms for problems related to computing shortest paths in outerplanar and planar graphs and in spanner graphs for point sets in d-dimensional space and sets of obstacles in the plane.; In particular, we show in the first part of the thesis that the following problems can be solved in sorting complexity or even in a linear number of I/Os: outerplanarity testing, outerplanar embedding, planarity testing, planar embedding, computing optimal ϵ-separators of planar and outerplanar graphs, breadth-first search; depth-first search, and single source shortest paths on planar and outerplanar graphs.; In the second part of the thesis, we show that the well-separated pair decomposition of [37] can be computed in sorting complexity. We use this decomposition to construct two types of Euclidean spanners of linear size for point sets in d dimensions. The first spanner is derived in a natural manner from the well-separated pairs in the decomposition. The second spanner is a supergraph of the first spanner. The particular structure of this spanner makes it possible to construct a data structure which can be used to report spanner paths in an I/O-efficient manner. For sets of polygonal obstacles in the plane, we use a subdivision derived from the fair split tree of a point set to compute a planar Steiner spanner of the set of obstacles. Given the results from the first part of the thesis and results from [2, 100, 177]; the planarity of the graph can be exploited to compute spanner paths I/O-efficiently and to preprocess the graph so that shortest path queries can be answered and paths in the graph can be traversed in an I/O-efficient manner.; As part of the results in Part I of the thesis; we present improved and much simplified algorithms for computing maximal matchings and maximal independent sets of general undirected graphs. As an additional application of the well-separated pair decomposition, which is at the core of the algorithms presented in Part II, we obtain nearly I/O-optimal algorithms for solving the K-nearest neighbor and K-closest pair problems for point sets in d dimensions.