TY - JOUR

T1 - Upward straight-line embeddings of directed graphs into point sets

AU - Binucci, Carla

AU - Di Giacomo, Emilio

AU - Didimo, Walter

AU - Estrella-Balderrama, Alejandro

AU - Frati, Fabrizio

AU - Kobourov, Stephen G.

AU - Liotta, Giuseppe

N1 - Funding Information:
✩ Research partially supported by the MIUR Project “MAINSTREAM: Algorithms for massive information structures and data streams”. * Corresponding author. E-mail addresses: binucci@diei.unipg.it (C. Binucci), digiacomo@diei.unipg.it (E. Di Giacomo), didimo@diei.unipg.it (W. Didimo), aestrell@cs.arizona.edu (A. Estrella-Balderrama), frati@dia.uniroma3.it (F. Frati), skobourov@research.att.com (S.G. Kobourov), liotta@diei.unipg.it (G. Liotta).

PY - 2010/2

Y1 - 2010/2

N2 - 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.

AB - 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.

KW - Graph drawing

KW - Point-set embedding

KW - Upward drawings

UR - http://www.scopus.com/inward/record.url?scp=84867975626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867975626&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2009.07.002

DO - 10.1016/j.comgeo.2009.07.002

M3 - Article

AN - SCOPUS:84867975626

VL - 43

SP - 219

EP - 232

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 2 SPEC. ISS.

ER -