Tightening Nonsimple Paths and Cycles on Surfaces
From MaRDI portal
Publication:5390615
DOI10.1137/090761653zbMath1216.05156OpenAlexW2057266558MaRDI QIDQ5390615
Jeff Erickson, Éric Colin de Verdière
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/090761653
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Homotopy groups, general; sets of homotopy classes (55Q05) Relations of low-dimensional topology with graph theory (57M15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (14)
Minimum Cuts in Surface Graphs ⋮ Computing the Fréchet Distance Between Polygons with Holes ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ Shortest path embeddings of graphs on surfaces ⋮ Bijective enumeration of planar bipartite maps with three tight boundaries, or how to slice pairs of pants ⋮ Testing graph isotopy on surfaces ⋮ Topologically trivial closed walks in directed surface graphs ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face ⋮ Unnamed Item ⋮ Quantitative Restrictions on Crossing Patterns ⋮ A Census of Plane Graphs with Polyline Edges ⋮ Unnamed Item ⋮ Discrete systolic inequalities and decompositions of triangulated surfaces
This page was built for publication: Tightening Nonsimple Paths and Cycles on Surfaces
