A contraction procedure for planar directed graphs
- 1 June 1992
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 431-441
- https://doi.org/10.1145/140901.141935
Abstract
We show that testing reachability in a planar DAGcan be performed in parallel in O(log n logn) time(O(log n) time using randomization) using O(n) processors.In general we give a paradigm for contractinga planar DAG to a point and then expanding it back.This paradigm is developed from a property of planar directedgraphs we refer to as the Poincar'e index formula.Using this new paradigm we then "overlay" our applicationin a fashion similar to parallel tree contraction[MR85, MR89]. We ...Keywords
This publication has 8 references indexed in Scilit:
- Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected ComponentsSIAM Journal on Computing, 1993
- High-probability parallel transitive closure algorithmsPublished by Association for Computing Machinery (ACM) ,1990
- Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphsPublished by Association for Computing Machinery (ACM) ,1990
- Parallel graph contractionPublished by Association for Computing Machinery (ACM) ,1989
- Local reorientation, global order, and planar topologyPublished by Association for Computing Machinery (ACM) ,1989
- An optimal parallel algorithm for graph planarityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Parallel symmetry-breaking in sparse graphsPublished by Association for Computing Machinery (ACM) ,1987