Graph Clustering I: Cycles of Cliques

Brandenburg, Franz J. (1998) Graph Clustering I: Cycles of Cliques. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 158-168 (Official URL:

Full text not available from this repository.


A graph is a cycle of cliques, if its set of vertices can be partitioned into clusters, such that each cluster is a clique and the cliques form a cycle. Then there is a partition of the set of edges into inner edges of the cliques and interconnection edges between the clusters. Cycles of cliques are special instance of two-level clustered graphs. Such graphs are drawn by a two phase method: draw the top level graph and then browse into the clusters. In general, it is NP-hard whether or not a graph is a two-level clustered graph of a particular type, e.g. a clique or a planar graph or a triangle of cliques. However, it is efficiently solvable whether or nor a graph is a path of cliques or is a large cycle of cliques.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_59
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.180 Cluster
ID Code:78

Repository Staff Only: item control page


C.J. Alpert and A.B. Kahng: Recent directions in netlist partitioning: a survey. Integration, the VLSI J. 19 (1995), 1-18.

J. Bosik: Decompositions of Graphs. Kluvwer Academic Publishers, Dordrecht (1990).

F.J. Brandenburg: Designing graph drawings by layout graph grammars. Graph Drawing 94, LNCS 894 (1995), 416-427.

R.C. Brewster, P. Hell and G. MacGillivray: The complexity of restricted graph homomorphisms. Discrete Mathematics 167/168 (1997), 145-154.

U. Dogrusöz, B. Madden and P. Madden: Circular layout in the graph layout toolkit. Graph Drawing 96, LNCS 1190 (1997), 92-100.

D. Dor and M. Tarsi: Graph decomposition in NP-complete: proof of Holyer's conjecture. SIAM J. Comput. 26 (1997), 1166-1187.

P. Eades and Q.W. Feng: Multilevel visualization of clustered graphs. Graph Drawing 96, LNCS 1190 (1997), 101-112.

P. Eades, Q.W. Feng and X. Lin: Straight-line drawing algorithms for hierarchical graphs and clustered graphs. Graph Drawing 96, LNCS 1190 (1997), 113-128.

P. Eades, J. Marks and S. North: Graph-Drawing Contest Report. Graph Drawing 96, LNCS 1190 (1997), 129-138.

M.R. Garey and D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979).

D.J. Geschwindt and M.T. Murthagh: A recursive algorithm for drawing hierarchical graphs. Technical Report CS-89-02, Williams College, Williamstown (1989).

D. Harel: On visual formalisms. Comm. ACM 31(1988). 514-530.

P. Hell and J. Nesetril: On the complexity of H-coloring. J. of Combinatorial Theory, Series B 48 (1990), 92-110.

M. Himsolt: Konzeption und Implementierung von Grapheneditoren. Shaker Verlag, Aachen (1993).

I. Holyer: The NP-completeness of some edge partition problems. SIAM J. Comput., 10 (1981), 713-717.

J. Kratochvíl: String Graphs. II. Recognizing string graphs is NP-Hard. J. of Combinatorial Theory, Series B 52 (1991), 67-78.

J. Kratochvíl, M. Goljan and P. Kucera: String Graphs. Academia, Prague (1986).

T. Lengauer: Combinatorial Algorithms for Integrated Circuit Layout. Wiley-Teubner Series (1990).

U. Manber: Introduction to Algorithms a Creative Approach. Addison Wesley, Reading (1989).

E.B. Messinger, L.A. Rowe and R.R. Henry: A divide- and conquer algorithm for the automatic layout of large directed graphs. IEEE Trans. Systems Man Cybernetics 21 (1991), 1-12.

R. Sablowski and A. Frick: Automatic graph clustering. Graph Drawing 96, LNCS 1190 (1997), 396-400.

F.-S. Shieh and C.L. McCreary: Directed graphs drawing by clan-based decomposition. Graph Drawing 95, LNCS 1027 (1996), 472-482.

K. Sugiyama and K. Misue: Visualization of structural information: automatic drawing of compound graphs . IEEE Trans. Systems Man Cybernetics 21 (1991), 876-792.

R.E. Tarjan: Decomposition by clique separators. Discrete Math. 55 (1985), 221-232.

S.H. Whitesides: An algorithm for finding clique cut-sets. Inf. Proc. Letters 12 (1981), 31-32.