Space-Efficient Algorithms for Reachability in Geometric Graphs

01/13/2021
by   Sujoy Bhore, et al.
0

The problem of graph Reachability is to decide whether there is a path from one vertex to another in a given graph. In this paper, we study the Reachability problem on three distinct graph families - intersection graphs of Jordan regions, unit contact disk graphs (penny graphs), and chordal graphs. For each of these graph families, we present space-efficient algorithms for the Reachability problem. For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a space-efficient manner and use it to solve the Reachability in polynomial time and O(m^1/2log n) space, where n is the number of Jordan regions, and m is the total number of crossings among the regions. We use a similar approach for chordal graphs and obtain a polynomial-time and O(m^1/2log n) space algorithm, where n and m are the number of vertices and edges, respectively. However, we use a more involved technique for unit contact disk graphs (penny graphs) and obtain a better algorithm. We show that for every ϵ> 0, there exists a polynomial-time algorithm that can solve Reachability in an n vertex directed penny graph, using O(n^1/4+ϵ) space. We note that the method used to solve penny graphs does not extend naturally to the class of geometric intersection graphs that include arbitrary size cliques.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset