Planarity testing in parallel

DOI10.1016/S0022-0000(05)80070-4MaRDI QIDQ1342859zbMATH OpenFDO

Authors Vijaya Ramachandran, J. Reif

Publication date 21 June 2000

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 4060743 (Why is no real title available?)
• scientific article; zbMATH DE number 4064466 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3315017 (Why is no real title available?)
• scientific article; zbMATH DE number 3422404 (Why is no real title available?)
• A new graph triconnectivity algorithm and its parallelization
• An Efficient Parallel Biconnectivity Algorithm
• An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
• An efficient parallel algorithm for planarity
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Computing an st-numbering
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Finding Triconnected Components by Local Replacement
• How to Draw a Graph
• Improved algorithms for graph four-connectivity
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Parallel Algorithms in Graph Theory: Planarity Testing
• Parallel Tree Contraction Part 2: Further Applications
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Symmetric Complementation
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Towards optimal parallel bucket sorting

Cited in

(4)

• The complexity of planarity testing
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• Planarity testing revisited

This page was built for publication: Planarity testing in parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1342859)