Upward straight-line embeddings of directed graphs into point sets |
| |
Authors: | Carla Binucci Emilio Di Giacomo Walter Didimo Alejandro Estrella-Balderrama Fabrizio Frati Stephen G. Kobourov Giuseppe Liotta |
| |
Affiliation: | aDipartimento di Ingegneria Elettronica e dell'Informazione – Università degli Studi di Perugia, Italy;bDepartment of Computer Science – University of Arizona, USA;cDipartimento di Informatica e Automazione – Università di Roma Tre, Italy;dAT&T Research Labs., USA |
| |
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. |
| |
Keywords: | Graph drawing Upward drawings Point-set embedding |
本文献已被 ScienceDirect 等数据库收录! |