Graph Clustering Using Multiway Ratio Cut (Software Demonstration)

Roxborough, Tom and Sen, Arunabha (1998) Graph Clustering Using Multiway Ratio Cut (Software Demonstration). In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 291-296 (Official URL:

Full text not available from this repository.


Identifying the natural clusters of nodes in a graph and treating them as supernodes or metanodes for a higher level graph (on an abstract graph) is a technique used for the reduction of visual complexity of graphs with a large number of nodes. In this paper we report on the implementation of a clustering algorithm based on the idea of ratio cut, a well known technique used for circuit partitioning in the VLSI domain. The algorithm is implemented in WINDOWS95/NT environment. The performance of the clustering algorithm on some large graphs obtained from the archives of Bell Laboratories is presented.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_71
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
S Software and Systems > S.001 General
P Styles > P.180 Cluster
ID Code:85

Repository Staff Only: item control page


R. Sablowski and A. Frick, "Automatic Graph Clustering," Proceedings of Graph Drawing '96, Berkeley, California, September, 1996.

U. Dogrusoz, B. Madden and P. Madden, "Circular Layout in the Graph Layout Toolkit," Proceedings of Graph Drawing '96, Berkeley, California, September, 1996.

P. Eades, "Multilevel Visualization of Clustered Graphs," Proceedings of Graph Drawing '96, Berkeley, California, September, 1996.

Y.C. Wei and C.K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs," IEEE Transactions on Computer Aided Design, vol.10, no.7, pp.911-921, July 1991.

C.J. Alpert and A.B. Kahng, "Recent Directions in Netlist Partitioning: A Survey," INTEGRATION: the VLSI journal, vol. 19, pp.1-81, 1995.

D. Kimmelman, B. Leban, T. Roth, D. Zernik "Dynamic Graph Abstraction for Effective Software Visualization," The Australian Computer Journal, vol. 27, no.4, pp.129-137, Nov 1995.

F.J. Brandenburg, M. Himsolt and K. Skodinis, "Graph Clustering: Circles of Cliques," submitted to Graph Drawing '97.