Let G be a complete edge-weighted graph on n vertices. To each subset of vertices of G assign the cost of the minimum spanning tree of the subset as its weight. Suppose that n is a multiple of some fixed positive integer k . The k -matching problem is the problem of finding a partition of the vertices of G into k -sets (sets of k elements), that minimizes the sum of the weights of the k -sets. The case of k = 3 has been shown to be NP-hard [Johnsson et al., 1998]. In the Euclidean version, the vertices of G are points in the plane and the weight of an edge is the Euclidean distance between its endpoints. We call this problem the Euclidean k -matching problem. We show that, for every fixed k ≥ 3 , the Euclidean k -matching problem is NP-hard. This resolves an open problem in the literature and provides the first theoretical justification for the use of known heuristic methods in the case of k = 3 . We also show that the problem remains NP-hard if the trees are required to be paths.

A geometric graph is a graph whose vertex set is a set of points in general position in the plane, and its edges are straight line segments joining these points. We show that for every integer k ≥ 2 , there exists a constant c > 0 such that the following holds. The edges of every dense geometric graph, with sufficiently many vertices, can be colored with k colors, such that the number of pairs of edges of the same color that cross is at most ( 1 / k − c ) times the total number of pairs of edges that cross. The case when k = 2 and G is a complete geometric graph, was proved by Aichholzer et al. (2019) [2] .

Abstract For sets of n points, n 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 $$C_{n/2}$$ C n / 2 different plane perfect matchings, where $$C_{n/2}$$ C n / 2 is the n /2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every $$k\le \frac{1}{64}n^2-\frac{35}{32}n\sqrt{n}+\frac{1225}{64}n$$ k ≤ 1 64 n 2 - 35 32 n n + 1225 64 n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most $$\frac{5}{72}n^2-\frac{n}{4}$$ 5 72 n 2 - n 4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n . (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for $$k=0,1,2$$ k = 0 , 1 , 2 , and maximize the number of perfect matchings with $$\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) $$ n / 2 2 crossings and with $${\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) }\!-\!1$$ n / 2 2 - 1

In 2001, Karolyi, Pach and Toth introduced a family of point sets to solve an Erdos-Szekeres type problem; which have been used to solve several other Edos-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set X has the property that the interior of every triangle determined by three points in the same convex layer of X , contains exactly one point of X . In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of n points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of n points, with integer coordinates of absolute values at most O(n log 25). Finally, we use our characterization to obtain an O (n logn)-time algorithm to determine whether a set of points is a nested almost convex set.

Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of B ∪ W there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B : (i) 3 n / 2 white points are always sufficient to block a set of n black points, (ii) if B is in convex position, 5 n / 4 white points are always sufficient to block it, and (iii) at least n − 1 white points are always necessary to block a set of n black points.

Given a large weighted graph G = (V, E) and a subset U of V , we define several graphs with vertex set U in which two vertices are adjacent if they satisfy some prescribed proximity rule. These rules use the shortest path distance in G and generalize the proximity rules that generate some of the most common proximity graphs in Euclidean spaces. We prove basic properties of the defined graphs and provide algorithms for their computation.