A Separator Theorem for Planar Graphs
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Computational properties of argument systems satisfying graph-theoretic constraints
- Decomposition by clique separators
- The performance of multilective VLSI algorithms
- Finding small simple cycle separators for 2-connected planar graphs
- Parallel nested dissection for path algebra computations
- Approximation algorithms for weighted matching
- The analysis of a nested dissection algorithm
- Communication-efficient parallel algorithms for distributed random-access machines
- Designing networks with compact routing tables
- A random NC algorithm for depth first search
- An efficient parallel algorithm for updating minimum spanning trees
- An application of the planar separator theorem to counting problems
- A linear-processor algorithm for depth-first search in planar graphs
- Min Cut is NP-complete for edge weighted trees
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver)
- Lower bounds for synchronous circuits and planar circuits
- Subtree isomorphism is NC reducible to bipartite perfect matching
- Efficient approximate solution of sparse linear systems
- Triangulating a simple polygon in linear time
- -vertex separator is NP-hard even for 3-regular graphs
- Nonlinear lower bounds on the number of processors of circuits with sublinear separators
- An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
- Nested annealing: A provable improvement to simulated annealing
- Finding good approximate vertex and edge partitions is NP-hard
- The slab dividing approach to solve the Euclidean \(P\)-center problem
- Edge separators for graphs of bounded genus with applications
- Efficient Union-Find for planar graphs and other sparse graph classes
- A partial k-arboretum of graphs with bounded treewidth
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- The maximum clique problem
- Some combinatorial optimization problems arising from VLSI circuit design
- Graph theoretical issues in computer networks
- Two tapes versus one for off-line Turing machines
- A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
- Surface triangulations with isometric boundary
- Separators and structure prediction in sparse orthogonal factorization
- Treewidth for graphs with small chordality
- Combinatorial aspects of geometric graphs
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Bisection width of transposition graphs
- Divider-based algorithms for hierarchical tree partitioning.
- Generating irregular partitionable data structures
- Semi-dynamic breadth-first search in digraphs
- Numerical linear algebra algorithms and software
- Simple polytopes without small separators. II: Thurston's bound
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- The \(S\)-\textsc{labeling} problem: an algorithmic tour
- A quality and distance guided hybrid algorithm for the vertex separator problem
- How many lions are needed to clear a grid?
- General variable neighborhood search for computing graph separators
- Simple polytopes without small separators
- Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph
- Parameterized algorithms for stable matching with ties and incomplete lists
- Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
- Efficient heuristic algorithm for identifying critical nodes in planar networks
- Planar graphs without chordal 5-cycles are 2-good
- On classes of graphs with strongly sublinear separators
- The critical node detection problem in networks: a survey
- A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
- Counting models for 2SAT and 3SAT formulae
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- ``Global graph problems tend to be intractable
- Efficient parallel linear programming
- Voronoi diagrams with barriers and on polyhedra for minimal path planning
- Fast and efficient solution of path algebra problems
- An algorithm for colouring perfect planar graphs
- On the complexity of planar Boolean circuits
- Fragmentability of graphs
- An external memory data structure for shortest path queries
- Planarity-preserving clustering and embedding for large planar graphs
- Graph separators: A parameterized view
- Large planar graphs with given diameter and maximum degree
- Applications of the crossing number
- Tabu search for the BWC problem
- The size and depth of layered Boolean circuits
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Orthogonal drawings of graphs for the automation of VLSI circuit design
- Coloring invariants of knots and links are often intractable
- Packing and covering with non-piercing regions
- Faster approximate diameter and distance oracles in planar graphs
- On some tractable and hard instances for partial incentives and target set selection
- Solution methods for the vertex variant of the network system vulnerability analysis problem
- Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
- The one-cop-moves game on planar graphs
- Spectral threshold for extremal cyclic edge-connectivity
- Reconfiguring dominating sets in minor-closed graph classes
- An improved approximation for maximum \(k\)-dependent set on bipartite graphs
- Notes on graph product structure theory
- A sharp threshold phenomenon in string graphs
- Navigating planar topologies in near-optimal space and time
- Electrical flows over spanning trees
- Surviving rate of graphs and firefighter problem
- On the geometric set multicover problem
- On the discrepancies of graphs
- Local search is a PTAS for feedback vertex set in minor-free graphs
- On fractional fragility rates of graph classes
- Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
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)
