Characterization of Minimum Cycle Basis in Weighted Partial 2-trees

2013/02/24 by N. S. Narayanaswamy, G. Ramakrishna, Narayanaswamy, N. S. +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1302.5889

6 pages, 5 figures

arxiv created 2013/02/24 · openalex publication_date 2013/02/24 · arxiv updated 2013/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a weighted outerplanar graph, the set of lex short cycles is known to be a minimum cycle basis [Inf. Process. Lett. 110 (2010) 970-974 ]. In this work, we show that the set of lex short cycles is a minimum cycle basis in weighted partial 2-trees (graphs of treewidth two) which is a superclass of outerplanar graphs.

Related

• Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time
• Minimal Cycle Bases of Outerplanar Graphs
• Rooted Cycle Bases
• Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time
• Minimum Cycle Decomposition: A Constructive Characterization for Graphs of Treewidth Two with Node Degrees Two and Four