On BendMinimum Orthogonal Upward Drawing of Directed Planar GraphsFößmeier, Ulrich and Kaufmann, Michael (1995) On BendMinimum Orthogonal Upward Drawing of Directed Planar Graphs. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 5263(Official URL: http://dx.doi.org/10.1007/3540589503_356). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_356
AbstractIn 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 mincut 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 bendminimum 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.
Actions (login required)
