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 , 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

Actions (login required)

View Item View Item