On upward straight-line embeddings of oriented paths
| Authors | |
|---|---|
| Year of publication | 2017 |
| Type | Article in Proceedings |
| Conference | EGC 2017, XVII Spanish Meeting on Computational Geometry |
| MU Faculty or unit | |
| Citation | |
| Web | The book of abstracts where the publication is available online |
| Keywords | Computational geometry, probability, geometric embedding |
| Description | We investigate upward straight-line embeddings (UPSEs) of oriented paths. Along the lines of similar results in the literature, we find a condition —related to the number of vertices in between sources and sinks of an oriented path— that guarantees that an oriented path satisfying the condition on n vertices admits an UPSE into any n-point set in general position. We also show that the following holds for every ? > 0. If S is a set of n points chosen uniformly at random in the unit square, and P is an oriented path on at most (1/3 - ?)n vertices, then with high probability P has an UPSE into S. |
| Related projects: |