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 Applied Mathematics and Computer Science

University of Copenhagen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
Number of pages	20
Volume	2015-December
Publisher	IEEE Computer Society Press
Publication date	11 Dec 2015
Pages	370-389
Article number	7354404
ISBN (Electronic)	9781467381918
DOIs	https://doi.org/10.1109/FOCS.2015.30
Publication status	Published - 11 Dec 2015
Event	56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 - Berkeley, United States Duration: 18 Oct 2015 → 20 Oct 2015 Conference number: 56

Conference

Conference	56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Number	56
Country/Territory	United States
City	Berkeley
Period	18/10/2015 → 20/10/2015
Sponsor	IEEE

Keywords

data structures
directed graphs
Planar graphs
reachability

Access to Document

10.1109/FOCS.2015.30

OpenUrl availability

Full text

Cite this

@inproceedings{5e46835e74f043abbeb7ee20a601ecae,

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

keywords = "data structures, directed graphs, Planar graphs, reachability",

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

year = "2015",

month = dec,

day = "11",

doi = "10.1109/FOCS.2015.30",

language = "English",

volume = "2015-December",

pages = "370--389",

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

publisher = "IEEE Computer Society Press",

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

}

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, 7354404, IEEE Computer Society Press, pp. 370-389, 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, California, United States, 18/10/2015. https://doi.org/10.1109/FOCS.2015.30

Planar Reachability in Linear Space and Constant Time. / Holm, Jacob; Rotenberg, Eva; Thorup, Mikkel.
Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. Vol. 2015-December IEEE Computer Society Press, 2015. p. 370-389 7354404.

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

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

KW - data structures

KW - directed graphs

KW - Planar graphs

KW - reachability

UR - http://www.scopus.com/inward/record.url?scp=84960364193&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2015.30

DO - 10.1109/FOCS.2015.30

M3 - Article in proceedings

AN - SCOPUS:84960364193

VL - 2015-December

SP - 370

EP - 389

BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015

PB - IEEE Computer Society Press

T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015

Y2 - 18 October 2015 through 20 October 2015

ER -

Planar Reachability in Linear Space and Constant Time

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this