Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus

ABSTRACT

In this paper, we address two longstanding questions about finding good separators in graphs of bounded genus and degree: 1. It is a classical result of Gilbert, Hutchinson, and Tarjan [12] that one can find asymptotically optimal separators on these graphs if he is given both the graph and an embedding of it onto a low genus surface. Does there exist a simple, efficient algorithm to find these separators given only the graph and not the embedding? 2. In practice, spectral partitioning heuristics work extremely well on these graphs. Is there a theoretical reason why this should be the case.We resolve these two questions by showing that a simple spectral algorithm finds separators of cut ratio O(√g/n) and vertex bisectors of size O(√gn) in these graphs, both of which are optimal. As our main technical lemma, we prove an O(g/n) bound on the second smallest eigenvalue of the Laplacian of such graphs and show that this is tight, thereby resolving a conjecture of Spielman and Teng. While this lemma is essentially combinatorial in nature, its proof comes from continuous mathematics, drawing on the theory of circle packings and the geometry of compact Riemann surfaces.

References

1. Alon, N., Seymour, P., and Thomas, R. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3, 4 (October 1990), 801--808.
2. Alpert, C. J., and Kahng, A. B. Recent directions in netlist partitioning: a survey. Integration: the VLSI Journal 19 (1995), 1--81.
3. Beardon, A. F., and Stephenson, K. The uniformization theorem for circle packings. Indiana University Mathematics Journal 39 (1990), 1383--1425.
4. Bowers, P., and Stephenson, K. Uniformizing dessins and Belyi maps via circle packing. To appear. Available at http://web. math. fsu. edu/ bowers/Papers/recentPapers. html, 2003.
5. Chan, P., Schlag, M., and Zien, J. Spectral k-way ratio cut partitioning and clustering. In Symposium on Integrated Systems (1993).
6. Chan, T., and Resasco, D. C. A framework for the analysis and construction of domain decomposition preconditioners. Tech. rep., UCLA, 1987.
7. Chan, T., and Smith, B. Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes. Contemporary Mathematics (1993), 1--14.
8. Djidjev, H. A linear algorithm for partitioning graphs. Comptes rendus de l'Academie Bulgare des Sciences 35 (1982), 1053--1056.
9. Djidjev, H., and Reif, J. An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing (1991), pp. 337--348.
10. Filotti, I., Miller, G., and Reif, J. On determining the genus of a graph in o(vO(g)) steps. In Proceedings of the 11th Annual ACM Symposium on the Theory of Computing (1979), pp. 27--37.
11. Forster, O. Lectures on Riemann Surfaces. Springer-Verlag, 1981.
12. Gilbert, J., Hutchinson, J., and Tarjan, R. A separation theorem for graphs of bounded genus. Journal of Algorithms 5 (1984), 391--407.
13. Guattery, S., and Miller, G. On the performance of the spectral graph partitioning methods. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (1995), pp. 233--242.
14. Hagen, L., and Kahng, A. B. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on computer-aided design 11, 9 (September 1992), 1074--1085.
15. He, Z. -X., and Schramm, O. Fixed points, Koebe uniformization and circle packings. Annals of Mathematics 137 (1993), 369--406.
16. Lipton, R. J., and Tarjan, R. E. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics 36 (April 1979), 177--189.
17. McCaughan, G. A recurrence/transience result for circle packings. Proceedings of the American Mathematical Society 126, 12 (December 1998), 3647--3656.
18. Mihail, G. Conductance and convergence of markov chains---a combinatorial treatment of expanders. In Proceedings of the 29th Annual IEEE Conference on Foundations of Computer Scienc (1989), pp. 526--531.
19. Rodin, B., and Sullivan, D. The convergence of circle packings to the Riemann mapping. J. Differential Geometry 26 (1987), 349--360.
20. Simon, H. Partitioning of unstructured problems for parallel processing. computer systems in engineering 2(2/3) (1991), 135--148.
21. Spielman, D. A., and Teng, S. -H. Spectral partitioning works: Planar graphs and finite element meshes. In Proceedings of the 37th Annual IEEE Conference on Foundations of Computer Science (1996).
22. Stephenson, K. Circle packing and discrete analytic function theory. Available online at http://www. math. utk. edu/ kens.
23. Thomassen, C. The graph genus problem is np-complete. Journal of Algorithms 10, 4 (December 1989), 568--576.
24. Williams, R. D. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Tech. rep., California Institute of Technology, 1990.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Design and analysis of algorithms