We extend the order type data base of all realizable order types in the plane to point sets of cardinality 11. More precisely, we provide a complete data base of all combinatorial different sets of up to 11 points in general position in the plane. In addition, we develop a novel and efficient method for a complete extension to order types of size 12 and more in an abstract sense, that is, without the need to store or realize the sets. The presented method is well suited for independent computations. Thus, time intensive investigations benefit from the possibility of distributed computing.Our approach has various applications to combinatorial problems which are based on sets of points in the plane. This includes classic problems like searching for (empty) convex k-gons ('happy end problem'), decomposing sets into convex regions, counting structures like triangulations or pseudo-triangulations, minimal crossing numbers, and more. We present some improved results to all these problems. As an outstanding result we have been able to determine the exact rectilinear crossing number of the complete graph Kn for up to n = 17, the largest previous range being n = 12, and slightly improved the asymptotic upper bound.

We prove that planar pseudotriangulations have realizations as polyhedral surfaces in three-space. Two main implications are presented. The spatial embedding leads to a novel flip operation that allows for a drastic reduction of flip distances, especially between (full) triangulations. Moreover, several key results for triangulations, like flipping to optimality, (constrained) Delaunayhood, and a convex polytope representation, are extended to pseudotriangulations in a natural way.

(MATH) Let $\overlinecr(G)$ denote the rectilinear crossing number of a graph $G. We determine $\overlinecr(K 11)=102 and $\overlinecr(K 12)=153. Despite the remarkable hunt for crossing numbers of the complete graph .K n -- initiated by R. Guy in the 1960s -- these quantities have been unknown for n>10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size 11.(MATH) Based on these findings, we establish new upper and lower bounds on $\overlinecr(K n), for general n. Specific values are given for n, ≤ 45. The new asymptotic lower bound is immediate from the result $\overlinecr(K 11)=102, whereas the upper bound stems from a novel construction of drawings with few crossings. The tantalizing question of determining $\overlinecr(K 13) is left open. The latest ra(n)ge is 221,223,225,227,229; our conjecture is $\overlinecr(K 13) = 229.

Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by an planar $n$-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size $n=10$ or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.