Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time

2013/03/04 by Carola Doerr, G. Ramakrishna, Doerr, Carola +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems

paper · doi:10.48550/arxiv.1303.0728

openalex publication_date 2013/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two. The implicit representation can be made explicit in a running time that is proportional to the size of the MCB. Our algorithm improves the result of Borradaile, Sankowski, and Wulff-Nilsen [Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010]---which computes for all planar graphs an implicit O(n log n) space representation of an MCB in O(n log⁵ n) time---by a polylog factor for the special case of partial 2-trees. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970--974, 2010].

Related

• Characterization of Minimum Cycle Basis in Weighted Partial 2-trees
• Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time
• Rooted Cycle Bases
• Minimal Cycle Bases of Outerplanar Graphs
• Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time