When do short cycles generate the cycle space? (Q757424)

Let \(G=(V,E)\) be a graph with arbitrary (perturbed) edge weights and let C(e) denote the shortest cycle containing the edge e. It is easy to show that the cycles in \(\{\) C(e)\(| e\in E\}\) are not only independent (over GF(2)) but are also contained in the cycle basis of minimum weight. We characterize, in several ways, those graphs for which \(\{\) C(e)\(| e\in E\}\) is a cycle basis (hence, the cycle basis of minimum weight) for every perturbed edge weighting. For example, these are the planar graphs such that no dual graph has two non-adjacent nodes connected by three internally node disjoint paths. Another characterization shows that these graphs can be obtained from cycles, bonds and \(K_ 4's\) by a special type of 2-sum operation; this leads to a linear time recognition algorithm for this class.