Complexity of Finding Perfect Bipartite Matchings Minimizing the Number of Intersecting Edges

Understand

Consider a problem where we are given a bipartite graph H with vertices arranged on two horizontal lines in the plane, such that the two sets of vertices placed on the two lines form a bipartition of H.

• We additionally require that H admits a perfect matching and assume that edges of H are embedded in the plane as segments.
• The goal is to compute the minimal number of intersecting edges in a perfect matching in H.
• The problem stems from so-called token swapping problems, introduced by Yamanaka et al.