Reachability, Routing and Distance Labeling Schemes in Graphs with Applications in Networks and Graph Databases

Three fundamental and related problems, with applications in networks and graph databases, are the focus of this dissertation. They are: how to answer quickly whether a vertex can reach another vertex in a directed graph, using a succinct representation of the reachability information; how to route a message efficiently from a source vertex to a destination vertex and how to calculate or estimate quickly the distance between any two vertices, using very limited information stored locally at those vertices.

To efficiently answer reachability queries, we introduce a novel path-tree structure to assist with the compression of transitive closure and answering reachability queries. Our path-tree generalizes the traditional tree cover approach and can produce a better compression rate for the transitive closure. We also propose a 3-hop indexing scheme with high compression rate targeting the directed graphs with higher edge-vertex ratio. In addition, we show how to effectively summarize reachability information.

To efficiently route messages in a graph, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path close to optimal. We investigate advantages and limitations of these strategies on several families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, and graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.

Finally, we propose distance and routing labeling schemes for circle graphs and polygon graphs by constructing collective additive tree spanners. We show that the family of n-vertex circle graphs admits a 2-additive distance labeling scheme with O(log³n)-bit labels and O(log n) time distance decoder, and the family of n-vertex k-polygon graphs admits a 2-additive distance labeling scheme with O(log k log²n)-bit labels and O(log k) time distance decoder. Similar routing labeling schemes are also designed for these families of graphs.