Computing the Girth of a Planar Graph in Linear Time

DOI10.1137/110832033zbMath1272.05089arXiv1104.4892OpenAlexW2764219506MaRDI QIDQ5891165

Hsueh-I Lu, Hsien-Chih Chang

Publication date: 25 September 2013

Published in: SIAM Journal on Computing, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1104.4892

zbMATH Keywords

planar graphsdata structuresgraph algorithmspaths and cycles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (8)

Planar drawings with few slopes of Halin graphs and nested pseudotrees ⋮ On the negative cost girth problem in planar networks ⋮ Several extremal problems on graphs involving the circumference, girth, and hyperbolicity constant ⋮ A branch‐and‐cut algorithm for a bipartite graph construction problem in digital communication systems ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Computing the Girth of a Planar Graph in Linear Time