Constant-Time Reachability in DAGs Using Multidimensional Dominance Drawings

• Published in: SN computer science 2021-07, Vol.2 (4), p.320, Article 320
• Main Authors: Lionakis, Panagiotis, Ortali, Giacomo, Tollis, Ioannis G.
• Format: Article
• Language: English
• Subjects: Algorithms; Computer Imaging; Computer Science; Computer Systems Organization and Communication Networks; Data search; Data structures; Data Structures and Information Theory; Decomposition; Density; Graph theory; Graphs; Information Systems and Communication Service; Original Research; Pattern Recognition and Graphics; Queries; Software Engineering/Programming and Operating Systems; Vision
• ISSN: 2662-995X; 2661-8907
• DOI: 10.1007/s42979-021-00713-6

Answering reachability queries in directed acyclic graphs is an operation required by many applications. In this paper, we present efficient algorithms to construct and search a space-efficient data structure in the k -dimensional space that is based on Graph Dominance Drawing. Our algorithms construct this data structure in O ( km ) time, while it can be stored in O ( kn ) space. Any reachability query is answered in constant time, since no “falsely implied paths (fips)” are introduced. We also present experimental results that show that the number of dimensions, k , in the solutions produced by our techniques is low. Additionally, we present a new method for constructing random DAGs with prespecified structure and density. The analysis of our experimental results reveals an interesting interplay between density and structure.