A separator theorem for graphs of bounded genus

DOI10.1016/0196-6774(84)90019-1zbMath0556.05022OpenAlexW2073558110MaRDI QIDQ3220606

John R. Gilbert, Joan P. Hutchinson, Robert Endre Tarjan

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6346

zbMATH Keywords

planar graphsgraph bisectiongraph algorithmsseparators in graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

Related Items (67)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ A Five-Color Theorem for Graphs on Surfaces ⋮ A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Asymptotic dimension of planes and planar graphs ⋮ On the black-box complexity of Sperner's Lemma ⋮ Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Cheeger constants of surfaces and isoperimetric inequalities ⋮ Approximation algorithms for weighted matching ⋮ The analysis of a nested dissection algorithm ⋮ Separators and structure prediction in sparse orthogonal factorization ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Polynomial-time self-reducibility: theoretical motivations and practical results^∗ ⋮ Local optimization on graphs ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ Layered separators in minor-closed graph classes with applications ⋮ Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm ⋮ The game of overprescribed Cops and Robbers played on graphs ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Non‐planarity of SL(2,Z)$\operatorname{SL}(2,\mathbb {Z})$‐orbits of origamis in H(2)$\mathcal {H}(2)$ ⋮ Modularity of minor‐free graphs ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Planarization of graphs embedded on surfaces ⋮ Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Shortcutting Planar Digraphs ⋮ The size and depth of layered Boolean circuits ⋮ Approximation algorithms via contraction decomposition ⋮ Theory and application of width bounded geometric separators ⋮ On the Fiedler value of large planar graphs ⋮ Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées ⋮ Vulnerability of nearest neighbor graphs ⋮ Sublinear time width-bounded separators and their application to the protein side-chain packing problem ⋮ Distributional limits of Riemannian manifolds and graphs with sublinear genus growth ⋮ Metric uniformization and spectral bounds for graphs ⋮ Separator theorems and Turán-type results for planar intersection graphs ⋮ A Separator Theorem for Nonplanar Graphs ⋮ On classes of graphs with strongly sublinear separators ⋮ Edge separators for graphs of bounded genus with applications ⋮ Shortest-path queries in static networks ⋮ Faster shortest-path algorithms for planar graphs ⋮ Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs ⋮ Min-max-boundary domain decomposition ⋮ A Separator Theorem for Chordal Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Separator Theorem for String Graphs and its Applications ⋮ A Separator Theorem for String Graphs and Its Applications ⋮ MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING ⋮ General lower bounds for the minor crossing number of graphs ⋮ Strongly Sublinear Separators and Polynomial Expansion ⋮ Balanced line separators of unit disk graphs ⋮ Expanding and forwarding ⋮ Approximating small balanced vertex separators in almost linear time ⋮ Reconfiguring dominating sets in minor-closed graph classes ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ ``Global graph problems tend to be intractable ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes ⋮ The Parameterized Complexity of Finding a 2-Sphere in a Simplicial Complex ⋮ Hyperbolic and parabolic unimodular random maps ⋮ Enhanced algorithms for local search ⋮ Singularities, expanders and topology of maps. I: Homology versus volume in the spaces of cycles ⋮ The first order definability of graphs with separators via the Ehrenfeucht game ⋮ Fragmentability of graphs ⋮ Short and Simple Cycle Separators in Planar Graphs

This page was built for publication: A separator theorem for graphs of bounded genus