Planar Reachability in Linear Space and Constant Time

2014/11/21 by Jacob Holm, Holm, Jacob, Eva Rotenberg +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1411.5867

20 pages, 5 figures, submitted to FoCS

arxiv created 2015/04/04 · arxiv updated 2015/04/07

Abstract

We show how to represent a planar digraph in linear space so that distance queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reachability is thus optimal in both time and space, and has optimal construction time. The previous best solution used O(nlog n) space for constant query time [Thorup FOCS'01].

Cited by

• Adjacency labelling for proper minor-closed graph classes

Related

• Improved distance queries in planar graphs
• Planar Distance Oracles with Better Time-Space Tradeoffs
• Better Tradeoffs for Exact Distance Oracles in Planar Graphs
• Almost Optimal Distance Oracles for Planar Graphs
• Fast and Compact Exact Distance Oracle for Planar Graphs