Computing the Girth of a Planar Graph in Linear Time

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

Hsien-Chih Chang, Hsueh-I Lu

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 graphs; data structures; graph algorithms; paths and cycles

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

68P05: Data structures