@inproceedings{27c5b682cb6049f3bf5def89aa821b53,

title = "Local reorientation, global order, and planar topology",

abstract = "Almost every problem on digraphs requires computing strongly connected components and directed spanning trees in one form or another. It has long been an open problem whether polylog time and linear processors are enough to find the strongly connected components of a digraph and compute directed spanning trees for these components. This paper provides the first non-trivial partial solution to this open problem: For a planar digraph with n vertices, the strongly connected components can be computed in O(log3 n) time and O(n) processors. If the graph is strongly connected, a directed spanning tree can be built in O(log2 n) time and O(n) processors. Both algorithms are deterministic and run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory.",

author = "Kao, {Ming Yang} and Shannon, {Gregory E.}",

year = "1989",

month = dec,

day = "1",

language = "English (US)",

isbn = "0897913078",

series = "Proc Twenty First Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "286--296",

booktitle = "Proc Twenty First Annu ACM Symp Theory Comput",

note = "Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing ; Conference date: 15-05-1989 Through 17-05-1989",

}