Upward planar embedding of an n -vertex oriented path on O(n2) O ( n 2 ) points
We prove that every n -vertex oriented path admits an upward planar embedding on every general set of (n?1)2+1 ( n ? 1 ) 2 + 1 points on the plane. This result improves the previously known upper bound which is exponential in the number of switches of the given oriented path (Angelini et al. 2010) [1].
oriented path upward point-set embedding universal point set