1. Upward straight-line embeddings of directed graphs into point sets
- Author
-
Binucci, Carla, Di Giacomo, Emilio, Didimo, Walter, Estrella-Balderrama, Alejandro, Frati, Fabrizio, Kobourov, Stephen G., and Liotta, Giuseppe
- Subjects
- *
EMBEDDINGS (Mathematics) , *DIRECTED graphs , *POINT set theory , *ACYCLIC model , *MATHEMATICAL mappings , *CONVEX geometry - Abstract
Abstract: In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic 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. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position. [Copyright &y& Elsevier]
- Published
- 2010
- Full Text
- View/download PDF