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)
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (4)
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Planarity testing in parallel
