Quasi-Upward planarity (extended abstract)

Bertolazzi, Paola and Di Battista, Giuseppe and Didimo, Walter (1998) Quasi-Upward planarity (extended abstract). In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 15-29 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_2).

Full text not available from this repository.

Abstract

In this paper we introduce the quasi-upward planar drawing convention and give a polynomial time algorithm for computing a quasi-upward planar drawing with a minimum number of bends within a given planar embedding. Further, we study the problem of computing quasi-upward planar drawings with a minimum number of bends of digraphs considering all the possible planar embeddings. The paper contains also experimental results about proposed techniques.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_2
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.540 Planar
ID Code:204

Repository Staff Only: item control page

References

R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows. In G.L. Nemhauser, A.H:G: Rinnooy Kan, and M.J: Todd, editors, Optimization, vol. 1 of Handbooks in Operations Research and Management, pages 211-360. North-Holland, 1990.

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. In Proc. 5th Workshop Algorithms and Data Structures, vol. 1272 of LNCS, pages 331-344. Springer-Verlag, 1997.

P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica 6(12):476-497, 1994.

P. Bertolazzi, G. Di Battista, C. Mannino, and R. Tamassia. Optimal upward planarity testing of single-source digraphs. In Proc. 1st Annu. European Sympos. Algorithms, vol. 726 of LNCS, pages 37-48, Springer-Verlag, 1993.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

G. Di Battista, W.P. Liu, and I. Rival. Bipartite graphs upward drawings and planarity. Inform. Process. Letters, 36:317-322, 1990.

G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61:175-198, 1988.

G. Di Battista and R. Tamassia. On-line planarity testing.SIAM J. Comput., 25:956-997, 1996.

A. Garg and R. Tamassia. On the Computational Complexity of Upward and Rectilinear Planarity Testing. Proc. DIMACS Workshop GD '94, LNCS, 894, Springer-Verlag, pages 286-297, 1995.

A. Garg and R. Tamassia. Upward planarity testing. Order, 12:109-133, 1995.

A. Garg and R. Tamassia. A New Minimum Cost Flow Algorithm with Applications to Graph Drawing. In Proc. of the Symp. on Graph Drawing, GD'96, pages 139-154. Springer Verlag, September 1996.

J. Hopcroft and R.E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2:135-158, 1973.

M.D: Hutton and A. Lubiw. Upward planar drawing of single-source acyclic digraphs. SIAM J. Comput. 25(2): 391-311, 1996.

D. Kelly. Fundamentals of planar ordered sets. Discrete Math., 63:197-216, 1987.

X. Lin and P. Eades. Arearequirements for drawing hierarchically planar graphs. In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 219-229. Springer Verlag, 1998.

T. Nishizeki and N. Chiba. Planar graphs: Theory and algorithms. Ann. Discrete Math., 32, 1988.

A. Papakostas. Upward planarity testing of outerplanar dags. In R. Tamassia and I.G. Tollis, eds., Proc. of the Symp. on Graph Drawing, GD'94, vol. 894 of LNCS, pages 298-306. Springer Verlag, 1995.

E.M. Reingold and J.S: Tilford. Tidier drawing of trees. IEEE Trans. on Softawre Engineering, SE-7(2):223-228, March 1981.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16 (1987), pages 421-444.

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Transactions on Systems, Man and Cybernetics, SMC-18(1):61-79, 1988.