{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/30169"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/30169","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"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(sqrt(g/n)) and vertex bisectors of size O(sqrt(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.","abstract_html":"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(sqrt(g/n)) and vertex bisectors of size O(sqrt(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.","abstract_has_math":false,"creators":["Kelner, Jonathan, 1980-"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Daniel Spielman."],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005","date_published":"2005","updated_at":"2026-07-22T22:22:30Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/30169","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Daniel Spielman."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Kelner, Jonathan, 1980-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-03-24T18:26:04Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-03-24T18:26:04Z"]},{"key":"dc:date.issued","label":"Date","values":["2005"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/30169"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.","Includes bibliographical references (leaves 37-39)."]},{"key":"dc:description.abstract","label":"Abstract","values":["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(sqrt(g/n)) and vertex bisectors of size O(sqrt(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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus"]}]}],"canonical_facts":{"dc:contributor.advisor":["Daniel Spielman."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Kelner, Jonathan, 1980-"],"dc:date.accessioned":["2006-03-24T18:26:04Z"],"dc:date.available":["2006-03-24T18:26:04Z"],"dc:date.issued":["2005"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.","Includes bibliographical references (leaves 37-39)."],"dc:description.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(sqrt(g/n)) and vertex bisectors of size O(sqrt(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."],"dc:description.degree":["S.M."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/30169"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:30Z"}