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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/97

Actions (login required)

View Item View Item