On Bend-Minimum Orthogonal Upward Drawing of Directed Planar Graphs

Fößmeier, Ulrich and Kaufmann, Michael (1995) On Bend-Minimum Orthogonal Upward Drawing of Directed Planar Graphs. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 52-63 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_356).

Full text not available from this repository.

Abstract

In last year's graph drawing workshop GD'93 we considered a restricted version of the problem of minimization of bends in orthogonal upward drawings. Inserting the severe restriction that each node should have an incoming edge from below and an outgoing edge upwards (if such edges exist),we were able to get optimal bounds on the number of bends in linear time. In this paper now, we release this restriction completely. The problem becomes much harder. Starting from a fixed planar topological embedding we are able to reduce the problem to a min-cut problem and present three algorithms: a) Find an orthogonal upward drawing without any bend, if such a drawing exists (in linear time), b) find a bend-minimum solution, if the undirected version of the graph requires no bends (in time 0(n^2 \times log n), n beeing the number of vertices of the graph), c) apply our technique to the general case; here we could not prove the optimality up to now. But the achieved number of bends does not exceed the optimum by more than the optimal number of bends in Tamassia's undirected case, i.e. our algorithm needs at most twice the number of bends as necessary in this case.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_356
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:97

Repository Staff Only: item control page

References

Bertolazzi, P., R.F. Cohen,G. Di Battista, R. Tamassia and I.G. Tollis, How to Draw a Series-Parallel Digraph, Proc. 3rd Scandinavian Workshop on Algorithm Theory, LNCS 621, (1992), pp. 272-283.

Di Battista, G., Liotta and F. Vargiu, Spiriality of Orthogonal Representations and Optimal Drawings of Series-Parallel Graphs and 3-planar Graphs, Proc. 3nd Workshop on Algorithms and Data Structures, (1993), Lecture Notes in Comp. Science 709, pp. 151-162.

Di Battista, G., W.P. Liu, and I. Rival, Bipartite Graphs, Upward Drawings and Planarity, Information Processing Letters. vol. 36, (1990), pp. 317-322.

Di Battista, G. and R. Tamassia, Algorithms for Plane Representations of Acylic Digraphs, Theoretical Computer Science Vol. 61, (1988), pp. 175-198.

Di Battista, G., R. Tamassia and I.G. Tollis, Area Requirement and Symmetry Display in Drawing Graphs, Discrete and Comp. Geometry 7 (1992), pp. 381-401.

Eades, P., B. McKay and N. Wormald, On an Edge Crossing Problem, Proc. 9th Australian Computer Science Conf., (1986), pp. 327-334.

Fößmeier, U. and M. Kaufmann, An Approach for Bend-Minimal Upward Drawing, Workshop of GD'93, Paris (1993), pp. 27-29.

Garg, A. and R. Tamassia, On the Computational Complexity of Upward and Rectilinear Planarity Testing, Report CS-94-10, Comp. Sci. Dep., Brown Univ., Providence (1994), this proceedings.

Kelly, I. and I. Rival, Planar Lattices, Canadian J. Mathematics, Vol. 27, (1995), pp. 636-666.

Storer, J.A., On Minimal Node-cost Planar Embeddings, Networks 14 (1984), pp. 181-212.

Sugiyama, K, S. Tagawa and M. Toda, Methods for Visual Understanding of Hierarchical Systems, IEEE Trans. on Systems, Man and Cybernetics, Vol, SMC-11, (1981), pp. 109-125.

Tamassia, R., On Embedding a Graph in the Grid with the Minimum Number of Bends, SIAM J. Comput. 16 (1987), pp. 421-444.

Tamassia, R. and I.G. Tollis, A Unified Approach to Visibility Representations of Planar Graphs, Discrete and Comp.Geometry 1 (1986), pp. 321-341.

Tamassia, R. and I.G. Tollis, Efficient Embedding of Planar Graphs in Linear Time, Proc. IEEE Int. Symp. on Circuits and Systems, Philadelphia, (1987), pp. 495-498.

Tarjan, R.E., Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, (1983), Chapter 8.

Thomassen, C., Planar Acylic Oriented Graphs, Order, Vol. 5, (1989), pp. 349-361.