A Separator Theorem for Planar Graphs
From MaRDI portal
Publication:3869371
DOI10.1137/0136016zbMath0432.05022OpenAlexW2038643780WikidataQ56453456 ScholiaQ56453456MaRDI QIDQ3869371
Richard J. Lipton, Robert Endre Tarjan
Publication date: 1979
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/47c4651a707a91db806a6034897e42e2530bb681
partitionplanar graphdivide-and-conquerpebblingpost office problemsparse systems of linear equations
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) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items (only showing first 100 items - show all)
Parameterized graph separation problems ⋮ On the maximum order of graphs embedded in surfaces ⋮ The 2-surviving rate of planar graphs without 5-cycles ⋮ Finding small simple cycle separators for 2-connected planar graphs ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ On the minimum corridor connection problem and other generalized geometric problems ⋮ Network decontamination with a single agent ⋮ Component-cardinality-constrained critical node problem in graphs ⋮ Edge separators for quasi-binary trees ⋮ Parallel nested dissection for path algebra computations ⋮ Collective tree spanners in graphs with bounded parameters ⋮ A faster algorithm for computing the principal sequence of partitions of a graph ⋮ 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 ⋮ On the stabbing number of a random Delaunay triangulation ⋮ Variable neighborhood search for the vertex separation problem ⋮ An application of the planar separator theorem to counting problems ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ 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 ⋮ Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Large processors are good in VLSI chips ⋮ Über Separatoren in planaren Graphen ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ Efficient approximate solution of sparse linear systems ⋮ Approximation algorithms for cutting a convex polyhedron out of a sphere ⋮ On the negative cost girth problem in planar networks ⋮ Crossings in grid drawings ⋮ On graph thickness, geometric thickness, and separator theorems ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Oblivious algorithms for multicores and networks of processors ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Compact and low delay routing labeling scheme for unit disk graphs ⋮ An exact algorithm for solving the vertex separator problem ⋮ Theory and application of width bounded geometric separators ⋮ Satisfiability, branch-width and Tseitin tautologies ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ Computational geometry in a curved world ⋮ Multilayer grid embeddings for VLSI ⋮ On cleaving a planar graph ⋮ Approximation algorithms for maximum independent set of pseudo-disks ⋮ A distributed shortest path algorithm for a planar network ⋮ Sparse direct factorizations through unassembled hyper-matrices ⋮ A lower bound on the area of permutation layouts ⋮ A survey of geodesic paths on 3D surfaces ⋮ Sublinear time width-bounded separators and their application to the protein side-chain packing problem ⋮ Packing, covering and tiling in two-dimensional spaces ⋮ Graph layouts via layered separators ⋮ Triangulating a simple polygon in linear time ⋮ Formula dissection: A parallel algorithm for constraint satisfaction ⋮ Metric uniformization and spectral bounds for graphs ⋮ Maximum size of a planar graph with given degree and even diameter ⋮ \(N\)-separators in planar graphs ⋮ \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs ⋮ Anticoloring of a family of grid graphs ⋮ Nonlinear lower bounds on the number of processors of circuits with sublinear separators ⋮ A nonlinear lower bound on the practical combinational complexity ⋮ Planar graph is on fire ⋮ New graph decompositions with applications to emulations ⋮ Computing planarity in computable planar graphs ⋮ An \(O(n\log n)\) algorithm for computing the link center of a simple polygon ⋮ Nested annealing: A provable improvement to simulated annealing ⋮ Exploiting planarity in separation routines for the symmetric traveling salesman problem ⋮ The MIN-cut and vertex separator problem ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Finding good approximate vertex and edge partitions is NP-hard ⋮ Dynamic algorithms for shortest paths in planar graphs ⋮ Ramsey numbers of cubes versus cliques ⋮ Locating facilities which interact: Some solvable cases ⋮ Anticoloring and separation of graphs ⋮ Every minor-closed property of sparse graphs is testable ⋮ Cubic polyhedral Ramanujan graphs with face size no larger than six ⋮ The slab dividing approach to solve the Euclidean \(P\)-center problem ⋮ A bipartite strengthening of the crossing Lemma ⋮ Edge separators for graphs of bounded genus with applications ⋮ On the number of binary characters needed to recover a phylogeny using maximum parsimony ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs ⋮ Single source shortest paths in \(H\)-minor free graphs ⋮ Communication tree problems ⋮ Optimal deterministic algorithms for 2-d and 3-d shallow cuttings ⋮ Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces ⋮ Efficient Union-Find for planar graphs and other sparse graph classes ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ 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 ⋮ \(L(p,q)\)-label coloring problem with application to channel allocation ⋮ Calculs de complexité relatifs à une méthode de dissection emboîtée ⋮ Decomposition by clique separators ⋮ The performance of multilective VLSI algorithms ⋮ A fast algorithm for minimum weight odd circuits and cuts in planar graphs
This page was built for publication: A Separator Theorem for Planar Graphs
