Maximum Weighted Matching with Few Edge Crossings for 2-Layered Bipartite Graph

Kazuya Haraguchi, Kotaro Torii, Motomu Endo

Let c denote a non-negative constant. Suppose that we are given an edge-weighted bipartite graph G=(V,E) with its 2-layered drawing and a family X of intersecting edge pairs. We co…