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
Simple polytopes without small separators. II: Thurston's bound, Graph separators: A parameterized view, The degree-diameter problem for outerplanar graphs, The searching over separators strategy to solve some NP-hard problems in subexponential time, Graph theoretic analysis of PLA folding heuristics, Maximum matchings in planar graphs via Gaussian elimination, Surface triangulations with isometric boundary, An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs, Surviving rate of graphs and firefighter problem, Large planar graphs with given diameter and maximum degree, The \(S\)-\textsc{labeling} problem: an algorithmic tour, Separators and structure prediction in sparse orthogonal factorization, A quality and distance guided hybrid algorithm for the vertex separator problem, How many lions are needed to clear a grid?, On the geometric set multicover problem, Treewidth for graphs with small chordality, Applications of the crossing number, Layered separators in minor-closed graph classes with applications, Multicuts in planar and bounded-genus graphs with bounded number of terminals, Combinatorial aspects of geometric graphs, General variable neighborhood search for computing graph separators, Simple polytopes without small separators, On the discrepancies of graphs, Tabu search for the BWC problem, On the maximum degree of path-pairable planar graphs, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Bisection width of transposition graphs, Grad and classes with bounded expansion. II: Algorithmic aspects, Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph, Local search is a PTAS for feedback vertex set in minor-free graphs, Succinct representation of labeled graphs, The size and depth of layered Boolean circuits, Almost exact matchings, Sharp separation and applications to exact and parameterized algorithms, Three problems about simple polygons, On fractional fragility rates of graph classes, Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators, Parameterized algorithms for stable matching with ties and incomplete lists, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, On approximating the \(d\)-girth of a graph, Divider-based algorithms for hierarchical tree partitioning., Vulnerability of nearest neighbor graphs, Orthogonal drawings of graphs for the automation of VLSI circuit design, Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs, A note on sublinear separators and expansion, Efficient heuristic algorithm for identifying critical nodes in planar networks, On the decay of crossing numbers, Coloring invariants of knots and links are often intractable, On the minimum load coloring problem, Efficient vertex-label distance oracles for planar graphs, Polynomial bounds for centered colorings on proper minor-closed graph classes, Planar graphs without chordal 5-cycles are 2-good, Packing and covering with non-piercing regions, On classes of graphs with strongly sublinear separators, The critical node detection problem in networks: a survey, Open problems around exact algorithms, A hybrid breakout local search and reinforcement learning approach to the vertex separator problem, Minimum vertex cover in ball graphs through local search, Faster approximate diameter and distance oracles in planar graphs, Join-reachability problems in directed graphs, Efficient parallel factorization and solution of structured and unstructured linear systems, The vertex separator problem: algorithms and computations, On some tractable and hard instances for partial incentives and target set selection, Counting models for 2SAT and 3SAT formulae, 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, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, On the convergence of the maximum likelihood estimator for the transition rate under a 2-state symmetric model, Subexponential algorithms for variants of the homomorphism problem in string graphs, The one-cop-moves game on planar graphs, Spectral threshold for extremal cyclic edge-connectivity, Reconfiguring dominating sets in minor-closed graph classes, Minimum fill-in: inapproximability and almost tight lower bounds, An improved approximation for maximum \(k\)-dependent set on bipartite graphs, Notes on graph product structure theory, ``Global graph problems tend to be intractable, Edge integrity of nearest neighbor graphs and separator theorems, Efficient parallel linear programming, A sharp threshold phenomenon in string graphs, 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, Comparing linear width parameters for directed graphs, Generating irregular partitionable data structures, On the complexity of planar Boolean circuits, Semi-dynamic breadth-first search in digraphs, Fragmentability of graphs, Numerical linear algebra algorithms and software, Navigating planar topologies in near-optimal space and time, Electrical flows over spanning trees, Separator-based graph embedding into multidimensional grids with small edge-congestion, On vertex rankings of graphs and its relatives, An external memory data structure for shortest path queries, 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, Planarity-preserving clustering and embedding for large planar graphs, 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, Well-mixing vertices and almost expanders, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, A Lower Bound for the Query Phase of Contraction Hierarchies and Hub Labels, Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs, Asymptotic dimension of planes and planar graphs, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Communication Complexity and Lower Bounds on Multilective Computations, Crossing numbers of random graphs, Complexity and Polynomially Solvable Special Cases of QUBO, Continuous quadratic programming formulations of optimization problems on graphs, Medial Axis Based Routing Has Constant Load Balancing Factor, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Minimal elimination of planar graphs, Fixed-Parameter Tractability of Treewidth and Pathwidth, Bandwidth, treewidth, separators, expansion, and universality, Maximum size of a planar graph with given degree and diameter, A dynamic separator algorithm, A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs, A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes, Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs, Graph separation techniques for quadratic zero-one programming, Treasure Hunt with Advice, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs, Embedding Outerplanar Graphs in Small Books, On temporal graph exploration, Prioritized Metric Structures and Embedding, An O(n log n) algorithm for computing a link center in a simple polygon, An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications, Communication throughput of interconnection networks, Visibility-based pursuit-evasion in a polygonal environment, Reordering Strategy for Blocking Optimization in Sparse Linear Solvers, Graph coloring with no large monochromatic components, Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem, An Application of Generalized Tree Pebbling to Sparse Matrix Factorization, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Stack and Queue Layouts via Layered Separators, Dismantling Sparse Random Graphs, Shortcutting Planar Digraphs, Approximating the k-Level in Three-Dimensional Plane Arrangements, Finding and Using Expanders in Locally Sparse Graphs, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Unnamed Item, Unnamed Item, On treewidth, separators and Yao's garbling, Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting, É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, Constructing near spanning trees with few local inspections, Parameters Tied to Treewidth, Computation in Causal Graphs, Provably Shorter Regular Expressions from Deterministic Finite Automata, On the Block Number of Graphs, Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere, Knowledge Discovery in Graphs Through Vertex Separation, A Separator Theorem for Nonplanar Graphs, Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs, PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA, Fast and efficient linear programming and linear least-squares computations, Square Root SAM: Simultaneous Localization and Mapping via Square Root Information Smoothing, The vertex separator problem: a polyhedral investigation, Shortest-path queries in static networks, Unnamed Item, Sublinear Graph Approximation Algorithms, Transitive-Closure Spanners: A Survey, Exact algorithms for the Hamiltonian cycle problem in planar graphs, A Separator Theorem for Chordal Graphs, Planar graphs, negative weight edges, shortest paths, and near linear time, A PTAS for a disc covering problem using width-bounded separators, The HOMFLY-PT polynomial is fixed-parameter tractable, Unnamed Item, Layouts of Expander Graphs, 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, Decompositions of Triangle-Dense Graphs, On Approximating the d-Girth of a Graph, Strongly Sublinear Separators and Polynomial Expansion, A nonlinear lower bound on the practical combinational complexity, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, Distributed Corruption Detection in Networks, An Efficient Partitioning Oracle for Bounded-Treewidth Graphs, A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, Bidimensionality and Kernels, Universal knot diagrams, Via Detours to I/O-Efficient Shortest Paths, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Planar k-Path in Subexponential Time and Polynomial Space, Separators in region intersection graphs, Collective Tree Spanners for Unit Disk Graphs with Applications, Sublinear Separators in Intersection Graphs of Convex Shapes, Isometric Universal Graphs, TOWARDS MORE EFFICIENT INFECTION AND FIRE FIGHTING, Faster Approximate Diameter and Distance Oracles in Planar Graphs, The first order definability of graphs with separators via the Ehrenfeucht game, Unnamed Item, Graph minors and the crossing number of graphs, Short and Simple Cycle Separators in Planar Graphs, Efficient Point-to-Point Resistance Distance Queries in Large Graphs, Clustered 3-colouring graphs of bounded degree, Space-efficient algorithms for reachability in directed geometric graphs, Metropolized Knockoff Sampling, Non‐planarity of SL(2,Z)$\operatorname{SL}(2,\mathbb {Z})$‐orbits of origamis in H(2)$\mathcal {H}(2)$, On matchings, T‐joins, and arc routing in road networks, Reliable Spanners for Metric Spaces, Gap sets for the spectra of cubic graphs, On weighted sublinear separators, Modularity of minor‐free graphs, Clique-based separators for geometric intersection graphs, Counting cycles on planar graphs in subexponential time, Planarization of graphs embedded on surfaces, Non-existence of annular separators in geometric graphs, Counting cycles on planar graphs in subexponential time, Population-based iterated greedy algorithm for the S-labeling problem, Vertex Fault-Tolerant Geometric Spanners for Weighted Points, New approximation results on graph matching and related problems, Fast separator decomposition for finite element meshes, Edge separators for graphs excluding a minor, Non-planarity of Markoff graphs \(\mod p\), The degree/diameter problem in maximal planar bipartite graphs, An efficient parallel algorithm for shortest paths in planar layered digraphs, Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions., Shortest rectilinear path queries to rectangles in a rectangular domain, A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions, A survey of direct methods for sparse linear systems, Faster shortest-path algorithms for planar graphs, Recursive conditioning, Min-max-boundary domain decomposition, Multiphase mesh partitioning, Efficient dynamic approximate distance oracles for vertex-labeled planar graphs, Spectral geometry, link complements and surgery diagrams, General lower bounds for the minor crossing number of graphs, A Bipartite Strengthening of the Crossing Lemma, How to walk your dog in the mountains with no magic leash, The degree/diameter problem in maximal planar bipartite graphs, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Balanced line separators of unit disk graphs, Fast and compact planar embeddings, Approximating small balanced vertex separators in almost linear time, BOUNDARY-OPTIMAL TRIANGULATION FLOODING, Many distances in planar graphs, Tractable minor-free generalization of planar zero-field Ising models, Unnamed Item, Separation profiles of graphs of fractals