An efficient parallel algorithm for planarity

DOI10.1016/0022-0000(88)90006-2zbMath0662.68073OpenAlexW2148686552MaRDI QIDQ1114415

John H. Reif, Philip N. Klein

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

zbMATH Keywords

embeddingplanarityparallel algorithmPQ-tree

Mathematics Subject Classification ID

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