Finding small simple cycle separators for 2-connected planar graphs
From MaRDI portal
Recommendations
Cites work
- A Separator Theorem for Planar Graphs
- An O(logn) parallel connectivity algorithm
- An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph
- Efficient Planarity Testing
- Generalized Nested Dissection
- scientific article; zbMATH DE number 3815696 (Why is no real title available?)
- scientific article; zbMATH DE number 3688740 (Why is no real title available?)
- scientific article; zbMATH DE number 3752239 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3315017 (Why is no real title available?)
- On the Problem of Partitioning Planar Graphs
- Parallel Algorithms in Graph Theory: Planarity Testing
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Parallel Evaluation of General Arithmetic Expressions
- Universality considerations in VLSI circuits
Cited in
(87)- An external-memory depth-first search algorithm for general grid graphs
- A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
- A linear-processor algorithm for depth-first search in planar graphs
- Representations of graphs and networks (coding, layouts and embeddings)
- How to find Steiner minimal trees in Euclidean \(d\)-space
- Not all planar digraphs have small cycle separators
- Parallel search algorithms for graphs and trees
- Edge separators for graphs of bounded genus with applications
- 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
- Simple polytopes without small separators. II: Thurston's bound
- A QPTAS for the base of the number of crossing-free structures on a planar point set
- An efficient parallel algorithm for shortest paths in planar layered digraphs
- An optimal parallel algorithm for planar cycle separators
- Reduced constants for simple cycle graph separation
- Applications of the crossing number
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
- Treetopes and their graphs
- Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
- Counting triangulations and other crossing-free structures approximately
- The searching over separators strategy to solve some NP-hard problems in subexponential time
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- 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
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Finding short cycles in planar graphs using separators
- Embedding Outerplanar Graphs in Small Books
- Approximation algorithms for cutting a convex polyhedron out of a sphere
- Edge Separators of Planar and Outerplanar Graphs With Applications
- Planar Separators
- scientific article; zbMATH DE number 1979709 (Why is no real title available?)
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Approximating the k-Level in Three-Dimensional Plane Arrangements
- Wiener Index and Remoteness in Triangulations and Quadrangulations
- Improved bounds for shortest paths in dense distance graphs
- NC algorithms for weighted planar perfect matching and related problems
- Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
- Surprising Applications of Treewidth Bounds for Planar Graphs
- 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
- Metric Embedding via Shortest Path Decompositions
- On Geometric Set Cover for Orthants
- I/O-efficient path traversal in succinct planar graphs
- The ropelengths of knots are almost linear in terms of their crossing numbers
- Short and simple cycle separators in planar graphs
- Short and simple cycle separators in planar graphs
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Engineering planar separator algorithms
- BOUNDARY-OPTIMAL TRIANGULATION FLOODING
- Algorithms – ESA 2005
- Structured recursive separator decompositions for planar graphs in linear time
- Exact distance oracles for planar graphs
- Extending planar graph algorithms to \(K_{3,3}\)-free graphs
- Accelerated bend minimization
- On the minimum consistent subset problem
- An efficient oracle for counting shortest paths in planar graphs
- Balanced line separators of unit disk graphs
- Many distances in planar graphs
- An efficient oracle for counting shortest paths in planar graphs
- scientific article; zbMATH DE number 7754308 (Why is no real title available?)
- Modularity of minor‐free graphs
- Better distance labeling for unweighted planar graphs
- Bounds for the oriented diameter of planar triangulations
- Counting cycles on planar graphs in subexponential time
- Planarization of graphs embedded on surfaces
- Counting cycles on planar graphs in subexponential time
- \(N\)-separators in planar graphs
- On the oriented diameter of planar triangulations
- Space-efficient graph coarsening with applications to succinct planar encodings
- Drawn tree decomposition: new approach for graph drawing problems
- Clustering in polygonal domains
- TSP in a simple polygon
- A face cover perspective to _1 embeddings of planar graphs
- Almost optimal exact distance oracles for planar graphs
- Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
- Shortest path separators in unit disk graphs
- Faster construction of a planar distance oracle with \(\tilde{O}(1)\) query time
- Covering nearly surface-embedded graphs with a fixed number of balls
- Space efficient separator algorithms for planar graphs
- Better distance labeling for unweighted planar graphs
- A note on maximum independent set and related problems on box graphs
- Planar separators and parallel polygon triangulation.
- Dynamic programming and planarity: improved tree-decomposition based algorithms
This page was built for publication: Finding small simple cycle separators for 2-connected planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085169)
