Planar reachability in linear space and constant time

Jacob Holm; Eva Rotenberg; Mikkel Thorup

doi:10.1109/FOCS.2015.30

Planar reachability in linear space and constant time

Jacob Holm, Eva Rotenberg, Mikkel Thorup

Department of Computer Science

6 Citations (Scopus)

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 language	English
Title of host publication	2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
Number of pages	20
Publisher	IEEE
Publication date	11 Dec 2015
Pages	370-389
DOIs	https://doi.org/10.1109/FOCS.2015.30
Publication status	Published - 11 Dec 2015
Event	The Annual Symposium on Foundations of Computer Science - DoubleTree Hotel, Berkeley, California, United States Duration: 18 Oct 2015 → 20 Oct 2015 Conference number: 56

Conference

Conference	The Annual Symposium on Foundations of Computer Science
Number	56
Location	DoubleTree Hotel
Country/Territory	United States
City	Berkeley, California
Period	18/10/2015 → 20/10/2015

Series	Symposium on Foundations of Computer Science. Annual Proceedings
ISSN	1523-8288

Access to Document

10.1109/FOCS.2015.30

Planar Reachability in Linear Space and Constant TimeFinal published version, 398 KB

http://arxiv.org/pdf/1411.5867v2.pdfLicence: Other

Cite this

Planar reachability in linear space and constant time. / Holm, Jacob; Rotenberg, Eva; Thorup, Mikkel.

2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2015. p. 370-389 (Symposium on Foundations of Computer Science. Annual Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Holm, J, Rotenberg, E & Thorup, M 2015, Planar reachability in linear space and constant time. in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, Symposium on Foundations of Computer Science. Annual Proceedings, pp. 370-389, The Annual Symposium on Foundations of Computer Science, Berkeley, California, United States, 18/10/2015. https://doi.org/10.1109/FOCS.2015.30

@inproceedings{a13cb0cbb19a4d0c877989a883b72c0f,

title = "Planar reachability in linear space and constant time",

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].",

author = "Jacob Holm and Eva Rotenberg and Mikkel Thorup",

year = "2015",

month = dec,

day = "11",

doi = "10.1109/FOCS.2015.30",

language = "English",

series = "Symposium on Foundations of Computer Science. Annual Proceedings",

publisher = "IEEE",

pages = "370--389",

booktitle = "2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)",

note = "The Annual Symposium on Foundations of Computer Science ; Conference date: 18-10-2015 Through 20-10-2015",

}

TY - GEN

T1 - Planar reachability in linear space and constant time

AU - Holm, Jacob

AU - Rotenberg, Eva

AU - Thorup, Mikkel

N1 - Conference code: 56

PY - 2015/12/11

Y1 - 2015/12/11

N2 - 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].

AB - 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].

U2 - 10.1109/FOCS.2015.30

DO - 10.1109/FOCS.2015.30

M3 - Article in proceedings

T3 - Symposium on Foundations of Computer Science. Annual Proceedings

SP - 370

EP - 389

BT - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - The Annual Symposium on Foundations of Computer Science

Y2 - 18 October 2015 through 20 October 2015

ER -

Planar reachability in linear space and constant time

Abstract

Conference

Access to Document

Fingerprint

Cite this