๐Ÿ“–
Two-colour crossing minimization in complete geometric graphs is NP-hard
Zhe Zhang

Two-colour crossing minimization in complete geometric graphs is NP-hard

Author / Organization:
Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Two-colour crossing minimization in complete geometric graphs is NP-hard
Author / Organization Zhe Zhang
Subject & Discipline cs.CC
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-265086
Original Source Link Visit Source Page on arxiv.org »