Perfect Matchings with Crossings.

For sets of points, even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least different plane perfect matchings, where is the /2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have crossings. We show the following results. (1) For every , any set with points, sufficiently large, admits a perfect matching with exactly crossings. (2) There exist sets of  points where every perfect matching has at most crossings. (3) The number of perfect matchings with at most crossings is superexponential in if is superlinear in . (4) Point sets in convex position minimize the number of perfect matchings with at most crossings for , and maximize the number of perfect matchings with crossings and with crossings.