Finding small simple cycle separators for 2-connected planar graphs

DOI10.1016/0022-0000(86)90030-9zbMath0607.05028OpenAlexW2049413646MaRDI QIDQ1085169

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90030-9

zbMATH Keywords

vertex separator planar triangulations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

The searching over separators strategy to solve some NP-hard problems in subexponential time, Surprising Applications of Treewidth Bounds for Planar Graphs, Better distance labeling for unweighted planar graphs, A note on maximum independent set and related problems on box graphs, A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, Proximity in triangulations and quadrangulations, Improved parallel depth-first search in undirected planar graphs, A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs, An efficient parallel algorithm for shortest paths in planar layered digraphs, An optimal parallel algorithm for planar cycle separators, Metric Embedding via Shortest Path Decompositions, A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs, A linear-processor algorithm for depth-first search in planar graphs, Embedding Outerplanar Graphs in Small Books, Applications of the crossing number, NC Algorithms for Weighted Planar Perfect Matching and Related Problems, Approximation algorithms for cutting a convex polyhedron out of a sphere, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, Modularity of minor‐free graphs, Bounds for the oriented diameter of planar triangulations, Counting cycles on planar graphs in subexponential time, Planarization of graphs embedded on surfaces, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Counting cycles on planar graphs in subexponential time, Treetopes and their graphs, Unnamed Item, A QPTAS for the base of the number of crossing-free structures on a planar point set, Approximating the k-Level in Three-Dimensional Plane Arrangements, Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators, Unnamed Item, Cycle bases in graphs characterization, algorithms, complexity, and applications, Representations of graphs and networks (coding, layouts and embeddings), Better distance labeling for unweighted planar graphs, How to find Steiner minimal trees in Euclidean \(d\)-space, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, I/O-efficient path traversal in succinct planar graphs, Not all planar digraphs have small cycle separators, Parallel search algorithms for graphs and trees, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Edge separators for graphs of bounded genus with applications, Dynamic programming and planarity: improved tree-decomposition based algorithms, Exact algorithms for the Hamiltonian cycle problem in planar graphs, Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles, Planar graphs, negative weight edges, shortest paths, and near linear time, Extending planar graph algorithms to \(K_{3,3}\)-free graphs, On the minimum consistent subset problem, An efficient oracle for counting shortest paths in planar graphs, On Geometric Set Cover for Orthants, Covering nearly surface-embedded graphs with a fixed number of balls, Balanced line separators of unit disk graphs, Accelerated Bend Minimization, BOUNDARY-OPTIMAL TRIANGULATION FLOODING, The ropelengths of knots are almost linear in terms of their crossing numbers, Many distances in planar graphs, An external-memory depth-first search algorithm for general grid graphs, Wiener Index and Remoteness in Triangulations and Quadrangulations, Counting triangulations and other crossing-free structures approximately, Unnamed Item, An efficient oracle for counting shortest paths in planar graphs, Short and Simple Cycle Separators in Planar Graphs, Flow in planar graphs with vertex capacities, Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs, Graph theoretical issues in computer networks

Cites Work