Computing the Girth of a Planar Graph in $O(n \logn)$ Time

DOI10.1137/090767868zbMath1213.05152OpenAlexW2039267480MaRDI QIDQ5392914

Raphael Yuster, Oren Weimann

Publication date: 15 April 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090767868

zbMATH Keywords

girthplanar graphshortest cyclegraphs of bounded genus

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

On the negative cost girth problem in planar networks ⋮ Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths