Instances with low geometric k-colored crossing number

This is a companion repository to a paper on the geometric k-colored crossing number.

There are 9 files named nS_C.coKm for numbers S, K and C which contain coordinates of point sets in general position of size S and a K-edge-coloring of the induced straight-line drawing of the complete graph on S vertices. The number of monochromatic crossings in that drawing is C which can be verified by running count_crossings.py with the filename of the point set as its first argument. 

• The first line of a file nS_C.coKm contains the number N indicating the number of vertices of the complete graph and the upper bound on the geometric K-colored crossing constant derived from that instance. The vertices are indexed from 0 to N-1.
• The next N lines contain 2-dimensional coordinates x y. We say that the ith 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.