Planar Reachability in Linear Space and Constant Time

Jacob Holm, Eva Rotenberg, Mikkel Thorup

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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

Original languageEnglish
Title of host publicationProceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
Number of pages20
Volume2015-December
PublisherIEEE Computer Society Press
Publication date11 Dec 2015
Pages370-389
Article number7354404
ISBN (Electronic)9781467381918
DOIs
Publication statusPublished - 11 Dec 2015
Event56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States
Duration: 18 Oct 201520 Oct 2015
Conference number: 56

Conference

Conference56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Number56
CountryUnited States
CityBerkeley
Period18/10/201520/10/2015
SponsorIEEE

Keywords

  • data structures
  • directed graphs
  • Planar graphs
  • reachability

Cite this

Holm, J., Rotenberg, E., & Thorup, M. (2015). Planar Reachability in Linear Space and Constant Time. In Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 (Vol. 2015-December, pp. 370-389). [7354404] IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2015.30