An efficient parallel algorithm for planarity
From MaRDI portal
Publication:1114415
DOI10.1016/0022-0000(88)90006-2zbMath0662.68073OpenAlexW2148686552MaRDI QIDQ1114415
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90006-2
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (12)
Planarity testing in parallel ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ Parallel nested dissection for path algebra computations ⋮ An efficient parallel algorithm for planarity ⋮ PC trees and circular-ones arrangements. ⋮ Efficient parallel algorithms for doubly convex-bipartite graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal parallel algorithms on circular-arc graphs ⋮ The Monotone Circuit Value Problem with Bounded Genus Is in NC ⋮ On testing consecutive-ones property in parallel ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
Cites Work
- Sorting in \(c \log n\) parallel steps
- An efficient parallel algorithm for planarity
- Computing an st-numbering
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Parallel Algorithms in Graph Theory: Planarity Testing
- Efficient Planarity Testing
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- Implementation of simultaneous memory address access in models that forbid it
- Parallelism in random access machines
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An efficient parallel algorithm for planarity