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.

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
ID Code:99

Repository Staff Only: item control page

References

A. Amihood. A direct linear-time planarity test for unflippable modules. Intern.J. Computer Math., vol. 21, pp. 277-290, 1987.

T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. In Proc. of the Second Annual European Symposium (ESA '94), Lecture Notes in Computer Science, Vol. 855, pp. 24-35. Springer-Verlag, 1994.

G. Di Battista, R. Tamissa, and I.G. Tollis. Constrained visibility representations of graphs. Information Processing Letters, vol. 41, pp. 1-7, 1992.

S. Even and G. Granot. Rectilinear planar drawings with few bends in each edge. Technical Report 797, Computer Science Department, Technion, Israel Inst. of Tech., 1994. can be retrieved by anonymous ftp. technion.ac.il at directory /pub/supported/cs/Tech_Reports/1994 as file TR797.ps.Z

S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science, vol. 2, pp. 339-344, 1976.

Z. Miller and J. B. Orlin. NP-completeness for minimizing Maximum edge length in grid embeddings. Journal of Algorithms, vol. 6, pp. 10-16, 1985.

R. Y. Pinter. River routing: Methodology and analysis. In third CALTECH conference on Very Large Scale Integration, pp. 141-163. Computer Science Press, 1983.

P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete and Computational Geometry, vol. 1 no. 4, pp. 343-353, 1986.

Y. Shiloach. Linear and Planar Arrangements of Graphs. PhD thesis, Department of Applied Mathematics, Weizmann Institute of Science, Rehovot Israel, 1976.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Computing, vol. 16 no. 3, pp. 421-444, 1987.

R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, vol. 1 no. 4, pp. 322-341, 1986.

L. Yanpei, A. Morgana, and B. Simeone. General theoretical results on rectilinear embedability of graphs. Acta Mathematicae Applicatae Sinica Journal, vol. 7 no. 2, pp. 187-192, 1991.

S. Zaks. An easy planarity test for unflippable modules. Technical Report 771, Computer Science Department, Technion, Israel Inst. of Tech., 1993.