Tightening Nonsimple Paths and Cycles on Surfaces

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

zbMATH Keywords

homotopyembedded graphcomputational topologytopological graph theorycombinatorial surface

Mathematics Subject Classification ID

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