×

Upward straight-line embeddings of directed graphs into point sets. (English) Zbl 1221.05175

Summary: 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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Binucci, Carla; Di Giacomo, Emilio; Didimo, Walter; Kobourov, Stephen; Liotta, Giuseppe, Upward geometric point-set embeddings of directed graphs, Technical Report RT-005-08, DIEI, Univ. Perugia, 2008 · Zbl 1221.05175
[2] Bose, P., On embedding an outer-planar graph in a point set, Comput. Geom., 23, 3, 303-312 (2002) · Zbl 1012.05057
[3] Bose, P.; McAllister, M.; Snoeyink, J., Optimal algorithms to embed trees in a point set, J. Graph Algorithms Appl., 1, 2, 1-15 (1997) · Zbl 0890.05066
[4] Cabello, S., Planar embeddability of the vertices of a graph using a fixed point set is NP-hard, J. Graph Algorithms Appl., 10, 2, 353-366 (2006) · Zbl 1161.68645
[5] Chrobak, M.; Karloff, H., A lower bound on the size of universal sets for planar graphs, Sigact News, 20, 4, 83-86 (1989)
[6] de Fraysseix, H.; Pach, J.; Pollack, R., How to draw a planar graph on a grid, Combinatorica, 10, 1, 41-51 (1990) · Zbl 0728.05016
[7] Di Battista, G.; Tamassia, R., Algorithms for plane representations of acyclic digraphs, Theoret. Comput. Sci., 61, 175-198 (1988) · Zbl 0678.68059
[8] Di Battista, G.; Tamassia, R.; Tollis, I. G., Area requirement and symmetry display of planar upward drawings, Discrete Comput. Geom., 7, 381-401 (1992) · Zbl 0757.05055
[10] Di Giacomo, E.; Didimo, W.; Liotta, G.; Wismath, S. K., Book embeddability of series-parallel digraphs, Algorithmica, 45, 4, 531-547 (2006) · Zbl 1099.68075
[12] Gritzmann, P.; Mohar, B.; Pach, J.; Pollack, R., Embedding a planar triangulation with vertices at specified positions, The American Mathematical Monthly, 98, 165-166 (1991)
[13] Heath, L. S.; Pemmaraju, S. V.; Trenk, A., Stack and queue layouts of directed acyclic graphs: Part I, SIAM Journal on Computing, 28, 1510-1539 (1999) · Zbl 0926.68095
[14] Kaufmann, M.; Wiese, R., Embedding vertices at points: Few bends suffice for planar graphs, J. Graph Algorithms Appl., 6, 1, 115-129 (2002) · Zbl 0999.68164
[15] Kurowski, M., A 1.235 lower bound on the number of points needed to draw all \(n\)-vertex planar graphs, Inform. Process. Lett., 92, 2, 95-98 (2004) · Zbl 1183.68430
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.