Drawing Clustered Graphs on an Orthogonal Grid

Eades, Peter and Feng, Qing-Wen (1998) Drawing Clustered Graphs on an Orthogonal Grid. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 146-157 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_58).

Full text not available from this repository.

Abstract

Clustered graphs are graphs with recursive clustering structures over the vertices. For graphical representation, the clustering structure is represented by a simple region that contains the drawing of all the vertices which belong to that cluster. In this paper, we present an algorithm which produces planar drawings of clustered graphs in a convention known as orthogonal grid rectangular cluster drawings. We present an algorithm which produces such drawings with O(n²) area and with at most 3 bends in each edge. This result is as good as existing results of planar graphs. Further, we show that our algorithm is optimal in terms of the number of bends in each edge.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_58
Classifications:P Styles > P.900 Visibility
P Styles > P.180 Cluster
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:75

Repository Staff Only: item control page

References

C. Batini, L. Furlani, and E. Nardelli. What is a good diagram? a pragmatic approach. In Proc. 4th Int. Conf. on the Entity Relationship Approach, 1985.

C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity-relationship diagrams. Journal of Systems and Software, 4:163-173, 1984.

G. di Battista and R. Tamassia. Algorithms for plane representations of acyclic diagraphs. Theoretical Computer Science, 61:175-198, 1988.

G. di Battista, R. Tamassia, and I.G. Tollis. Constrained visibility representations of graphs. Information processing Letters, 41:1-7, 1992.

T. Biedl. New lower bounds for orthogonal graph drawings. In Franz J. Brandenburg, editor, GD '95, volume 1027 of Lecture Notes in Computer Science, pages 28-39. Springer-Verlag, 1995.

T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. In ESA '94, volume 855 of Lecture Notes in Computer Science, pages 24-35. Springer-Verlag, 1994.

P. Bose, A. Dean, J. Hutchison., and T. Shermer. On rectangle visibility graphs. In Stephen C. North, editor, GD '96, volume 1190 of Lecture Notes in Computer Science, pages 25-44. Springer-Verlag, 1997.

P. Eades, Q. Feng, and X. Lin. Straight-line drawing algorithms for hierarchical graphs and clustered graphs. In Stephen C. North, editor, GD '96, volume 1190 of Lecture Notes in Computer Science, pages 113-128. Springer-Verlag, 1997.

S. Even and G. Granot. Rectilinear planar drawings with few bends in each edge. Technical Report 797, Computer Science Department, Technion, Israel Institute of Technology, 1994.

S. Even and G. Granot. Grid layout of block diagrams - bounding the number of bends in each connection. In R. Tamassia and I. G. Tollis, editors, GD '94, volume 894 of Lecture Notes in Computer Science, pages 64-75. Springer-Verlag, 1995.

Q. Feng, R. Cohen, and P. Eades. How to draw a planar clustered graph. In COCOON '95, volume 959 of Lecture Notes in Computer Science, pages 21-31. Springer-Verlag, 1995.

Q. Feng, R. Cohen, and P. Eades. Planarity for clustered graphs. In ESA '95, volume 979 of Lecture Notes in Computer Science, pages 213-226. Springer-Verlag, 1995.

U. Fößmeier, G. Kant, and M. Kaufmann. 2-visibility drawings of planar graphs. In Stephen C. North, editor, GD '96, volume 1190 of Lecture Notes in Computer Science, pages 155-168. Springer-Verlag, 1997.

A. Garg and R. Amassia. On the computational complexity of upward and rectilinear planarity testing. In R. Tamassia and I. G. Tollis, editors, GD '94, volume 894 of Lecture Notes in Computer Science, pages 286-297. Springer-Verlag, 1995.

D. Harel. On visual formalisms. Communications of the ACM, 31(5): 514-530, 1988.

G. Kant. Drawing planar graphs using the lmc-ordering. In Proc. 33th IEEE Symp. on Fundations of Computer Science, pages 101-110, 1992.

G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16:4-32, 1996.

G. Kar, B.P. Madden, and R.S. Gilbert. Heuristic layout algorithms for network management presentations services. IEEE Network, pages 29-36, November 1988.

J. Kawakita. The KJ method - a scientific approach to problem solving. Technical report, Kawakita Research Institute, Tokyo, 1975.

M.R. Kramer and J. van Leeuwen. The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. In F.P. Preparata, editor, Advances in Computing Research, volume 2, pages 129-146. JAI Press, Greenwich, Conn., 1985.

C.E. Leiserson. Area-efficient graph layouts (for VLSI). In Proceedings of the IEEE Symposium on the Fundations of Computer Science, pages 270-281, 1980.

K. Misue and K. Sugiyama. An overview of diagram based idea organizer: Dabductor. Technical Report IIAS-RR-93-3E, ISIS, Fujitsu Laboratories, 1993.

S. North. Drawing ranked digraphs with recursive clusters. In Proc. ALCOM Workshop on Graph Drawing '93, September 1993.

J. Nummenmaa and J. Tuomi. Constructing layouts for er-diagrams from visibility representations. In Proc. 9th Int. Conf. on Entity-Relationship Approach, pages 303-317. 1990.

A. Papakostas and I.G. Tollis. Improved algorithms and bounds for orthogonal drawings. In R. Tamassia and I.G. Tollis, editors, GD '94, volume 894 of Lecture Notes in Computer Science, pages 40-51. Springer-Verlag, 1994.

A. Papakostas and I.G. Tollis. A pairing technique for area-efficient orthogonal drawings. In Stephen. C. North, editor, GD '96, volume 1190 of Lecture Notes in Computer Science, pages 355-370. Springer-Verlag, 1997.

D. Reiner, G. Brown, M. Friedell, J. Lehmann, R. McKee, P. Rheingans, and A. Rosenthal. A database designer's workbench. In S. Spaccapietra, editor, Entity-Relationship Approach: Proc. 5th Int. Conf. on Entity-Relationship Approach (Dijon France 1987), pages 347-360, New York, N.Y., 1987. North-Holland.

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

J.A. Storer. On minimal node-cost planar embeddings. Networks. 14:181-212, 1984.

K. Sugiyama and K. Misue. Visualization of structural information: Automatic drawing of compound digraphs. IEEE Transactions on Software Engineering, 21(4):876-892, 1991.

R. Tamassia. New layout techniques for entity-relationship diagrams. In Proc. 4th Int. Conf. on Entity-Relationship Approach, pages 304-311. 1985.

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

R. Tamassia and I.G. Tollis. A unified approach to visibility representations of planar graphs. Discrete and Computational Geometry, 1(4):321-341, 1986.

R. Tamassia and I.G. Tollis. Efficient embedding of planar graphs in linear time. In Proc. IEEE Int. Symp. on Circuits and Systems, pages 495-498, 1987.

R. Tamassia and I.G. Tollis. Planar grid embedding in linear time. IEEE Trans. on Circuits and Systems, CAS-36(9):1230-1234, 1989.

R. Tamassia, I.G. Tollis, and J.S. Vitter. Lower bounds for planar orthogonal drawings of graphs. Information Processing Letters, 39:35-40, 1991.

J.D. Ullman. Computational Aspects of VLSI. Principles of Computer Science. Computer Science Press, Rockville, Md., 1984.

L. Valiant. Universality considerations in VLSI circuits. IEEE Transactions on Computers, C-30(2):135-140, 1981.

C.Williams, J. Rasure, and C. Hansen. The state of the art of visual languages for visualization. In Visualization 92, pages 202-209, 1992.