Parallel Graph Drawing Algorithm for Bipartite Planar Graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917784182587392 |
|---|---|
| author | Jain, Naman |
| author_facet | Jain, Naman |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15400 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Graph Drawing Algorithm for Bipartite Planar Graphs Jain, Naman Computational Geometry 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. |
| title | Parallel Graph Drawing Algorithm for Bipartite Planar Graphs |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2409.15400 |