The Library
On L-shaped point set embeddings of trees : first non-embeddable examples
Tools
Mutze, Torsten and Scheucher, Manfred (2020) On L-shaped point set embeddings of trees : first non-embeddable examples. Journal of Graph Algorithms and Applications, 24 (3). pp. 343-369. doi:10.7155/jgaa.00537 ISSN 1526-1719.
|
PDF
WRAP-On-L-shaped-point-set-embeddings-trees-Mutze-2020.pdf - Accepted Version - Requires a PDF viewer. Download (2151Kb) | Preview |
Official URL: https://doi.org/10.7155/jgaa.00537
Abstract
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∈{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.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Embeddings (Mathematics), Trees (Graph theory) | ||||||
Journal or Publication Title: | Journal of Graph Algorithms and Applications | ||||||
Publisher: | Brown University. Department of Computer Science | ||||||
ISSN: | 1526-1719 | ||||||
Official Date: | 31 July 2020 | ||||||
Dates: |
|
||||||
Volume: | 24 | ||||||
Number: | 3 | ||||||
Page Range: | pp. 343-369 | ||||||
DOI: | 10.7155/jgaa.00537 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | This paper was first published in the Journal of Graph Algorithms and Applications 2020,24(3) 343-369. https://doi.org/10.7155/jgaa.00537 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Copyright Holders: | © Journal of Graph Algorithms and Applications | ||||||
Description: | An extended abstract of this paper appeared in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization |
||||||
Date of first compliant deposit: | 6 October 2020 | ||||||
Date of first compliant Open Access: | 6 October 2020 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year