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.
On Directed Graphs with an Upward Straight-line Embedding into Every Point Set
BINUCCI, Carla;DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe
2009
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
