Bounding the pseudolinear crossing number of Kn
via simulated annealing
Here we store the experimental results described in
Abstract:
- 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]
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