Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs
2012
This work presents a log-space reduction which compresses a directed acyclic graph with m sources embedded on a surface of genus g to a graph on O(m + g) vertices while preserving reachability between a given pair of vertices. Applying existing algorithms to this smaller graph gives improved space bounds as well as improved simultaneous time-space bounds for the reachability problem for a large class of directed acyclic graphs. Specifically, it significantly extends the class of surface-embedded graphs with log-space reachability algorithms: from planar graphs with O(log n) sources, to graphs with 2 O( √ log n) sources embedded in a surface of genus 2 O( √ log n). Additionally it also yields sublinear space (n 1−ɛ space) algorithms with polynomial running time for graphs with n 1−ɛ sources embedded on surfaces of genus n 1−ɛ. 1