Grid Layouts of Block Diagrams - Bounding the Number of Bends in Each Connection (Extended Abstract)

Even, S. and Granot, G. (1995) Grid Layouts of Block Diagrams - Bounding the Number of Bends in Each Connection (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 64-75(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_357).

Full text not available from this repository.

Abstract

Consider an input data which specifies rectangular modules and connections between them; this is a graph. The size of the modules and the placements of the terminals on them is given as part of the input. We produce a block diagram, conforming to the input. The block diagram is on the rectilinear grid, and each edge (connection between modules) has few bends. For planar input, a linear-time algorithm is described to construct a planar drawing with at most 6 bends in each self-loop and at most 4 bends in any other edge. The external face of the drawing may be specified by the user. We show a planar input with no self-loops which has no drawing with at most 3 bends in every edge and another planar input which has no drawing with at most 5 bends in every self-loop. A linear-time algorithm is described to construct a nonplanar drawing of any input, with at most 4 bends in each edge. We show inputs that have no drawing with at most 3 bends in every edge.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_357
Classifications: M Methods > M.999 Others
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/99

Actions (login required)

View Item View Item