On L-shaped point set embeddings of trees: First non-embeddable examples

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10435470" target="_blank" >RIV/00216208:11320/20:10435470 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=f9enG_zP5o" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=f9enG_zP5o</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.7155/jgaa.00537" target="_blank" >10.7155/jgaa.00537</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On L-shaped point set embeddings of trees: First non-embeddable examples

Popis výsledku v původním jazyce

An L-shaped embedding of a tree in a point set is a planar drawing of the tree where the vertices are mapped to distinct points and every edge is drawn as a sequence of two axis-aligned line segments. There has been considerable work on establishing upper bounds on the minimum cardinality of a point set to guarantee that any tree of the same size with maximum degree 4 admits an L-shaped embedding on the point set. However, no non-trivial lower bound is known to this date, i.e., no known n-vertex tree requires more than n points to be embedded. In this paper, we present the first examples of n-vertex trees for n ELEMENT OF {13, 14, 16, 17, 18, 19, 20} that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on n &lt;= 12 vertices admits an L-shaped embedding in every set of n points. We also consider embedding ordered trees, where the cyclic order of the neighbors of each vertex in the embedding is prescribed. For this setting, we determine the smallest non-embeddable ordered tree on n = 10 vertices, and we show that every ordered tree on n &lt;= 9 or n = 11 vertices admits an L-shaped embedding in every set of n points. We also construct an infinite family of ordered trees which do not always admit an L-shaped embedding, answering a question raised by Biedl, Chan, Derka, Jain, and Lubiw.

Název v anglickém jazyce

On L-shaped point set embeddings of trees: First non-embeddable examples

Popis výsledku anglicky

An L-shaped embedding of a tree in a point set is a planar drawing of the tree where the vertices are mapped to distinct points and every edge is drawn as a sequence of two axis-aligned line segments. There has been considerable work on establishing upper bounds on the minimum cardinality of a point set to guarantee that any tree of the same size with maximum degree 4 admits an L-shaped embedding on the point set. However, no non-trivial lower bound is known to this date, i.e., no known n-vertex tree requires more than n points to be embedded. In this paper, we present the first examples of n-vertex trees for n ELEMENT OF {13, 14, 16, 17, 18, 19, 20} that require strictly more points than vertices to admit an L-shaped embedding. Moreover, using computer help, we show that every tree on n &lt;= 12 vertices admits an L-shaped embedding in every set of n points. We also consider embedding ordered trees, where the cyclic order of the neighbors of each vertex in the embedding is prescribed. For this setting, we determine the smallest non-embeddable ordered tree on n = 10 vertices, and we show that every ordered tree on n &lt;= 9 or n = 11 vertices admits an L-shaped embedding in every set of n points. We also construct an infinite family of ordered trees which do not always admit an L-shaped embedding, answering a question raised by Biedl, Chan, Derka, Jain, and Lubiw.

Druh

J_SC - Č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)

Projekt

<a href="/cs/project/GA19-08554S" target="_blank" >GA19-08554S: Struktury a algoritmy ve velmi symetrických grafech</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

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ů

Název periodika

Journal of Graph Algorithms and Applications

ISSN

1526-1719

e-ISSN

—

Svazek periodika

24

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

27

Strana od-do

343-369

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85088247543