We present an algorithm for finding a perfect matching in a 3-edge-connected cubic graph that intersects every 3-edge cut in exactly one edge. Specifically, we propose an algorithm with a time complexity of O (n ⁴ n), which significantly improves upon the previously known O (n³) -time algorithms for the same problem. The technique we use for the improvement is efficient use of cactus model of 3-edge cuts. As an application, we use our algorithm to compute embeddings of 3-edge-connected cubic graphs with limited number of singular edges (i. e. , edges that are twice in the boundary of one face) in O (n ⁴ n) time; this application contributes to the study of the well-known Cycle Double Cover conjecture.
Ghanbari et al. (Sat,) studied this question.