arXiv:2610.31719 · v2
Two-colour crossing minimization in complete geometric graphs is NP-hard
摘要
Given a fixed straight-line drawing of a complete graph, we seek a two-colouring of its edges that minimizes monochromatic crossing pairs. We prove that the threshold decision problem is NP-complete, even for points in general position with integer coordinates. Thus exact minimization is NP-hard, resolving the complexity question posed at the Crossing Number Workshop in 2019. We reduce from MaxCut on permutation graphs by representing source vertices with classes of geometric edges, whose crossings encode source adjacencies. The complete target also contains every other edge between its points, and their freely chosen colours can affect the encoded cost. To control these interactions, we construct a large comparison grid with two stable colour phases and use program points to turn this reference into colour preferences on other edges. The optimum differs from a computable baseline plus the amplified minimum number of uncut source edges by an error small enough to distinguish consecutive source values. The reduction is deterministic, with polynomially many points and polynomial coordinate bit length.
作者备注：35 pages, 5 figures, 2 tables. Local clarifications to the cancellation calculation, stability proof and source representation. Proof source and verification: https://github.com/Myyura/two-colour-crossing-complete-geometric-graphs