Parallel Algorithms in Graph Theory: Planarity Testing

DOI10.1137/0211024zbMath0494.68069OpenAlexW2071939274WikidataQ56431282 ScholiaQ56431282MaRDI QIDQ3957959

Janos Simon, Joseph F. Ja'Ja'

Publication date: 1982

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0211024

zbMATH Keywords

parallel algorithmsplanarity testingembeddings of triconnected planar graphs in the planeplane meshpseudoembeddingtriconnected components of undirected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Finding small simple cycle separators for 2-connected planar graphs, The complexity of planarity testing, Planarity testing in parallel, Parallel dynamic lowest common ancestors, An efficient parallel algorithm for finding rectangular duals of plane triangular graphs, Parallel ear decomposition search (EDS) and st-numbering in graphs, Parallel O(log n) time edge-colouring of trees and Halin graphs, An efficient parallel algorithm for planarity, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, Parallel computations on graphs, Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata, On the complexity of the stability problem of binary freezing totalistic cellular automata, Parallel computation and conflicts in memory access, Formula dissection: A parallel algorithm for constraint satisfaction, Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses, Planarity Testing Revisited, A new graph triconnectivity algorithm and its parallelization, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Parallel strong orientation of an undirected graph, A parallel search algorithm for directed acyclic graphs, Topological queries in spatial databases, A note on finding minimum cuts in directed planar networks by parallel computations