Topologically trivial closed walks in directed surface graphs

DOI10.4230/LIPICS.SOCG.2019.34MaRDI QIDQ5088964FDOQ5088964

Authors: Jeff Erickson, Yipu Wang 

Publication date: 18 July 2022

Recommendations

• Topologically trivial closed walks in directed surface graphs
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Shortest non-trivial cycles in directed and undirected surface graphs
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Shortest non-trivial cycles in directed surface graphs

zbMATH Keywords

computational topologyhyperbolic geometryhomotopycontext-free grammarshomologystrong connectivitymedial axessurface-embedded graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Computational topology. An introduction
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on curvature and fundamental group
• Graphs on surfaces
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Graphs, surfaces and homology
• Embeddings of graphs with no short noncontractible cycles
• Finding shortest contractible and shortest separating cycles in embedded graphs
• Detecting weakly simple polygons
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Formal-Language-Constrained Path Problems
• Intersections of curves on surfaces
• On problems related to growth, entropy, and spectrum in group theory
• Small cancellation theory and automatic groups
• Growth functions on Fuchsian groups and the Euler characteristic
• Groups, the theory of ends, and context-free languages
• Optimally cutting a surface into a disk
• Curves von 2-manifolds and isotopies
• Finding one tight cycle
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Title not available (Why is that?)
• Minimum cuts and shortest homologous cycles
• Shortest non-trivial cycles in directed and undirected surface graphs
• Splitting (complicated) surfaces is hard
• Finding cycles with topological properties in embedded graphs
• Papers on group theory and topology. Translated and introduced by John Stillwell
• Finding shortest non-trivial cycles in directed graphs on surfaces
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• Transforming curves on surfaces
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components
• Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees
• Finding the closed partition of a planar graph
• Tightening nonsimple paths and cycles on surfaces
• Multiple-source shortest paths in embedded graphs
• Title not available (Why is that?)
• Holiest minimum-cost paths and flows in surface graphs
• A Semiring on Convex Polygons and Zero-Sum Cycle Problems
• Labeled shortest paths in digraphs with negative and positive edge weights
• Shortest non-trivial cycles in directed surface graphs
• Transforming curves on surfaces redux

Cited In (1)

• Topologically trivial closed walks in directed surface graphs

This page was built for publication: Topologically trivial closed walks in directed surface graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088964)