A separator theorem for graphs of bounded genus
From MaRDI portal
Recommendations
Cited in
(97)- Enhanced algorithms for local search
- Singularities, expanders and topology of maps. I: Homology versus volume in the spaces of cycles
- Approximation algorithms for weighted matching
- The analysis of a nested dissection algorithm
- Local optimization on graphs
- On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
- Edge separators for graphs of bounded genus with applications
- A partial k-arboretum of graphs with bounded treewidth
- Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
- Separators and structure prediction in sparse orthogonal factorization
- Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
- On classes of graphs with strongly sublinear separators
- Expanding and forwarding
- ``Global graph problems tend to be intractable
- The separator theorem for rooted directed vertex graphs
- Fragmentability of graphs
- The size and depth of layered Boolean circuits
- Approximation algorithms via contraction decomposition
- Reconfiguring dominating sets in minor-closed graph classes
- Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Hyperbolic and parabolic unimodular random maps
- Layered separators in minor-closed graph classes with applications
- The game of overprescribed Cops and Robbers played on graphs
- On the Fiedler value of large planar graphs
- Vulnerability of nearest neighbor graphs
- Distributional limits of Riemannian manifolds and graphs with sublinear genus growth
- The first order definability of graphs with separators via the Ehrenfeucht game
- Three-coloring triangle-free graphs on surfaces. VII. A linear-time algorithm
- Strongly sublinear separators and polynomial expansion
- A generalization of Spira's theorem and circuits with small segregators or separators
- A separator theorem for string graphs and its applications
- Cheeger constants of surfaces and isoperimetric inequalities
- A Five-Color Theorem for Graphs on Surfaces
- A Separator Theorem for Chordal Graphs
- A generalization of Spira's theorem and circuits with small segregators or separators
- The Bidimensional Theory of Bounded-Genus Graphs
- A Heuristic Algorithm for Small Separators in Arbitrary Graphs
- Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
- A Separator Theorem for String Graphs and Its Applications
- MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING
- scientific article; zbMATH DE number 3946182 (Why is no real title available?)
- scientific article; zbMATH DE number 3970774 (Why is no real title available?)
- É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
- A Separator Theorem for Nonplanar Graphs
- scientific article; zbMATH DE number 16297 (Why is no real title available?)
- Polynomial-time self-reducibility: theoretical motivations and practical results∗
- Edge Separators of Planar and Outerplanar Graphs With Applications
- scientific article; zbMATH DE number 4127226 (Why is no real title available?)
- scientific article; zbMATH DE number 219242 (Why is no real title available?)
- scientific article; zbMATH DE number 4117852 (Why is no real title available?)
- Shortcutting Planar Digraphs
- Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
- Sublinear separators in intersection graphs of convex shapes
- Asymptotic dimension of planes and planar graphs
- Almost tight lower bounds for hard cutting problems in embedded graphs
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- Shortest-path queries in static networks
- Asymptotic Bounds on the Integrity of Graphs and Separator Theorems for Graphs
- The parameterized complexity of finding a 2-sphere in a simplicial complex
- Short and simple cycle separators in planar graphs
- Structure of graphs with locally restricted crossings
- Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
- Faster shortest-path algorithms for planar graphs
- Balanced line separators of unit disk graphs
- Approximating small balanced vertex separators in almost linear time
- Min-max-boundary domain decomposition
- General lower bounds for the minor crossing number of graphs
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces
- 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
- Planarization of graphs embedded on surfaces
- Theory and application of width bounded geometric separators
- Product structure extension of the Alon-Seymour-Thomas theorem
- Metric uniformization and spectral bounds for graphs
- Pursuit-evasion in graphs: zombies, lazy zombies and a survivor
- Product structure of graphs with an excluded minor
- Space-efficient graph coarsening with applications to succinct planar encodings
- Product structure of graph classes with strongly sublinear separators
- On hypergraph supports (extended abstract)
- Chasing puppies: mobile beacon routing on closed curves
- Shortest path separators in unit disk graphs
- Clustered independence and bounded treewidth
- Defective and clustered colouring of graphs with given girth
- A WSPD, separator and small tree cover for c-packed graphs
- Sublinear hitting sets for some geometric graphs
- On the (in)approximability of the monitoring edge geodetic set problem
- On supports for graphs of bounded genus
- How to catch marathon cheaters: new approximation algorithms for tracking paths
- On the black-box complexity of Sperner's Lemma
- Collective tree spanners in graphs with bounded parameters
- Spectral partitioning works: planar graphs and finite element meshes
- Sublinear separators, fragility and subexponential expansion
- Sublinear time width-bounded separators and their application to the protein side-chain packing problem
- Separator theorems and Turán-type results for planar intersection graphs
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
This page was built for publication: A separator theorem for graphs of bounded genus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3220606)
