Charles Explorer logo
🇨🇿

On the Edge-Length Ratio of 2-Trees

Publikace na Matematicko-fyzikální fakulta |
2020

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor.

Comput. Sci. 770 (2019), 88-94] and, for any given constant r, we provide a 2-tree which does not admit a planar straight-line drawing with a ratio bounded by r.

When the ratio is restricted to adjacent edges only, we prove that any 2-tree admits a planar straight-line drawing whose edge-length ratio is at most 4 + ε for any arbitrarily small ε> 0, hence the upper bound on the local edge-length ratio of partial 2-trees is 4. (C) 2020, Springer Nature Switzerland AG.