GRID: An Intercative Tool for Computing Orthogonal Drawings with the Minimum Number of Bends

Didimo, Walter and Leonforte, Antonio (1998) GRID: An Intercative Tool for Computing Orthogonal Drawings with the Minimum Number of Bends. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 309-316 (Official URL:

Full text not available from this repository.


In this paper we present a new interactive tool for computing orthogonal grid drawings of planar graphs. The tool is based on GDToolkit, an object-oriented library of classes for handling graphs and computing their layout. GDToolkit is built on LEDA (an efficient library of data types and algorithms) and currently implements three orthogonal layout methods. Especially, we provide a new branch-and-bound algorithm choosing a planar embedding in order to minimize the number of bends. The enumeration schema of the branch-and-bound algorithm is based on the GDToolkit SPQR-tree class (as far as we know, the only existing SPQR-tree implementation). The tool offers an interactive grapical interface to the branch-and-bound algorithm, which allows to edit the embedding, to execute the algorithm step by step and to view partial results. It also gives qualtiy measures on the drawing, and quantitative measures on the algorithm's performance.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_74
Classifications:M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:132

Repository Staff Only: item control page


P. Bertolazzi, G. Di Battista and W. Didimo. Computing Orthogonal Drawings with the Minimum Number of Bends. In Proc. Workshop Algorithms Data Struct., 1997 (to appear).

G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Comput. Geom. Theory Appl., 4:235-282, 1994.

G. Di Battista, G. Liotta, M. Strani and F. Vargiu. Diagram Server. Proceedings of Advances Visual Interfaces, 36:415-417, 1992.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996.

M. Fröhlich and M. Werner. Demonstration of the Interactive Graph Visualization System da Vinci. Lecture Notes in Computer Science, 894:266-269, 1994.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear palanarity testing. Submitted to SIAM Journal on Computing, 1995.

A. Garg and R. Tamassia. GIOTTO3D: A System for Visualizing Hierarchical Structures in 3D. In Symposium Graph Drawing, GD '96, LNCS, 1190, 1996.

M. Himsolt. The Graphlet System. In Symposium Graph Drawing, GD '96, LNCS, 1190, 1996.

J. Hopcroft and R.E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2:135-158, 1973.

D.E. Knuth. The Stanfort Graph Base: a platform for combinatorial algorithms. Stanford University, 1993.

K.Mehlhorn and S. Näher. LEDA: a platform for combinatorial and geometric computing. Commun. ACM, 38:96-102, 1995.

T. Nishizeki and N. Chiba. Planar graphs: Theory and algorithms. Ann. Discrete Math., 32, 1988.

A. Scott. A Survey of Graph Drawing Systems. Technical Report 95-06., Department of Computer Science University of Newcastle, Australia, 1995.

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

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

Tom Sawyer Software. Tom Sawyer Graph Layout Toolkit. Tom Sawyer Software Corporation, 1824B Fourth Street, Berkley, CA94710, USA.