On L-shaped point set embeddings of trees: First non-embeddable examples
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On L-shaped point set embeddings of trees: First non-embeddable examples
Original language description
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 <= 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 <= 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-08554S" target="_blank" >GA19-08554S: Structures and algorithms in highly symmetric graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Graph Algorithms and Applications
ISSN
1526-1719
e-ISSN
—
Volume of the periodical
24
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
27
Pages from-to
343-369
UT code for WoS article
—
EID of the result in the Scopus database
2-s2.0-85088247543