Shortest non-trivial cycles in directed surface graphs

No abstract is available for this paper.

• Publication year

  2011

• Venue

  International Symposium on Computational Geometry

• Publication date

  2011-06-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1998196.1998231
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Multiple-Source Shortest Paths in Embedded Graphs

  2012cited by this paper
• Minimum cuts and shortest non-separating cycles via homology covers

  2011cited by this paper
• Improved algorithms for min cut and max flow in undirected planar graphs

  2011cited by this paper
• Finding Cycles with Topological Properties in Embedded Graphs

  2011cited by this paper
• Minimum s-t cut in undirected planar graphs when the source and the sink are close

  2011cited by this paper
• Output-sensitive algorithm for the edge-width of an embedded graph

  2010cited by this paper
• Shortest Cut Graph of a Surface with Prescribed Vertex Set

  2010cited by this paper
• Maximum flows and parametric shortest paths in planar graphs

  2010cited by this paper
• Min st-Cut of a Planar Graph in O(n loglog n) Time

  2010cited by this paper
• Computing the Shortest Essential Cycle

  2010cited by this paper
• Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs

  2010cited by this paper
• Homology flows, cohomology cuts

  2009cited by this paper
• Randomly removing g handles at once

  2009cited by this paper
• Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

  2009cited by this paper
• Minimum cuts and shortest homologous cycles

  2009cited by this paper
• Finding shortest contractible and shortest separating cycles in embedded graphs

  2009cited by this paper
• Graph and map isomorphism and all polyhedral embeddings in linear time

  2008cited by this paper
• Finding one tight cycle

  2008cited by this paper
• Computing crossing number in linear time

  2007cited by this paper
• Approximation algorithms via contraction decomposition

  2007cited by this paper
• Probabilistic embeddings of bounded genus graphs into planar graphs

  2007cited by this paper
• Multiple source shortest paths in a genus g graph

  2007cited by this paper
• Splitting (complicated) surfaces is hard

  2006cited by this paper
• An O (n log n) algorithm for maximum st-flow in a directed planar graph

  2006cited by this paper
• Many Distances in Planar Graphs

  2006cited by this paper
• Tightening non-simple paths and cycles on surfaces

  2006cited by this paper
• Multiple-source shortest paths in planar graphs

  2005influential reference
• Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

  2005influential reference
• Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs

  2005influential reference
• Greedy optimal homotopy and homology generators

  2005cited by this paper
• Removing excess topology from isosurfaces

  2004cited by this paper
• Optimally Cutting a Surface into a Disk

  2002cited by this paper
• Dynamic generators of topologically embedded graphs

  2002cited by this paper
• Graphs on Surfaces

  2001influential reference
• Topological Noise Removal

  2001cited by this paper
• Faster shortest-path algorithms for planar graphs

  1994cited by this paper
• Maximum (s,t)-flows in planar networks in O(|V|log|V|) time

  1994cited by this paper
• Minimum cut in directed planar networks

  1992influential reference
• Embeddings of graphs with no short noncontractible cycles

  1990cited by this paper
• Topological Graph Theory

  1987cited by this paper
• Matching is as easy as matrix inversion

  1987cited by this paper
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

  1987cited by this paper
• Minimum s-t Cut of a Planar Undirected Network in O(n log2(n)) Time

  1983cited by this paper
• Classical topology and combinatorial group theory

  1980cited by this paper
• Maximum Flow in Planar Networks

  1979influential reference

• Computing shortest closed curves on non-orientable surfaces

  2024cites this paper
• Minimum Cuts in Surface Graphs

  2019cites this paper
• Holiest minimum-cost paths and flows in surface graphs

  2018influential citation
• Topologically Trivial Closed Walks in Directed Surface Graphs

  2018cites this paper
• Computational topology of graphs on surfaces

  2017influential citation
• Minimum cycle and homology bases of surface-embedded graphs

  2016cites this paper
• 32nd International Symposium on Computational Geometry, SoCG 2016, Boston, MA, USA, June 14-18, 2016

  2016cites this paper
• A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection

  2015cites this paper
• Minimum Cut of Directed Planar Graphs in O(n log log n) Time

  2015cites this paper
• Computing Surface Uniformization Using Discrete Beltrami Flow

  2015cites this paper
• All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

  2014cites this paper
• Fast algorithms for surface embedded graphs via homology

  2013cites this paper
• Global Minimum Cuts in Surface-Embedded Graphs

  2012influential citation
• Multiple-Source Shortest Paths in Embedded Graphs

  2012cites this paper
• Combinatorial optimization on embedded curves

  2012cites this paper
• Faster Shortest Non-contractible Cycles in Directed Surface Graphs

  2011influential citation
• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs

  2011influential citation
• Finding shortest non-trivial cycles in directed graphs on surfaces

  2010influential citation