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: http://dx.doi.org/10.1007/3-540-63938-1_59).
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.
Repository Staff Only: item control page