Planarity testing in parallel
From MaRDI portal
Publication:1342859
DOI10.1016/S0022-0000(05)80070-4zbMath0938.68948MaRDI QIDQ1342859
Vijaya Ramachandran, John H. Reif
Publication date: 21 June 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
68W10: Parallel algorithms in computer science
Related Items
The combinatorial approach yields an NC algorithm for computing Pfaffians, The complexity of planarity testing, The isomorphism problem for planar 3-connected graphs is in unambiguous logspace, Planarity Testing Revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
- Improved algorithms for graph four-connectivity
- Parallel ear decomposition search (EDS) and st-numbering in graphs
- Towards optimal parallel bucket sorting
- An efficient parallel algorithm for planarity
- A new graph triconnectivity algorithm and its parallelization
- Computing an st-numbering
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- An Efficient Parallel Biconnectivity Algorithm
- Symmetric Complementation
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Parallel Algorithms in Graph Theory: Planarity Testing
- An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
- Parallel Tree Contraction Part 2: Further Applications
- Efficient Planarity Testing
- Finding Triconnected Components by Local Replacement
- Dividing a Graph into Triconnected Components
- How to Draw a Graph
