Back to Search
Start Over
Universal Slope Sets for Upward Planar Drawings.
- Source :
-
Algorithmica . Sep2022, Vol. 84 Issue 9, p2556-2580. 25p. - Publication Year :
- 2022
-
Abstract
- We study universal sets of slopes for computing upward planar drawings of planar st-graphs. We first consider a subfamily of planar st-graphs, called bitonic st-graphs. We prove that every set S of Δ slopes containing the horizontal slope is universal for 1-bend upward planar drawings of bitonic st-graphs with maximum vertex degree Δ , i.e., every such digraph admits a 1-bend upward planar drawing whose edge segments use only slopes in S . This result is worst-case optimal in terms of number of slopes, and, for a suitable choice of S , it gives rise to drawings with worst-case optimal angular resolution. We then prove that every such set S can be used to construct 2-bend upward planar drawings of n-vertex planar st-graphs with at most 4 n - 9 bends in total. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*CHARTS, diagrams, etc.
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 84
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 158510135
- Full Text :
- https://doi.org/10.1007/s00453-022-00975-3