On Directed Graphs with an Upward Straight-line Embedding into Every Point Set
Carla Binucci, Emilio Di Giacomo, Walter Didimo, Alejandro Estrella-Balderrama, Fabrizio Frati, Stephen Kobourov, Giuseppe Liotta · Iris (Roma Tre University) · 2009
In this paper we study the problem of computing an upward straight-line embedding of a directed graph G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction.We characterize the family of directed graphs that admit an upward straight-line embedding into every one-side convex point set, that is, into every point-set such that the top-most and the bottom-most points are adjacent in the convex hull of the point set.Also we show how to construct upward straight-line embeddings for a sub-class of directed paths when the point set is in general position.