@inproceedings{5a8bf3233f1148d3923a308130a6bb10,
title = "The directed planar reachability problem",
abstract = "We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to the planar case. We also consider a previously-studied subclass of planar graphs known as grid graphs. We show that the directed planar s-t-connectivity problem reduces to the reachability problem for directed grid graphs. A special case of the grid-graph reachability problem where no edges are directed from right to left is known as the {"}layered grid graph reachability problem{"}. We show that this problem lies in the complexity class UL.",
author = "Eric Allender and Samir Datta and Sambuddha Roy",
year = "2005",
doi = "10.1007/11590156_19",
language = "English (US)",
isbn = "3540304959",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "238--249",
booktitle = "FSTTCS 2005",
note = "25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2005 ; Conference date: 15-12-2005 Through 18-12-2005",
}