On Edge-Length Ratios of Partial 2 -Trees
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10455445" target="_blank" >RIV/00216208:11320/21:10455445 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21240/21:00358128
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9nKjNXZNWp" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9nKjNXZNWp</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0218195921500072" target="_blank" >10.1142/S0218195921500072</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Edge-Length Ratios of Partial 2 -Trees
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On Edge-Length Ratios of Partial 2 -Trees
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>SC</sub> - Článek v periodiku v databázi SCOPUS
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2021
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
International Journal of Computational Geometry and Applications
ISSN
0218-1959
e-ISSN
—
Svazek periodika
31
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
SG - Singapurská republika
Počet stran výsledku
22
Strana od-do
141-162
Kód UT WoS článku
—
EID výsledku v databázi Scopus
2-s2.0-85123985692