Upward straight-line embeddings of directed graphs into point sets
Tài liệu tham khảo
Binucci
Bose, 2002, On embedding an outer-planar graph in a point set, Comput. Geom., 23, 303, 10.1016/S0925-7721(01)00069-4
Bose, 1997, Optimal algorithms to embed trees in a point set, J. Graph Algorithms Appl., 1, 1, 10.7155/jgaa.00002
Cabello, 2006, Planar embeddability of the vertices of a graph using a fixed point set is NP-hard, J. Graph Algorithms Appl., 10, 353, 10.7155/jgaa.00132
Chrobak, 1989, A lower bound on the size of universal sets for planar graphs, Sigact News, 20, 83, 10.1145/74074.74088
de Fraysseix, 1990, How to draw a planar graph on a grid, Combinatorica, 10, 41, 10.1007/BF02122694
Di Battista, 1988, Algorithms for plane representations of acyclic digraphs, Theoret. Comput. Sci., 61, 175, 10.1016/0304-3975(88)90123-5
Di Battista, 1992, Area requirement and symmetry display of planar upward drawings, Discrete Comput. Geom., 7, 381, 10.1007/BF02187850
Alejandro Estrella-Balderrama, Fabrizio Frati, Stephen Kobourov, Upward straight-line embeddings of directed graphs into point sets, in: Proc. of WG 2008, in: LNCS, vol. 5344, 2008, pp. 122–133
Di Giacomo, 2006, Book embeddability of series-parallel digraphs, Algorithmica, 45, 531, 10.1007/s00453-005-1185-7
F. Giordano, G. Liotta, T. Mchedlidze, A. Symvonis, Computing upward topological book embeddings of upward planar digraphs, in: T. Tokuyama (Ed.), ISAAC, 2007, pp. 172–183
Gritzmann, 1991, Embedding a planar triangulation with vertices at specified positions, The American Mathematical Monthly, 98, 165, 10.2307/2323956
Heath, 1999, Stack and queue layouts of directed acyclic graphs: Part I, SIAM Journal on Computing, 28, 1510, 10.1137/S0097539795280287
Kaufmann, 2002, Embedding vertices at points: Few bends suffice for planar graphs, J. Graph Algorithms Appl., 6, 115, 10.7155/jgaa.00046
Kurowski, 2004, A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs, Inform. Process. Lett., 92, 95, 10.1016/j.ipl.2004.06.009
W. Schnyder, Embedding planar graphs on the grid, in: 1st ACM–SIAM Sympos. Discr. Alg. (SODA '90), 1990, pp. 138–148