On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs

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 log⁴ 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 log⁴ n) time; this application contributes to the study of the well-known Cycle Double Cover conjecture.