Logo

Login | Create Account

Graph Clustering I: Cycles of Cliques

Brandenburg, Franz J. (1998) Graph Clustering I: Cycles of Cliques. [Conference Paper]

Full text not available from this repository.

Abstract

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
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.180 Cluster
ID Code:78
Deposited By:Martinez Leon, Victoria
Deposited On:02 Nov 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

8. 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.

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

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

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

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

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

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

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

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

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

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

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

20. 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.

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.