Not all planar digraphs have small cycle separators
From MaRDI portal
Publication:1201868
DOI10.1016/0020-0190(92)90189-3zbMath0759.05031OpenAlexW1991407326MaRDI QIDQ1201868
Publication date: 17 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90189-3
Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)
Cites Work
- Unnamed Item
- Finding small simple cycle separators for 2-connected planar graphs
- A random NC algorithm for depth first search
- A linear-processor algorithm for depth-first search in planar graphs
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- Fast and efficient solution of path algebra problems
- Parallel Depth-First Search in General Directed Graphs
- Space-Efficient Message Routing inc-Decomposable Networks
- Parallel Algorithms for Depth-First Searches I. Planar Graphs
- A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
- Parallel algorithms for planar graph isomorphism and related problems
- Efficient Message Routing in Planar Networks
- Generalized Nested Dissection
- Universality considerations in VLSI circuits
- Applications of a Planar Separator Theorem
