Back to Search
Start Over
On Edge-Length Ratios of Partial 2-Trees.
- Source :
- International Journal of Computational Geometry & Applications; Jun/Sep2021, Vol. 31 Issue 2/3, p141-162, 22p
- Publication Year :
- 2021
-
Abstract
- The edge-length ratio of a planar straight-line drawing of a graph is the maximum ratio between the lengths of any two of its edges. When the edges to be considered in the ratio are required to be adjacent, the ratio is called local edge-length ratio. The (local) edge-length ratio of a graph G is the infimum over all (local) edge-length ratios in the planar straight-line drawings of G. We prove that the edge-length ratio of the n -vertex 2-trees is Ω (log n) , which proves a conjecture by Lazard et al. [TCS 770, 2019, pp. 88–94] and complements an upper bound by Borrazzo and Frati [JoCG 11(1), 2020, pp. 137–155]. We also prove that every partial 2-tree admits a planar straight-line drawing whose local edge-length ratio is at most 4 + for any arbitrarily small > 0. [ABSTRACT FROM AUTHOR]
- Subjects :
- PLANAR graphs
LOGICAL prediction
EDGES (Geometry)
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 31
- Issue :
- 2/3
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 154929880
- Full Text :
- https://doi.org/10.1142/S0218195921500072