Topologically trivial closed walks in directed surface graphs
From MaRDI portal
Publication:2223623
DOI10.1007/s00454-020-00255-3zbMath1466.05049arXiv1812.01564OpenAlexW3108789639MaRDI QIDQ2223623
Publication date: 29 January 2021
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1812.01564
Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Computational aspects of digital topology (68U03)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Small cancellation theory and automatic groups
- Groups, the theory of ends, and context-free languages
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Embeddings of graphs with no short noncontractible cycles
- Splitting (complicated) surfaces is hard
- Intersections of curves on surfaces
- Growth functions on Fuchsian groups and the Euler characteristic
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Spektren periodischer Graphen
- Transforming curves on surfaces
- Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
- Finding the closed partition of a planar graph
- The growth rate and balance of homogeneous tilings in the hyperbolic plane
- Optimally cutting a surface into a disk
- Combinatorial group theory.
- A data structure for dynamic trees
- On problems related to growth, entropy, and spectrum in group theory
- Curves von 2-manifolds and isotopies
- A note on curvature and fundamental group
- Multiple-Source Shortest Paths in Embedded Graphs
- Finding shortest contractible and shortest separating cycles in embedded graphs
- Shortest paths in directed planar graphs with negative lengths
- Finding one tight cycle
- Finding shortest non-trivial cycles in directed graphs on surfaces
- Finding Cycles with Topological Properties in Embedded Graphs
- A Semiring on Convex Polygons and Zero-Sum Cycle Problems
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- A new approach to the maximum-flow problem
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
- Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
- Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
- Formal-Language-Constrained Path Problems
- Computing the Geometric Intersection Number of Curves
- Homology Flows, Cohomology Cuts
- Holiest minimum-cost paths and flows in surface graphs
- Labeled shortest paths in digraphs with negative and positive edge weights
- Detecting Weakly Simple Polygons
- Minimum cuts and shortest homologous cycles
- Tightening Nonsimple Paths and Cycles on Surfaces
- Shortest non-trivial cycles in directed surface graphs
- Finding shortest non-trivial cycles in directed graphs on surfaces
- Path Detection in Multidimensional Iterative Arrays
- The Organization of Computations for Uniform Recurrence Equations
- On some techniques useful for solution of transportation network problems
- Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
- Transforming Curves on Surfaces Redux
- A characterization of shortest geodesics on surfaces
