Parallel Graph Drawing Algorithm for Bipartite Planar Graphs
<|reference_start|>Parallel Graph Drawing Algorithm for Bipartite Planar Graphs: 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.<|reference_end|>
@article{jain2024parallel,
    title={Parallel Graph Drawing Algorithm for Bipartite Planar Graphs},
    author={Naman Jain},
    journal={arXiv preprint arXiv:2409.15400},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.15400},
    primaryClass={cs.CG}
}