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, Princeton, New Jersey, USA , pp. 64-75 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_357).
Full text not available from this repository.
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.
Repository Staff Only: item control page