Bounding the pseudolinear crossing number of Kn
via simulated annealing


Homepage

Here we store the experimental results described in

  • M. Balko and J. Kynčl. Bounding the pseudolinear crossing number of Kn via simulated annealing, Extended abstract in the (informal) Proceedings of the XVI Spanish Meeting on Computational Geometry, pages 37-40, 2015. [booklet of abstracts]
Abstract:

A drawing D of a graph is pseudolinear if the edges of D can be extended to doubly-infinite curves that form an arrangement of pseudolines. The pseudolinear crossing number of Kn, denoted by cr(Kn), is the minimum number of crossings in a pseudolinear drawing of Kn. Using simulated annealing, we obtain new pseudolinear drawings of Kn with few crossings for small values of n. We introduce a pseudolinear version of known constructions that blow up rectilinear drawings of Kn and we improve an upper bound for the leading constant in cr(Kn) to 0.380448, shrinking the current gap between the lower and upper bound by roughly five percent.

Further details can be found in the paper.

Results:

Every pseudolinear drawing of Kn can be decribed by specifying the orientation of each of its triangles. The n-signature of a drawing is the vector of these orientations. Every pseudolinear drawing of Kn is thus stored as a {+,-}-vector whose length is the number of triples of vertices of Kn. The coordinates of this vector are triples (a,b,c), 1 <= a < b < c <= n, in the lexicographic order where a triple is assigned + if the corresponding triangle in D is oriented counterclockwise and - otherwise. For n even, we also store a halving matching contained in the corresponding drawing of Kn. We recall that f : [n] → [n] is a halving matching in a pseudolinear drawing D of Kn if for every element i from [n] the pair {i, f(i)} is a halving pair in D and there are no distinct i, j in [n] with f(i) = j and f(j) = i. A halving matching f is represented with pairs i:f(i) for every i from [n].

Number of vertices Number of crossings Drawing Halving matching
42 40588 TXT TXT
43 44826 TXT
44 49366 TXT TXT
46 59459 TXT TXT
48 71007 TXT TXT
49 77424 TXT
50 84219 TXT TXT
52 99158 TXT TXT
54 115953 TXT TXT
56 134901 TXT TXT
57 145158 TXT
58 156040 TXT TXT
59 167490 TXT
60 179514 TXT TXT
61 192275 TXT
62 205638 TXT TXT
63 219637 TXT
64 234441 TXT TXT
65 249938 TXT
66 266142 TXT TXT
67 283230 TXT
68 301043 TXT TXT
69 319679 TXT
70 339241 TXT TXT
71 359635 TXT
72 380900 TXT TXT
73 403166 TXT
74 426391 TXT TXT
76 475758 TXT TXT
77 501997 TXT
78 529242 TXT TXT
79 557723 TXT
80 587251 TXT TXT
81 617908 TXT
82 649864 TXT TXT
83 682958 TXT
84 717222 TXT TXT
85 752963 TXT
86 789892 TXT TXT
87 828107 TXT
88 867862 TXT TXT
89 908914 TXT
90 951323 TXT TXT
91 995430 TXT
92 1040897 TXT TXT
93 1087843 TXT
94 1136565 TXT TXT
95 1187003 TXT
96 1238490 TXT TXT
97 1292586 TXT
98 1347824 TXT TXT
99 1404386 TXT
216 33260204 ZIP TXT

A compressed directory with all drawings: [ZIP, 121 kB]

Last update: 28.11.2016


Valid XHTML 1.0 Transitional