Finding Shortest Non-Separating and Non-Contractible Cycles for Topologically Embedded Graphs

No abstract is available for this paper.

• Publication year

  2005

• Venue

  Embedded Systems and Applications

• Publication date

  2005-10-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/11561071_14
• 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 planar graphs

  2005cited by this paper
• Greedy optimal homotopy and homology generators

  2005cited by this paper
• Optimal pants decompositions and shortest homotopic cycles on an orientable surface

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

  2002influential reference
• Optimal System of Loops on an Orientable Surface

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

  2002influential reference
• An algorithm for embedding graphs in the torus ∗

  2001cited by this paper
• Exact and Approximate Distances in Graphs - A Survey

  2001cited by this paper
• Planar graphs, negative weight edges, shortest paths, and near linear time

  2001cited by this paper
• Computing a canonical polygonal schema of an orientable triangulated surface

  2001cited by this paper
• Graphs on Surfaces

  2001cited by this paper
• Transforming Curves on Surfaces

  1999cited by this paper
• On-Line Algorithms for Shortest Path Problems on Planar Digraphs

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

  1994cited by this paper
• A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection

  1994cited by this paper
• Paths in Graphs and Curves on Surfaces

  1994cited by this paper
• Disjoint circuits of prescribed homotopies in a graph on a compact surface

  1991cited by this paper
• Embeddings of graphs with no short noncontractible cycles

  1990cited by this paper
• Computational complexity of combinatorial surfaces

  1990cited by this paper
• On Short Noncontractible Cycles in Embedded Graphs

  1988cited by this paper
• Fibonacci heaps and their uses in improved network optimization algorithms

  1984cited by this paper
• On the independence ratio of a graph

  1978cited by this paper
• Algebraic Topology: An Introduction

  1977cited by this paper

• Excluding surfaces as minors in graphs

  2026cites this paper
• In the Search for Good Neck Cuts

  2026cites this paper
• Computing the second and third systoles of a combinatorial surface

  2024cites this paper
• Homomorphisms between graphs embedded in surfaces

  2024cites this paper
• Homomorphisms between graphs embedded on surfaces

  2023influential citation
• Algorithms for Length Spectra of Combinatorial Tori

  2023cites this paper
• A graph-based formalism for surface codes and twists

  2021cites this paper
• Minimum Cuts in Surface Graphs

  2019cites this paper
• Splitting ( Complicated ) Surfaces Is Hard 1 1

  2019influential citation
• Reachability in O(log n) Genus Graphs is in Unambiguous

  2018cites this paper
• C O ] 3 S ep 2 01 5 Three-coloring triangle-free graphs on surfaces VI . 3-colorability of quadrangulations ∗

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

  2018cites this paper
• Single-face non-crossing shortest paths in planar graphs

  2017cites this paper
• Computational topology of graphs on surfaces

  2017cites this paper
• Graphs on Surfaces: Topological Algorithms

  2016cites this paper
• Untangling two systems of noncrossing curves

  2016cites this paper
• Algorithms and combinatorics for geometric graphs

  2015cites this paper
• Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

  2015cites this paper
• Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations

  2015influential citation
• Algorithms for embedded graphs

  2014cites this paper
• Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

  2014cites this paper
• Untangling two systems of noncrossing curves

  2013cites this paper
• Counting and Sampling Minimum Cuts in Genus $$g$$g Graphs

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

  2013cites this paper
• List-coloring embedded graphs

  2012cites this paper
• Multiple-Source Shortest Paths in Embedded Graphs

  2012influential citation
• Global Minimum Cuts in Surface-Embedded Graphs

  2012cites this paper
• Classical simulation of measurement-based quantum computation on higher-genus surface-code states

  2012cites this paper
• Combinatorial optimization on embedded curves

  2012cites this paper
• ALGORITHMS FOR GRAPHS ON SURFACES Foreword and introduction Foreword and introduction Foreword

  2012cites this paper
• Algorithms for the edge-width of an embedded graph

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

  2011influential citation
• Shortest non-trivial cycles in directed surface graphs

  2011influential citation
• Shortest non-crossing walks in the plane

  2011influential citation
• Minimum cuts and shortest non-separating cycles via homology covers

  2011cites this paper
• Prize-collecting Steiner problems on planar graphs

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

  2011cites this paper
• Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs

  2011cites this paper
• Unambiguous logarithmic space bounded computations

  2011cites this paper
• A primal-dual clustering technique with applications in network design

  2011cites this paper
• Dynamic programming for graphs on surfaces

  2010cites this paper
• Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth

  2010cites this paper
• Finding shortest non-trivial cycles in directed graphs on surfaces

  2010cites this paper
• Output-sensitive algorithm for the edge-width of an embedded graph

  2010cites this paper
• Approximation Algorithms via Contraction DecompositionA preliminary version of this paper appears in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007

  2010cites this paper
• Space complexity of perfect matching in bounded genus bipartite graphs

  2010cites this paper
• Decomposition, approximation, and coloring of odd-minor-free graphs

  2010cites this paper
• Computing the Shortest Essential Cycle

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

  2010cites this paper
• Prize-collecting Network Design on Planar Graphs

  2010cites this paper
• Optimization in graphs under degree constraints. application to telecommunication networks

  2009cites this paper
• ALGORITHMS FOR GRAPHS ON SURFACES Foreword and introduction Foreword and introduction Foreword

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

  2009cites this paper
• Schnyder woods for higher genus triangulated surfaces, with applications to encoding

  2009cites this paper
• Programmation Dynamique pour les Graphes dans les Surfaces

  2009influential citation
• Curvature Aware Fundamental Cycles

  2009cites this paper
• Minimum cuts and shortest homologous cycles

  2009cites this paper
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

  2009cites this paper
• SCHNYDER WOODS FOR HIGHER GENUS TRIANGULATED SURFACES 3 Schaeffer

  2009cites this paper
• Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding

  2009cites this paper
• Distributed Coverage Verification in Sensor Networks Without Location Information

  2008cites this paper
• Graph and map isomorphism and all polyhedral embeddings in linear time

  2008cites this paper
• Schnyder woods for higher genus triangulated surfaces

  2008cites this paper
• Coloring triangle-free graphs on surfaces

  2008influential citation
• Finding one tight cycle

  2008cites this paper
• Distributed coverage verification in sensor networks without location information

  2008cites this paper
• Computing Interesting Topological Features

  2008cites this paper
• Testing contractibility in planar rips complexes

  2008cites this paper
• The crossing number of a projective graph is quadratic in the face-width

  2007influential citation
• Multiple source shortest paths in a genus g graph

  2007cites this paper
• Approximation algorithms via contraction decomposition

  2007influential citation
• Computing crossing number in linear time

  2007cites this paper
• Coloring triangle-free graphs on surfaces

  2007influential citation
• Approximating the Crossing Number of Toroidal Graphs

  2007cites this paper
• Splitting (complicated) surfaces is hard

  2006cites this paper
• Many Distances in Planar Graphs

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

  2006cites this paper
• Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time

  2005cites this paper
• Algorithmic graph minor theory: Decomposition, approximation, and coloring

  2005cites this paper
• Optimal pants decompositions and shortest homotopic cycles on an orientable surface

  2003cites this paper
• Shortest Noncontractible Cycles

  year unknowncites this paper