Applications of a Planar Separator Theorem

DOI10.1137/0209046zbMath0456.68077OpenAlexW1982180670WikidataQ56210427 ScholiaQ56210427MaRDI QIDQ3906439

Richard J. Lipton, Robert Endre Tarjan

Publication date: 1980

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0209046

zbMATH Keywords

algorithm matching planar graphs maximum independent set graph embedding divide-and-conquer pebbling Boolean circuit complexity space-time tradeoffs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering, On directed analogues of expander and hyperfinite graph sequences, Rooted Uniform Monotone Minimum Spanning Trees, Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs, On the minimum cut separator problem, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Fixed-Parameter Tractability of Treewidth and Pathwidth, Cheeger constants of surfaces and isoperimetric inequalities, Resolving Loads with Positive Interior Stresses, Graph separation techniques for quadratic zero-one programming, Genus characterizes the complexity of certain graph problems: Some tight results, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?, Planarity and Genus of Sparse Random Bipartite Graphs, On the Power of Tree-Depth for Fully Polynomial FPT Algorithms, Efficient algorithms for solving systems of linear equations and path problems, Facial reduction for symmetry reduced semidefinite and doubly nonnegative programs, Maximum matchings in geometric intersection graphs, A note on the SDP relaxation of the minimum cut problem, On matchings, T‐joins, and arc routing in road networks, Complexity and Algorithms for Well-Structured k-SAT Instances, On weighted sublinear separators, An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³, Obtaining a Planar Graph by Vertex Deletion, Unnamed Item, Unnamed Item, Obtaining a planar graph by vertex deletion, Sharp separation and applications to exact and parameterized algorithms, New approximation results on graph matching and related problems, On treewidth, separators and Yao's garbling, A variation on the min cut linear arrangement problem, New exact algorithms for the 2-constraint satisfaction problem, Bounds on half graph orders in powers of sparse 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 theory of guaranteed search on graphs, An efficient parallel algorithm for shortest paths in planar layered digraphs, The approximation of maximum subgraph problems, Better distance labeling for unweighted planar graphs, Shortest rectilinear path queries to rectangles in a rectangular domain, Open problems around exact algorithms, Competitive graph searches, The vertex separator problem: a polyhedral investigation, Computing largest empty circles with location constraints, Approximation algorithms for maximum two-dimensional pattern matching, Unnamed Item, Exact algorithms for the Hamiltonian cycle problem in planar graphs, A Separator Theorem for Chordal Graphs, Power indices and easier hard problems, ON GEOMETRIC PATH QUERY PROBLEMS, A Separator Theorem for String Graphs and its Applications, A Separator Theorem for String Graphs and Its Applications, Convexity-increasing morphs of planar graphs, Optimality program in segment and string graphs, MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Strongly Sublinear Separators and Polynomial Expansion, Unnamed Item, 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, Covering Metric Spaces by Few Trees, Planar k-Path in Subexponential Time and Polynomial Space, Sublinear Separators in Intersection Graphs of Convex Shapes, Parameterized computation and complexity: a new approach dealing with NP-hardness, Short and Simple Cycle Separators in Planar Graphs, New lower bound techniques for VLSI, Parameterized graph separation problems, Graph separators: A parameterized view, The power of geometric duality, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Functional inversion and communication complexity, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, Better distance labeling for unweighted planar graphs, How to catch marathon cheaters: new approximation algorithms for tracking paths, Maximum matchings in planar graphs via Gaussian elimination, Hard constraint satisfaction problems have hard gaps at location 1, Polynomial-average-time satisfiability problems, Rectilinear short path queries among rectangular obstacles, Nonserial dynamic programming formulations of satisfiability, \(\ell ^2_2\) spreading metrics for vertex ordering problems, An efficient parallel algorithm for shortest paths in planar layered digraphs, Approximation algorithms for weighted matching, On the stabbing number of a random Delaunay triangulation, A quality and distance guided hybrid algorithm for the vertex separator problem, An application of the planar separator theorem to counting problems, Measuring the vulnerability for classes of intersection graphs, A parallel graph partitioning algorithm for a message-passing multiprocessor, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, Lower bounds for synchronous circuits and planar circuits, Treewidth for graphs with small chordality, Covering metric spaces by few trees, A fast algorithm for point-location in a finite element mesh, On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines, Some recent progress and applications in graph minor theory, General variable neighborhood search for computing graph separators, Fast balanced partitioning is hard even on grids and trees, On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability, Bisecting de Bruijn and Kautz graphs, Line-graph lattices: Euclidean and non-Euclidean flat bands, and implementations in circuit quantum electrodynamics, Sublinear separators, fragility and subexponential expansion, Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane, Balanced tree partition problems with virtual nodes, New constructions of SSPDs and their applications, Large induced acyclic and outerplanar subgraphs of 2-outerplanar graph, Linkless and flat embeddings in 3-space, Small grid embeddings of 3-polytopes, The size and depth of layered Boolean circuits, Approximation algorithms via contraction decomposition, Anomalous diffusion of random walk on random planar maps, Theory and application of width bounded geometric separators, Non deterministic polynomial optimization problems and their approximations, Satisfiability, branch-width and Tseitin tautologies, Size-treewidth tradeoffs for circuits computing the element distinctness function, Partitioning planar graphs: a fast combinatorial approach for max-cut, On fractional fragility rates of graph classes, Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators, Multilayer grid embeddings for VLSI, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, On cleaving a planar graph, A distributed shortest path algorithm for a planar network, A lower bound on the area of permutation layouts, Orthogonal drawings of graphs for the automation of VLSI circuit design, On the induced matching problem, Triangulating a simple polygon in linear time, Formula dissection: A parallel algorithm for constraint satisfaction, Nonlinear lower bounds on the number of processors of circuits with sublinear separators, On the parameterized complexity of computing balanced partitions in graphs, A nonlinear lower bound on the practical combinational complexity, Frameworks for designing in-place graph algorithms, Linearity of grid minors in treewidth with applications through bidimensionality, Nested annealing: A provable improvement to simulated annealing, The MIN-cut and vertex separator problem, On classes of graphs with strongly sublinear separators, An algorithm for min-cost edge-disjoint cycles and its applications, Not all planar digraphs have small cycle separators, Locating facilities which interact: Some solvable cases, Every minor-closed property of sparse graphs is testable, Fast minor testing in planar graphs, The slab dividing approach to solve the Euclidean \(P\)-center problem, Edge separators for graphs of bounded genus with applications, Approximability of clausal constraints, Minimum vertex cover in rectangle graphs, Approximating nearest neighbor among triangles in convex position, The complexity of the Hajós calculus for planar graphs, Planar minimally rigid graphs and pseudo-triangulations, Linear space data structures for two types of range search, On 3-pushdown graphs with large separators, Unimodular hyperbolic triangulations: circle packing and random walk, Triangulating a simple polygon, Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces, Approximating the partition function of planar two-state spin systems, An exact combinatorial algorithm for minimum graph bisection, A bounded-error quantum polynomial-time algorithm for two graph bisection problems, Planar acyclic computation, Solving and sampling with many solutions, Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy, ``Global graph problems tend to be intractable, Edge integrity of nearest neighbor graphs and separator theorems, Voronoi diagrams with barriers and on polyhedra for minimal path planning, Hyperbolic and parabolic unimodular random maps, On the complexity of planar Boolean circuits, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems., Balanced partitions of trees and applications, An efficient parallel algorithm for computing a large independent set in a planar graph, The maximum clique problem, Exact algorithms for intervalizing coloured graphs