Computing a transitive completion / path existence oracle
Compact reachability oracles exist for planar graphs,

Mikkel Thorup: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004)

but are "hard" for general graphs (even sparse graphs)

Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011)

Nevertheless, there is an algorithm that can compute a close-to-optimal reachability labeling 

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Reachability and Distance Queries via 2-Hop Labels. SIAM J. Comput. 32(5): 1338-1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algorithms for Hub Label Optimization. ICALP 2013: 69-80

Building on the work of Cohen et al. and others, there is quite a bit of applied research (database community) see e.g.

Ruoming Jin, Guan Wang: Simple, Fast, and Scalable Reachability Oracle. PVLDB 6(14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. CIKM 2013: 1601-1606