caa a22 4500 46907535X CHVBK 20180323132933.0 cr unu---uuuuu 170328e19920401xx s 000 0 eng 10.1007/BF02187850 doi (NATIONALLICENCE)springer-10.1007/BF02187850 Area requirement and symmetry display of planar upward drawings [Elektronische Daten] [Giuseppe Battista, Roberto Tamassia, Ioannis Tollis] In this paper we investigate the problem of constructing planar straight-line drawings of acyclic digraphs such that all the edges flow in the same direction, e.g., from bottom to top. Our contribution is twofold. First we show the existence of a family of planar acyclic digraphs that require exponential area for any such drawing. Second, motivated by the preceding lower bound, we relax the straight-line constraint and allow bends along the edges. We present a linear-time algorithm that produces drawings of planarst-graphs with a small number of bends, asymptotically optimal area, and such that symmetries and isomorphisms of the digraph are displayed. If the digraph has no transitive edges, then the drawing obtained has no bends. Also, a variation of the algorithm produces drawings with exact minimum area. Springer-Verlag New York Inc., 1992 Battista Giuseppe Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Salaria, 00198, 113 Roma, Italy aut Tamassia Roberto Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA aut Tollis Ioannis Department of Computer Science, University of Texas at Dallas, 75083-0688, Richardson, TX, USA aut Discrete & Computational Geometry Springer New York 7/4(1992-04-01), 381-401 0179-5376 7:4<381 1992 7 454 https://doi.org/10.1007/BF02187850 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02187850 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Battista Giuseppe Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza”, Via Salaria, 00198, 113 Roma, Italy aut NATIONALLICENCE 700 1- Tamassia Roberto Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA aut NATIONALLICENCE 700 1- Tollis Ioannis Department of Computer Science, University of Texas at Dallas, 75083-0688, Richardson, TX, USA aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 7/4(1992-04-01), 381-401 0179-5376 7:4<381 1992 7 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer