  We survey graph reachability indexing techniques for efficient processing of
graph reachability queries in two types of popular graph models: plain graphs
and edge-labeled graphs. Reachability queries are fundamental in graph
processing, and reachability indexes are specialized data structures tailored
for speeding up such queries. Work on this topic goes back four decades -- we
include 33 of the proposed techniques. Plain graphs contain only vertices and
edges, with reachability queries checking path existence between a source and
target vertex. Edge-labeled graphs, in contrast, augment plain graphs by adding
edge labels. Reachability queries in edge-labeled graphs incorporate path
constraints based on edge labels, assessing both path existence and compliance
with constraints.
  We categorize techniques in both plain and edge-labeled graphs and discuss
the approaches according to this classification, using existing techniques as
exemplars. We discuss the main challenges within each class and how these might
be addressed in other approaches. We conclude with a discussion of the open
research challenges and future research directions, along the lines of
integrating reachability indexes into graph data management systems. This
survey serves as a comprehensive resource for researchers and practitioners
interested in the advancements, techniques, and challenges on reachability
indexing in graph analytics.
