On upward straight-line embeddings of oriented paths

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CAGIRICI Onur CASUSO Leonardo CAROLINA Medina RAGGI Miguel ROLDAN-PENSADO Edgardo SALAZAR Gelasio URRUTIA Jorge

Year of publication 2017
Type Article in Proceedings
Conference EGC 2017, XVII Spanish Meeting on Computational Geometry
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.