Instances with low geometric k-colored crossing number

We say that the i th of these line contains vertex i-1 . The next line contains a sequence of digits from 0 to K-1 which indicate the coloring of edges ij in order 01,02,03,...,0(N-1), 12,13,...,1(N-1),23,...,(N-2)N . The next N lines contain pairs of numbers i j indicating that in the initial point set, vertex i is matched to vertex j , that is, vertex i has matching edge ij .

Applying the doubling procedure described in the paper on a point set with a k-edge-coloring of the induced straight-line drawing yields an upper bound on the geometric k-colored crossing number. The claimed upper bounds can be checked using compute_asymptotics.py by providing filename of the point set as its first argument. This script requires the networkx -Python package.

Note that compute_asymptotics.py always searches for an optimum matching on its own and ignores the matching in the input file.