2024/09/23 by Naman Jain, Jain, Naman
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Graph Theory and Algorithms #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.2409.15400
openalex publication_date 2024/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a parallel O(log(n))-time algorithm on a CRCW PRAM to assign vertical and horizontal segments to the vertices of any planar bipartite graph G in the following manner: i) Two segments cannot share an interior point ii) Two segments intersect if and only if the corresponding vertices are adjacent, which uses a polynomial number of processors. In other words, represent vertices of a planar bipartite graph as parallel segments, and edges as intersection points between these segments. Note that two segments are not allowed to cross. Our method is based on a parallel algorithm for st-numbering which uses an ear decomposition search.