Bhore, Sujoy ;
Jain, Rahul
SpaceEfficient Algorithms for Reachability in Directed Geometric Graphs
Abstract
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 spaceefficient algorithms for the Reachability problem.
For intersection graphs of Jordan regions, we show how to obtain a "good" vertex separator in a spaceefficient manner and use it to solve the Reachability in polynomial time and O(m^{1/2} log 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/2} log n) space algorithm, where n and m are the number of vertices and edges, respectively. However, for unit contact disk graphs (penny graphs), we use a more involved technique 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.
BibTeX  Entry
@InProceedings{bhore_et_al:LIPIcs.ISAAC.2021.63,
author = {Bhore, Sujoy and Jain, Rahul},
title = {{SpaceEfficient Algorithms for Reachability in Directed Geometric Graphs}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {63:163:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15496},
URN = {urn:nbn:de:0030drops154961},
doi = {10.4230/LIPIcs.ISAAC.2021.63},
annote = {Keywords: Reachablity, Geometric intersection graphs, Spaceefficient algorithms}
}
30.11.2021
Keywords: 

Reachablity, Geometric intersection graphs, Spaceefficient algorithms 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 