TY - GEN
T1 - Upward straight-line embeddings of directed graphs into point sets
AU - Estrella-Balderrama, Alejandro
AU - Frati, Fabrizio
AU - Kobourov, Stephen G.
PY - 2008
Y1 - 2008
N2 - In this paper we consider the problem of characterizing the directed graphs that admit an upward straight-line embedding into every point set in convex or in general position. In particular, we show that no biconnected directed graph admits an upward straight-line embedding into every point set in convex position, and we provide a characterization of the Hamiltonian directed graphs that admit upward straight-line embeddings into every point set in general or in convex position. We also describe how to construct upward straight-line embeddings of directed paths into convex point sets and we prove that for directed trees such embeddings do not always exist. Further, we investigate the related problem of upward simultaneous embedding without mapping, proving that deciding whether two directed graphs admit an upward simultaneous embedding without mapping is NP-hard.
AB - In this paper we consider the problem of characterizing the directed graphs that admit an upward straight-line embedding into every point set in convex or in general position. In particular, we show that no biconnected directed graph admits an upward straight-line embedding into every point set in convex position, and we provide a characterization of the Hamiltonian directed graphs that admit upward straight-line embeddings into every point set in general or in convex position. We also describe how to construct upward straight-line embeddings of directed paths into convex point sets and we prove that for directed trees such embeddings do not always exist. Further, we investigate the related problem of upward simultaneous embedding without mapping, proving that deciding whether two directed graphs admit an upward simultaneous embedding without mapping is NP-hard.
UR - http://www.scopus.com/inward/record.url?scp=58349095889&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58349095889&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-92248-3_12
DO - 10.1007/978-3-540-92248-3_12
M3 - Conference contribution
AN - SCOPUS:58349095889
SN - 3540922474
SN - 9783540922476
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 122
EP - 133
BT - Graph-Theoretic Concepts in Computer Science - 34th International Workshop, WG 2008, Revised Papers
T2 - 34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008
Y2 - 30 June 2008 through 2 July 2008
ER -