A Separator Theorem for Planar Graphs
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Constructing near spanning trees with few local inspections
- Vulnerability of nearest neighbor graphs
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- A nonlinear lower bound on the practical combinational complexity
- An external memory data structure for shortest path queries
- Recursive conditioning
- Graph theoretic analysis of PLA folding heuristics
- On the decay of crossing numbers
- BOUNDARY-OPTIMAL TRIANGULATION FLOODING
- An efficient partitioning oracle for bounded-treewidth graphs
- Stable approximation algorithms for dominating set and independent set
- Electrical flows over spanning trees
- Knowledge discovery in graphs through vertex separation
- Shortest rectilinear path queries to rectangles in a rectangular domain
- Separators in region intersection graphs
- Algorithms for approximate shortest path queries on weighted polyhedral surfaces
- The MIN-cut and vertex separator problem
- Dynamic algorithms for shortest paths in planar graphs
- Locating facilities which interact: Some solvable cases
- Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
- A survey of geodesic paths on 3D surfaces
- Hyperbolic groups with logarithmic separation profile
- Edge integrity of nearest neighbor graphs and separator theorems
- Cubic polyhedral Ramanujan graphs with face size no larger than six
- Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
- Anticoloring and separation of graphs
- Layered separators in minor-closed graph classes with applications
- Sharp separation and applications to exact and parameterized algorithms
- A survey of direct methods for sparse linear systems
- How to catch marathon cheaters: new approximation algorithms for tracking paths
- Surviving rate of graphs and firefighter problem
- Lower bounds for synchronous circuits and planar circuits
- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- Parallel nested dissection for path algebra computations
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- The maximum clique problem
- Numerical linear algebra algorithms and software
- An efficient parallel algorithm for updating minimum spanning trees
- Isometric universal graphs
- The degree/diameter problem in maximal planar bipartite graphs
- The degree/diameter problem in maximal planar bipartite graphs
- Satisfiability, branch-width and Tseitin tautologies
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- Crossings in grid drawings
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Semi-dynamic breadth-first search in digraphs
- Finding small simple cycle separators for 2-connected planar graphs
- A bipartite strengthening of the crossing Lemma
- Planarization of graphs embedded on surfaces
- On the maximum order of graphs embedded in surfaces
- Component-cardinality-constrained critical node problem in graphs
- On the number of binary characters needed to recover a phylogeny using maximum parsimony
- Graph separators: A parameterized view
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- Open problems around exact algorithms
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Tangled paths: a random graph model from Mallows permutations
- Communication-efficient parallel algorithms for distributed random-access machines
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Voronoi diagrams with barriers and on polyhedra for minimal path planning
- On approximating the \(d\)-girth of a graph
- Approximation algorithms for polynomial-expansion and low-density graphs
- An O(n n) algorithm for computing a link center in a simple polygon
- Faster approximate diameter and distance oracles in planar graphs
- Compact and low delay routing labeling scheme for unit disk graphs
- On vertex rankings of graphs and its relatives
- Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting
- Efficient Point-to-Point Resistance Distance Queries in Large Graphs
- Product structure extension of the Alon-Seymour-Thomas theorem
- scientific article; zbMATH DE number 7378687 (Why is no real title available?)
- Efficient parallel factorization and solution of structured and unstructured linear systems
- A Separator Theorem for Chordal Graphs
- Collective tree spanners in graphs with bounded parameters
- A faster algorithm for computing the principal sequence of partitions of a graph
- Parameterized graph separation problems
- Separator-based graph embedding into multidimensional grids with small edge-congestion
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Non-existence of annular separators in geometric 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
- The 2-surviving rate of planar graphs without 5-cycles
- A PTAS for a disc covering problem using width-bounded separators
- Sublinear time width-bounded separators and their application to the protein side-chain packing problem
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Improved outerplanarity bounds for planar graphs
- Tractable minor-free generalization of planar zero-field Ising models
- Some combinatorial optimization problems arising from VLSI circuit design
- Simple polytopes without small separators. II: Thurston's bound
- An Application of Generalized Tree Pebbling to Sparse Matrix Factorization
- Clustered 3-colouring graphs of bounded degree
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Many distances in planar graphs
- Planar graphs without chordal 5-cycles are 2-good
- \(N\)-separators in planar graphs
- Maximum size of a planar graph with given degree and even diameter
- Fast and efficient solution of path algebra problems
- On some tractable and hard instances for partial incentives and target set selection
- Packing and covering with non-piercing regions
- Single source shortest paths in H-minor free graphs
- An algorithm for colouring perfect planar graphs
This page was built for publication: A Separator Theorem for Planar Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3869371)
