# Packing plane perfect matchings into a point set.

1 IntroductionLet P be a set of n points in general position in the plane (no three points on a line). A geometric graph G = (P, E) is a graph whose vertex set is P and whose edge set E is a set of straight-line segments with endpoints in P. We say that two edges of G cross each other if they have a point in common that is interior to both edges. Two edges are disjoint if they have no point in common. A subgraph S of G is said to be plane (non-crossing or crossing-free) if its edges do not cross. A plane matching is a plane graph consisting of pairwise disjoint edges. Two subgraphs [S.sub.1] and [S.sub.2] are edge-disjoint if they do not share any edge. A complete geometric graph K(P) is a geometric graph on P which contains a straight-line edge between every pair of points in P.

We say that a set of subgraphs of K(P) is packed into K(P), if the subgraphs in the set are pairwise edge-disjoint. In a packing problem, we ask for the largest number of subgraphs of a given type that can be packed into K(P). Among all subgraphs of K(P), plane perfect matchings, plane spanning trees, and plane spanning paths are of interest [2, 3, 4, 5, 9, 12, 28, 34]. That is, one may look for the maximum number of plane spanning trees, plane Hamiltonian paths, or plane perfect matchings that can be packed into K(P). Since K(P) has n(n-1)/2 edges, at most n/2 spanning trees, at most n/2 spanning paths, and at most n - 1 perfect matchings can be packed into it. In this paper we consider perfect matchings. A perfect matching in K (P) is a set of edges that do not share any endpoint and cover all the points in P.

A long-standing open question is to determine if the edges of K(P) (where n is even) can be partitioned into n/2 plane spanning trees. In other words, is it possible to pack n/2 plane spanning trees into K(P)? If P is in convex position, the answer in the affirmative follows from the result of Bernhart and Kanien [11]. For P in general position, Aichholzer et al. [5] prove that [OMEGA]([square root of n]) plane spanning trees can be packed into K(P). They also show the existence of at least 2 edge-disjoint plane spanning paths.

In this paper we consider a closely related question: How many plane perfect matchings can be packed into K(P), where P is a set of n points in general position in the plane, with n even?

1.1 Previous Work

1.1.1 Existence of Plane Subgraphs

The existence of certain plane subgraphs in a geometric graph on a set P of n points is one of the classic problems in combinatorial and computational geometry.

One of the extremal problems in geometric graphs which was first studied by Avital and Hanani [10], Kuptiz [31], Erdos [19], and Perles (see reference [43]) is the following. What is the smallest number [e.sub.k](n) such that any geometric graph with n vertices and more than [e.sub.k](n) edges contains k + 1 pairwise disjoint edges, i.e., a plane matching of size at least k + 1. Note that k [less than or equal to] [n/2] - 1. By a result of Hopf and Pannwitz [27], Sutherland [41], and Erdos [19], [e.sub.1](n) = n, i.e., any geometric graph with n +1 edges

contains a pair of disjoint edges, and there are some geometric graphs with n edges which do not contain any pair of disjoint edges.

Alon and Erdos [8] proved that [e.sub.2](n) < 6n - 5, i.e., any geometric graph with n vertices and at least 6n - 5 edges contains a plane matching of size three. This bound was improved to [e.sub.2](n) [less than or equal to] 3n by Goddard et al. [22]. Recently Cerny [14] proved that [e.sub.2](n) [less than or equal to] [2.5n]; while the lower bound of [e.sub.2](n) [greater than or equal to] [2.5n] - 3 is due to Perles (see [14]). For [e.sub.3](n), Goddard et al. [22] showed that 3.5n - 6 [less than or equal to] [e.sub.3](n) [less than or equal to] 10n, which was improved by Toth and Valtr [43] to 4n - 9 [less than or equal to] [e.sub.3](n) [less than or equal to] 8.5n.

For general values of k, Akiyama and Alon [7] gave the upper bound of [e.sub.k](n) = O([n.sup.2-1/(k+1)]). Goddard et al. [22] improved the bound to [e.sub.k](n) = O(n[(log n).sup.k-3]). Pach and Torocsik [36] obtained the upper bound of [e.sub.k](n) [less than or equal to] [k.sup.4]n; which is the first upper bound that is linear in n. The upper bound was improved to [k.sup.3](n+1) by Toth and Valtr [43]; they also gave the lower bound of [e.sub.k](n) [greater than or equal to] [3/2](k - 1)n - 2[k.sup.2]. Toth [42] improved the upper bound to [e.sub.k](n) [less than or equal to] [2.sup.9][k.sup.2]n, where the constant has been improved to [2.sup.8] by Felsner [20]. It is conjectured that [e.sub.k](n) [less than or equal to] ckn for some constant c.

For the maximum value of k, i.e., k = [n/2] - 1, with n even, Aichholzer et al. [4] showed that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. That is, by removing [n/2] - 1 edges from any complete geometric graph, the resulting graph has k + 1 = [n/2] disjoint edges, i.e., a plane perfect matching. This bound is tight; there exist complete geometric graphs, such that by removing [n/2] edges, the resulting graph does not have any plane perfect matching. Similar bounds were obtained by Kupitz and Perles for complete convex graphs, i.e., complete graphs of point sets in convex position. Kupitz and Perles showed that any convex geometric graph with n vertices and more than kn edges contains k + 1 pairwise disjoint edges; see [22] (see also [7] and [8]). In particular, in the convex case, 2n + 1 edges guarantee a plane matching of size three. In addition, Keller and Perles [29] gave a characterization of all sets of [n/2] edges whose removal prevents the resulting graph from having a plane perfect matching.

Cerny et al. [15] considered the existence of Hamiltonian paths in geometric graphs. They showed that after removing at most [square root of n](2[square root of 2]) edges from any complete geometric graph of n vertices, the resulting graph still contains a plane Hamiltonian path. Aichholzer et al. [4] obtained tight bounds on the maximum number of edges that can be removed from a complete geometric graph, such that the resulting graph contains a certain plane subgraph; they considered plane perfect matchings, plane subtrees of a given size, and triangulations.

1.1.2 Counting Plane Graphs

The number of plane graphs of a given type in a set of n points is also of interest. In 1980, Newborn and Moser [35] asked for the maximal number of plane Hamiltonian cycles; they give an upper bound of 2 x [6.sup.n-2][n/2], but conjecture that it should be of the form [c.sup.n], for some constant c. In 1982, Ajtai et al. [6] proved that the number of plane graphs is at most [10.sup.13n]. Every plane graph is a subgraph of some triangulation (with at most 3n - 6 edges). Since a triangulation has at most [2.sup.3n-6] plane subgraphs, as noted in [21], any bound of [[alpha].sup.n] on the number of triangulations implies a bound of [2.sup.3n- 6][[alpha].sup.n] < [(8[alpha]).sup.n] on the number of plane graphs. The best known upper bound of [30.sup.n], for the number of triangulations is due to Sharir and Sheffer [37]. This implies the bound [240.sup.n] for plane graphs. As for plane perfect matchings, since a perfect matching has n/2 edges, Dumitrescu [18] obtained an upper bound of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [alpha] = 30. Sharir and Welzl [38] improved this bound to O([10.05.sup.n]). They also showed that the number of all (not necessarily perfect) plane matchings is at most O([10.43.sup.n]).

Garcia et al. [21] showed that the number of plane perfect matchings of a fixed size set of points in the plane is minimum when the points are in convex position. Motzkin [33] showed that points in convex position have [C.sub.n/2] many perfect matchings (classically referred to as non-crossing configurations of chords on a circle), where [C.sub.n/2] is the (n/2)th Catalan number; [C.sub.n/2] = [THETA]([n.sup.-3/2][2.sup.n]). Thus, the number of plane perfect matchings of n points in the plane is at least [C.sub.n/2]. Garcia et al. [21] presented a configuration of n points in the plane which has [OMEGA]([n.sup.-4][3.sup.n]) many plane perfect matchings. See Table 1.

1.1.3 Counting Edge-Disjoint Plane Graphs

The number of edge-disjoint plane graphs of a given type in a point set P of n points is also of interest. Nash-Williams [34] and Tutte [44] independently considered the number of (not necessarily plane) spanning trees. They obtained necessary and sufficient conditions for a graph to have k edge-disjoint spanning trees. Kundu [30] showed that any k-edge-connected graph contains at least [[k-1]/2] edge-disjoint spanning trees.

As for the plane spanning trees a long-standing open question is to determine if the edges of K(P) (where n is even) can be partitioned into n/2 plane spanning trees. In other words, is it possible to pack n/2 plane spanning trees into K(P)? If P is in convex position, the answer in the affirmative follows from the result of Bernhart and Kanien [11]. In [12], the authors characterize the partitions of the complete convex graph into plane spanning trees. They also describe a sufficient condition, which generalizes the convex case, for points in general position. Aichholzer et al. [5] showed that if the convex hull of P contains h vertices, then K(P) contains at least [h/2] edge-disjoint plane spanning trees, and if P is in a "regular wheel configuration", K(P) can be partitioned into n/2 spanning trees. For P in general position they showed that K(P) contains [OMEGA]([square root of n]) edge-disjoint plane spanning trees. They obtained the following trade-off between the number of edge-disjoint plane spanning trees and the maximum vertex degree in each tree: For any k [less than or equal to] [square root of n/12], K(P) has k edge-disjoint plane spanning trees with maximum vertex degree O([k.sup.2]) and diameter O(log(n/[k.sup.2])). They also showed the existence of at least 2 edge-disjoint plane Hamiltonian paths.

1.2 Our Results

Given a set P of n points in the plane, with n even, we consider the problem of packing plane perfect matchings into K(P). From now on, a matching will be a perfect matching.

In Section 3 we prove bounds on the number of plane matchings that can be packed into K(P). In Section 3.1 we show that if P is in convex position, then n/2 plane matchings can be packed into K(P); this bound is tight.

The points in wheel configurations are considered in Section 3.2. We show that if P is in regular wheel configuration, then [n/2] - 1 edge-disjoint plane matchings can be packed into K(P); this bound is tight as well. In addition, for a fixed size set of points, we give a wheel configuration of the points which contains at most [n/3] edge-disjoint plane matchings.

Point sets in general position are considered in Section 3.3. We show how to find three edge-disjoint plane matchings in any set of at least 8 points. If n is a power of two, we prove that K(P) contains at least [log.sub.2] n many edge-disjoint plane matchings. For the general case, where n is an even number, we prove that K(P) contains at least [[log.sub.2] n] - 2 edge-disjoint plane matchings.

In Section 3.4 we count the number of pairwise non-crossing plane matchings. Two plane matchings [M.sub.1] and [M.sub.2] are called non-crossing (or compatible) if the edges of [M.sub.1] and [M.sub.2] do not cross each other. We show that K(P) contains at least two and at most five non-crossing plane matchings; these bounds are tight. Table 1 summarizes the results.

In Section 4 we study the concept of matching persistency in a graph. A graph G is called matching-persistent, if by removing any perfect matching M from G, the resulting graph, G - M, still contains a perfect matching. We define the plane matching persistency of a point set P, denoted by pmp(P), to be the smallest number of edge-disjoint plane matchings such that, if we remove them from K(P) the resulting graph does not have any plane perfect matching. In other words, pmp(P) = [absolute value of M], where M is the smallest set of edge-disjoint plane matchings such that K(P) - [[union].sub.M[member of]M]M does not have any plane perfect matching. Here, the challenge is to find point sets with high plane matching persistency. We show that pmp(P) [greater than or equal to] 2 for all point sets P. We give a configuration of P with pmp(P) [greater than or equal to] 3. Concluding remarks and open problems are presented in Section 5.

2 Preliminaries

2.1 Graph-Theoretical Background

Consider a graph G = (V, E) with vertex set V and edge set E. If G is a complete graph on a vertex set V of size n, then G is denoted by [K.sub.n]. A k-factor is a regular graph of degree k. If G is the union of pairwise edge-disjoint k-factors, their union is called a k-factorization and G itself is k-factorable [24]. A matching in a graph G is a set of edges that do not share vertices. A perfect matching of G is a 1-factor of G. In this paper only perfect matchings are considered and they are simply called matchings. Since a perfect matching is a regular graph of degree one, it is a 1-factor. It is well-known that for n even, the complete graph [K.sub.n] is 1-factorable (See [24]). Note that [K.sub.n] has n(n-1)/2 edges and every 1-factor has n/2 edges. Thus, [K.sub.n] can be partitioned into at most n - 1 edge-disjoint perfect matchings.

On the other hand it is well-known that the edges of a complete graph [K.sub.n], where n is even, can be colored by n - 1 colors such that any two adjacent edges have a different color. Each color is assigned to n/2 edges, so that each color defines a 1-factor. The following geometric construction of a coloring, which uses a "regular wheel configuration", is provided in [40]. In a regular wheel configuration, n - 1 equally spaced points are placed on a circle and one point is placed at the center of the circle. For each color class, include an edge e from the center to one of the boundary vertices, and all of the edges perpendicular to the line through e, connecting pairs of boundary vertices.

The number of perfect matchings in a complete graph [K.sub.n] (with n even), denoted by M(n), is given by the double factorial; M(n) = (n - 1)!! [13], where (n - 1)!! = 1 x 3 x 5 *** (n - 3) x (n - 1).

2.2 Plane Matchings in Colored Point Sets

Let P be a set of n colored points in general position in the plane with n even. A colored matching of P, is a perfect matching such that every edge connects two points of distinct colors. A plane colored matching is a colored matching which is non-crossing. A special case of a plane colored matching, where P is partitioned into a set R of n/2 red points and a set B of n/2 blue points, is called plane bichromatic matching, also known as red-blue matching (RB-matching). In other words, an RB-matching of P is a non-crossing perfect matching such that every edge connects a red point to a blue point. It is well-known that if no three points of P are collinear, then P has an RB -matching [1]. As shown in Figure 1(a), some point sets have a unique RB-matching. Hershberger and Suri [26] construct an RB-matching in O(n log n) time, which is optimal.

We review some proofs for the existence of a plane perfect matching between R and B:

* Min(R, B): Consider a matching M between R and B which minimizes the total Euclidean length of the edges. The matching M is plane. To prove this, suppose that two line segments [r.sub.1][b.sub.1] and [r.sub.2][b.sub.2] in M intersect. By the triangle inequality, [absolute value of [r.sub.1][b.sub.2]] + [absolute value of [r.sub.2][b.sub.1]] < [absolute value of [r.sub.1][b.sub.1]] + [absolute value of [r.sub.2][b.sub.2]]. This implies that by replacing [r.sub.1][b.sub.1] and [r.sub.2][b.sub.2] in M by [r.sub.1][b.sub.2] and [r.sub.2][b.sub.1], the total length of the matching is decreased; which is a contradiction.

* Cut(R, B): The ham sandwich theorem implies that there is a line l, known as a ham sandwich cut, that splits both R and B exactly in half; if the size of R and B is odd, the line passes through one of each. Match the two points on f (if there are any) and recursively solve the problem on each side of f; the recursion stops when each subset has one red point and one blue point. By matching these two points in all subsets, a plane perfect matching for P is obtained. See Figure 1(b). A ham sandwich cut can be computed in O(n) time [32], and hence the running time can be expressed as the recurrence T(n) = O(n) + 2 x T([n/2]). Therefore, an RB-matching can be computed in O(n log n) time.

* Tangent(R, B): If R and B are separated by a line, we can compute an RB-matching in the following way. W.l.o.g. assume that R and B are separated by a vertical line l. Let CH(R) and CH(B) denote the convex hulls of R and B. Compute the upper tangent rb of CH(R) and CH(B) where r [member of] R and b [member of] B. Match r and b, and recursively solve the problem for R - {r} and B - {b}; the recursion stops when the two subsets are empty. In each iteration, all the remaining points are below the line passing through r and b, thus, the line segments representing a matched pair in the successor iterations do not cross rb. Therefore, the resulting matching is plane.

Consider a set P of n points where n is even, and a partition {[P.sub.1], ..., [P.sub.k]} of P into k color classes. Sufficient and necessary conditions for the existence of a colored matching in P follows from the following theorem by Sitton [39]:

Theorem 1 (Sitton [39]) Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a complete multipartite graph with n vertices, where [n.sub.1] [less than or equal to] *** [less than or equal to] [n.sub.k]. If [n.sub.k] [less than or equal to] [n.sub.1] + *** + [n.sub.k-1], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has a matching of size [n/2].

Aichholzer et al. [4] showed that if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a geometric graph corresponding to a colored point set P, then the minimum-weight colored matching of P is non-crossing. Specifically, they extend the proof of 2-colored point sets to multi-colored point sets:

Theorem 2 (Aichholzer et al. [4]) Let P be a set of colored points in general position in the plane with [absolute value of P] even. Then P admits a non-crossing perfect matching such that every edge connects two points of distinct colors if and only if at most half the points in P have the same color.

3 Packing Plane Matchings into Point Sets

Let P be a set of n points in the plane with n even. In this section we prove lower bounds on the number of plane matchings that can be packed into K(P). It is obvious that every point set has at least one plane matching, because a minimum weight perfect matching in K(P), denoted by Min(P), is plane. A trivial lower bound of 2 (for n [greater than or equal to] 4) is obtained from a minimum weight Hamiltonian cycle in K(P), because this cycle is plane and consists of two edge-disjoint matchings. We consider points in convex position (Section 3.1), wheel configuration (Section 3.2), and general position (Section 3.3).

3.1 Points in Convex Position

In this section we consider points in convex position. We show that if P is in convex position, n/2 plane matchings can be packed into K(P); this bound is tight.

Lemma 1 If P is in convex position, where [absolute value of P] is even and [absolute value of P] [greater than or equal to] 4, then every plane matching in P contains at least two edges of CH(P).

Proof: Let M be a plane matching in P. We prove this lemma by induction on the size of P. If [absolute value of P] = 4, then [absolute value of M] = 2. None of the diagonals of P can be in M, thus, the two edges in M belong to CH(P). If [absolute value of P] > 4 then [absolute value of M] [greater than or equal to] 3. If all edges of M are edges of CH(P), then the claim in the lemma holds. Assume that M contains a diagonal edge pq, where pq is not an edge of CH(P). Let [P.sub.1] and [P.sub.2] be the sets of points of P on each side of l(p, q) (both including p and q). Let [M.sub.1] and [M.sub.2] be the edges of M in [P.sub.1] and [P.sub.2], respectively. It is obvious that [P.sub.1] (resp. [P.sub.2]) is in convex position and [M.sub.1] (resp. [M.sub.2]) is a plane matching in [P.sub.1] (resp. [P.sub.2]). By the induction hypothesis [M.sub.1] (resp. [M.sub.2]) contains two edges of CH([P.sub.1]) (resp. CH([P.sub.2])). Since CH(P) = CH([P.sub.1]) [union] CH([P.sub.2]) and [absolute value of ([M.sub.1] [intersection] [M.sub.2])] = 1, M contains at least two edges of CH(P). []

Theorem 3 For any set P of n points in convex position in the plane, with n even, the maximum number of plane matchings that can be packed into K(P) is n/2.

Proof: By Lemma 1, every plane matching in P contains at least two edges of CH(P). On the other hand, CH(P) has n edges. Therefore, the number of plane matchings that can be packed into K(P) is at most n/2.

Now we show how to pack n/2 plane matchings into K(P). Let P = {[p.sub.0], ..., [p.sub.n-1]}, and w.l.o.g. assume that [p.sub.0], [p.sub.1], ..., [p.sub.n-1] is the radial ordering of the points in P with respect to a fixed point in the interior of CH(P). For each [p.sub.i] in the radial ordering, where 0 [less than or equal to] i < [n/2], let [M.sub.i] = {[p.sub.i+j-1][p.sub.n+i-j]: j = 1, ..., n/2} (all indices are modulo n). Informally speaking, [M.sub.i] is a plane perfect matching obtained from edge [p.sub.i][p.sub.i-1] and all edges parallel to [p.sub.i][p.sub.i-1]; see Figure 2. Let M = {[M.sub.i]: i = 0, ..., [n/2] - 1}. The matchings in M are plane and pairwise edge-disjoint. Thus, M is a set of n/2 plane matchings that can be packed into K(P). []

3.2 Points in Wheel Configurations

A point set P of n points is said to be in "regular wheel configuration" in the plane, if n - 1 points of P are equally spaced on a circle C and one point of P is at the center of C. We introduce a variation of the regular wheel configuration as follows. Let the point set P be partitioned into X and Y such that [absolute value of X] [greater than or equal to] 3 and [absolute value of X] is an odd number. The points in X are equally spaced on a circle C. For any two distinct points p, q [member of] X let l(p, q) be the line passing through p and q. Since X is equally spaced on C and [absolute value of X] is an odd number, l(p, q) does not contain the center of C. Let H(p, q) and H'(p, q) be the two half planes defined by l(p, q) such that H'(p, q) contains the center of C. Let C' = [[intersection].sub.p,q[member of]X]H'(p, q). The points in Y are in the interior of C'; see Figure 3(a). For any two points p, q [member of] X, the line segment pq does not intersect the interior of C'. The special case when [absolute value of Y] = 1 is the regular wheel configuration.

Lemma 2 Let P be a set of points in the plane where [absolute value of P] is an even number and [absolute value of P] [greater than or equal to] 6. Let {X, Y} be a partition of the points in P such that [absolute value of X] is an odd number and [absolute value of Y] [less than or equal to] 2[[absolute value of P]/6] - 1. If P is in the wheel configuration described above, then any plane matching in P contains at least two edges of CH(P).

Proof: Consider a plane matching M of P. It is obvious that CH(P) = CH(X); we show that M contains at least two edges of CH(X). Note that [absolute value of X] = [absolute value of P] - [absolute value of Y], and both [absolute value of X] and [absolute value of Y] are odd numbers. Observe that [absolute value of X] [greater than or equal to] 4[[absolute value of P]/6] + 1 = 2[absolute value of Y] + 3 [greater than or equal to] 5; which implies that [absolute value of Y] [less than or equal to] [[[absolute value of X] - 1]/2] - 1. Thus, [absolute value of X] > [absolute value of Y], and hence there is at least one edge in M with both endpoints in X. Let [p.sub.i][p.sub.j] be the longest such edge. Recall that C' [subset] H'([p.sub.i], [p.sub.j]). Let A be the set of points of P in H([p.sub.i], [p.sub.j]) (including [p.sub.i] and [p.sub.j]), and let A' be the set of points of P in H'([p.sub.i], [p.sub.j]) (excluding [p.sub.i] and [p.sub.j]). By definition, H([p.sub.i], [p.sub.j]) [union] l([p.sub.i], [p.sub.j]) does not contain any point of Y. Thus, A [subset] X and A is in convex position with [absolute value of A] [less than or equal to] [[[absolute value of X] - 1]/2] (note that [absolute value of X] is an odd number). Let M(A) and M(A') be the edges of M induced by the points in A and A', respectively. Clearly, {M(A), M(A')} is a partition of the edges of M, and hence M(A) (resp. M(A')) is a plane perfect matching for A (resp. A'). We show that each of M(A) and M(A') contains at least one edge of CH(X). First we consider M(A). If [absolute value of A] = 2, then [p.sub.i][p.sub.j] is the only edge in M(A) and it is an edge of CH(X). Assume that [absolute value of A] [greater than or equal to] 4. By Lemma 1, M(A) contains at least two edges of CH(A). On the other hand each edge of CH(A), except for [p.sub.i][p.sub.j], is also an edge of CH(X); see Figure 3(b). This implies that M(A) - {[p.sub.i][p.sub.j]} contains at least one edge of CH(X). Now we consider M(A'). Let X' = A' [intersection] X, that is, {A, X'} is a partition of the points in X. Since [absolute value of A] < [[[absolute value of X] - 1]/2], we have [absolute value of X'] [greater than or equal to] [[[absolute value of X] + 1]/2]. Recall that [absolute value of Y] [less than or equal to] [[[absolute value of X] - 1]/2] - 1. Thus, [absolute value of Y] < [absolute value of X'], and hence there is an edge [p.sub.k][p.sub.l] [member of] M(A') with both [p.sub.k] and [p.sub.l] in X'. Let B be the set of points of P in H([p.sub.k], [p.sub.l]) (including [p.sub.k] and [p.sub.l]). By definition, H([p.sub.k], [p.sub.l]) [union] l([p.sub.k], [p.sub.l]) does not contain any point of Y. Thus, B [susbet] X and B is in convex position. On the other hand, by the choice of [p.sub.i][p.sub.j] as the longest edge, A cannot be a subset of B and hence B [subset] X'. Let M(B) be the edges of M(A') induced by the points in B. We show that M(B) contains at least one edge of CH(X). If [absolute value of B] = 2, then [p.sub.k][p.sub.l] is the only edge in M(B) and it is an edge of CH(X). Assume that [absolute value of B] [greater than or equal to] 4. By Lemma 1, M (B) contains at least two edges of CH(B). On the other hand, each edge of CH(B), except for [p.sub.k][p.sub.l], is also an edge of CH(X); see Figure 3(b). This implies that M(B) - {[p.sub.k][p.sub.l]} contains at least one edge of CH(X). This completes the proof. []

Theorem 4 For a set P of n [greater than or equal to] 6 points in the regular wheel configuration in the plane with n even, the maximum number of plane matchings that can be packed into K(P) is [n/2] - 1.

Proof: In the regular wheel configuration, P is partitioned into a point set X of size n - 1 and a point set Y of size 1. The points of X are equally spaced on a circle C and the (only) point of Y is the center of C. By Lemma 2, every plane matching in P contains at least two edges of CH(P). On the other hand, CH(P) has n - 1 edges. Therefore, the number of plane matchings that can be packed into K(P) is at most [n-1]/2. Since n is an even number and the number of plane matchings is an integer, we can pack at most [n/2] - 1 plane matchings into K(P).

Now we show how to pack [n/2] - 1 plane matchings into K(P). Let P = {[p.sub.0], ..., [p.sub.n-1]}, and w.l.o.g. assume that [p.sub.n-1] is the center of C. Let P' = P - {[p.sub.n-1]}, and let [p.sub.0], [p.sub.1], ..., [p.sub.n-2] be the radial ordering of the points in P' with respect to [p.sub.n-1]. For each [p.sub.i] in the radial ordering, where 0 [less than or equal to] i [less than or equal to] [n/2] - 2, let

[R.sub.i] = {[p.sub.i+j][p.sub.i+2[(n-2)/4]-j+1]: j = 1, ..., [(n - 2)/4]},

and

[L.sub.i] = {[p.sub.i-j][p.sub.i-2[(n-2)/4]+j-1]: j = 1, ..., [(n - 2)/4]}

(all indices are modulo n - 1). Let [M.sub.i] = [R.sub.i] [union] [L.sub.i] [union] {[p.sub.i][p.sub.n-1]}; informally speaking, [M.sub.i] is a plane perfect matching obtained from edge [p.sub.i][p.sub.n-1] and edges parallel to [p.sub.i][p.sub.n-1]. See Figure 4(a) for the case where n = 4k and Figure 4(b) for the case where n = 4k + 2. Let M = {[M.sub.i]: i = 0, ..., [n/2] - 2}. The matchings in M are plane and pairwise edge-disjoint. Thus, M is a set of [n/2] - 1 plane matchings that can be packed into K(P). []

In the following theorem we use the wheel configuration to show that for any even integer n [greater than or equal to] 6, there exists a set P of n points in the plane, such that no more than [n/3] plane matchings can be packed into K(P).

Theorem 5 For any even number n [greater than or equal to] 6, there exists a set P of n points in the plane such that no more than [n/3] plane matchings can be packed into K(P).

Proof: The set P of n points is partitioned into X and Y, where [absolute value of Y] = 2[n/6] - 1 and [absolute value of X] = n - [absolute value of Y]. The points in X are equally spaced on a circle C and the points in Y are in the interior [[intersection].sub.p,q[member of]X]H'(p, q). By Lemma 2, any plane matching in P contains at least two edges of CH(P). Since CH(P) = CH(X), any plane matching of P contains at least two edges of CH(X). Thus, if M denotes any set of plane matchings which can be packed into K(P), we have (note that [absolute value of X] is odd)

[absolute value of M] [less than or equal to] [[[absolute value of X] - 1]/2] = [n - 2[n/6]]/2 = [n/2] - [n/6] [less than or equal to] ]n/2] - [[n - 5]/6] [less than or equal to] [n/3]. []

3.3 Points in General Position

In this section we consider the problem of packing plane matchings for point sets in general position (no three points on a line) in the plane. Let P be a set of n points in general position in the plane, with n even. Let M (P) denote the maximum number of plane matchings that can be packed into K(P). As mentioned earlier, a trivial lower bound of 2 (when n [greater than or equal to] 4) is obtained from a minimum weight Hamiltonian cycle, which is plane and consists of two edge-disjoint perfect matchings.

In this section we show that at least [[log.sub.2] n] - 1 plane matchings can be packed into K(P). As a warm-up, we first show that if n is a power of two, then [log.sub.2] n plane matchings can be packed into K(P). Then we extend this result to get a lower bound of [[log.sub.2] n] - 1 for every point set with an even number of points. We also show that if n [greater than or equal to] 8, then at least three plane matchings can be packed into K(P), which improves the result for n = 10, 12, and 14. Note that, as a result of Theorem 5, there exists a set of n = 6 points such that no more than [n/3] = 2 plane matchings can be packed into K(P). First consider the following observation.

Observation 1 Let P = {[P.sub.1], ..., [P.sub.k]} be a partition of the point set P, such that [absolute value of [P.sub.i]] is even and CH([P.sub.i]) [intersection] CH([P.sub.j]) = 0 for all 1 [less than or equal to] i, j [less than or equal to] k where i [not equal to] j. Let i be an index such that, M([P.sub.i]) = min{M([P.sub.j]): 1 [less than or equal to] j [less than or equal to] k}. Then, M(P) [greater than or equal to] M([P.sub.i]).

Lemma 3 For a set P of n points in general position in the plane, where n is a power of 2, at least [log.sub.2] n plane matchings can be packed into K(P).

Proof: We prove this lemma by induction. The statement of the lemma holds for the base case, where n = 2. Assume that n [greater than or equal to] 4. Recall that M(P) denotes the maximum number of plane matchings that can be packed into K(P). W.l.o.g. assume that a vertical line l partitions P into sets R and B, each of size n/2. By the induction hypothesis, M(R), M(B) [greater than or equal to] [log.sub.2](n/2). By Observation 1, M(P) [greater than or equal to] min{M(R), M(B)} [greater than or equal to] [log.sub.2](n/2). That is, by pairing a matching [M.sub.R] in R with a matching [M.sub.B] in B we get a plane matching [M.sub.P] in K(P), such that each edge in [M.sub.P] has both endpoints in R or in B. If we consider the points in R as red and the points in B as blue, Cut(R, B) (see Section 2.2) gives us a plane perfect matching [M'.sub.P] in K(P), such that each edge in [M'.sub.P] has one endpoint in R and one endpoint in B. That is [M'.sub.P] [intersection] [M.sub.P] = 0. Therefore, we obtain one more plane matching in K(P), which implies that M(P) [greater than or equal to] [log.sub.2](n/2) + 1 = [log.sub.2]n. []

Let R and B be two point sets which are separated by a line. A crossing tangent between R and B is a line l touching CH(R) and CH(B) such that R and B lie on different sides of l. Note that l contains a point r [member of] R, a point b [member of] B, and consequently the line segment rb; we say that l is subtended from rb. It is obvious that there are two (intersecting) crossing tangents between R and B; see Figure 5.

Lemma 4 For a set P of n [greater than or equal to] 8 points in general position in the plane with n even, at least three plane matchings can be packed into K(P).

Proof: We describe how to extract three edge-disjoint plane matchings, [M.sub.1], [M.sub.2], [M.sub.3], from K(P). Let l be a vertical line which splits P into sets R and B, each of size n/2. Consider the points in R as red and the points in B as blue. We differentiate between two cases: (a) n = 4k and (b) n = 4k + 2, for some integer k > 1.

In case (a), both R and B have an even number of points. Let [M.sub.1](R) and [M.sub.2](R) (resp. [M.sub.1](B) and [M.sub.2](B)) be two edge-disjoint plane matchings in R (resp. B) obtained by a minimum length Hamiltonian cycle in R (resp. B). Let [M.sub.1] = [M.sub.1](R) [union] [M.sub.1](B) and [M.sub.2] = [M.sub.2](R) [union] [M.sub.2](B). Clearly [M.sub.1] and [M.sub.2] are edge-disjoint plane matchings for P. Let [M.sub.3] = Cut(R, B). It is obvious that [M.sub.3] is edge-disjoint from [M.sub.1] and [M.sub.2], which completes the proof in the first case.

In case (b), both R and B have an odd number of points and we cannot get a perfect matching in each of them. Let l and l' be the two crossing tangents between R and B, subtended from rb and r'b', respectively. We differentiate between two cases: (i) l and l' intersect in the interior of rb and r'b', (ii) l and l' intersect at an endpoint of both rb and r'b'; see Figure 5.

* In case (i), let c be the intersection point; see Figure 5(a). Let [r.sub.1], [r.sub.2], ..., [r.sub.m] and [b.sub.1], [b.sub.2], ..., [b.sub.m] be the points of R and B, respectively, sorted clockwise around c, where m = n/2, [r.sub.1] = r, [r.sub.m] = r', [b.sub.1] = b, [b.sub.m] = b'. Consider the Hamiltonian cycle H = {[r.sub.i][r.sub.i+1]: 1 [less than or equal to] i < m} union] {[b.sub.i][b.sub.i+1]: 1 [less than or equal to] i < m} [union] {[r.sub.1][b.sub.1], [r.sub.m][b.sub.m]}. Let [M.sub.1] and [M.sub.2] be the two edge-disjoint matchings obtained from H. Note that [r.sub.1][b.sub.1] and [r.sub.m][b.sub.m] cannot be in the same matching, thus, [M.sub.1] and [M.sub.2] are plane. Let [M.sub.3] = Tangent(R, B). As described in Section 2.2, [M.sub.3] is a plane matching for P. In order to prove that [M.sub.3] [intersection] ([M.sub.1] [union] [M.sub.2]) = 0, we show that rb and r'b'--which are the only edges in [M.sub.1] [union] [M.sub.2] that connect a point in R to a point in B--do not belong to [M.sub.3]. Note that Tangent(R, B) iteratively selects an edge which has the same number of red and blue points below its supporting line, whereas the supporting lines of rb and r'b' have different numbers of red and blue points below them. Thus rb and r'b' are not considered by Tangent(R, B). Therefore [M.sub.3] is edge-disjoint from [M.sub.1] and [M.sub.2].

* In case (ii), w.l.o.g. assume that l and l' intersect at the red endpoint of rb and r'b', i.e., r = r'; See Figure 5(b). Let R' = R\{r} and B' = B [union] {r}. Note that both R' and B' have an even number of points and [absolute value of R'], [absolute value of B'] [greater than or equal to] 4. Let [M.sub.1](R') and [M.sub.2](R') be two edge-disjoint plane matchings in R' obtained by a minimum length Hamiltonian cycle in R'. Let [b.sub.1], [b.sub.2], ..., [b.sub.m] be the points of B sorted clockwise around r, where m = n/2, [b.sub.1] = b, [b.sub.m] = b'. Consider the Hamiltonian cycle H(R') = {[b.sub.i][b.sub.i+1]: 1 [less than or equal to] i < m} [union] {r[b.sub.1], r[b.sub.m]}. Let [M.sub.1](B') and [M.sub.2](B') be the two edge-disjoint plane matchings in B' obtained from H(B'). Let [M.sub.1] = [M.sub.1](R') [union] [M.sub.1](B') and [M.sub.2] = [M.sub.2](R') [union] [M.sub.2](B'). Clearly [M.sub.1] and [M.sub.2] are edge-disjoint plane matchings in P. Let [M.sub.3] = Tangent(R, B). As described in case (i), [M.sub.3] is a plane matching in P and [M.sub.3] [intersection] ([M.sub.1] [union] [M.sub.2]) = 0. Therefore, [M.sub.3] is edge-disjoint from [M.sub.1] and [M.sub.2]. []

As a direct consequence of Lemma 3 and Lemma 4 we have the following theorem.

Theorem 6 For a set P of n = [2.sup.i] x m points in general position in the plane with n even, m [greater than or equal to] 4, i [greater than or equal to] 0, at least i + 2 plane matchings can be packed into K(P).

Proof: If i = 0, then a minimum weight Hamiltonian cycle in K(P) consists of two plane matchings. Assume i [greater than or equal to] 1. Partition P by vertical lines, into [2.sup.i-1] point sets, each of size 2m. By Lemma 4, at least three plane matchings can be packed into each set. Considering these sets as the base cases in Lemma 3, we obtain i - 1 plane matchings between these sets. Thus, in total, i + 2 plane matchings can be packed into K(P). []

Theorem 7 For a set P of n points in general position in the plane, with n even, at least [[log.sub.2] n] - 1 plane matchings can be packed into K(P).

Proof: If n is a power of two, then by Lemma 3 at least [log.sub.2] n [greater than or equal to] [[log.sub.2] n] - 1 matchings can be packed into K(P). Assume n is not a power of two. We describe how to pack a set M of [[log.sub.2] n] - 1 plane perfect matchings into K(P). The construction consists of the following three main steps which we will describe in detail.

1. Building a binary tree T.

2. Assigning the points of P to the leaves of T.

3. Extracting M from P using internal nodes of T.

1. Building the tree T. In this step we build a binary tree T such that each node of T stores an even number, and each internal node of T has a left and a right child. For an internal node u, let left(u) and right(u) denote the left child and the right child of u, respectively. Given an even number n, we build T in the following way:

* The root of T stores n.

* If a node of T stores 2, then that node is a leaf.

* For a node u storing m, with m even and m [greater than or equal to] 4, we store the following even numbers into left(u) and right(u):

--If m is divisible by 4, we store m/2s in both left(u) and right(u); see Figure 6(a).

--If m is not divisible by 4 and u is the root or the left child of its parent then we store 2 [m/4] J in left(u) and m - 2[m/4] in right(u); see Figure 6(b).

--If m is not divisible by 4 and u is the right child of its parent then we store m - 2[m/4] in left(u) and 2[m/4] in right(u); see Figure 6(c).

Note that in the last two cases--where m is not divisible by four--the absolute difference between the values stored in left(u) and right(u) is exactly 2. See Figure 7.

2. Assigning the points to the leaves of the tree. In this step we describe how to assign the points of P, in pairs, to the leaves of T. We may assume without loss of generality that no two points of P have the same x-coordinate. Sort the points of P in a increasing order of their x-coordinate. Assign the first two points to the leftmost leaf, the next two points to the second leftmost leaf, and so on. Note that T has n/2 leaves, and hence all the points of P are assigned to the leaves of T. See Figure 7.

3. Extracting the matchings. Let L be the number of edges in a shortest path from the root to any leaf in T; in Figure 7, L = 3. For an internal node u [member of] T, let [T.sub.u] be the subtree rooted at u. Let [L.sub.u] and [R.sub.u] be the set of points assigned to the left and right subtrees of [T.sub.u], respectively, and let [P.sub.u] = [L.sub.u] [union] [R.sub.u]. Consider the points in [L.sub.u] as red and the points in [R.sub.u] as blue. Since the points in [L.sub.u] have smaller x- coordinates than the points in [R.sub.u], we say that [L.sub.u] and [R.sub.u] are separated by a vertical line t(u). For each internal node u where u is in level 0 [less than or equal to] i < L in T--assuming the root is in level 0--we construct a plane perfect matching [M.sub.u] in [P.sub.u] in the following way. Let m be the even number stored at u.

* If m is divisible by 4 (Figure 6(a)), then let [M.sub.u] = Min([L.sub.u], [R.sub.u]); see Section 2.2. Since [absolute value of [L.sub.u]] = [absolute value of [R.sub.u]], [M.sub.u] is a plane perfect matching for Pu. See vertices [u.sub.2], [u.sub.3] in Figure 7.

* If m is not divisible by 4 and u is the root or a left child (Figure 6(b)), then [absolute value of [R.sub.u]] - [absolute value of [L.sub.u]] = 2. Let a, b be the two points assigned to the rightmost leaf in [T.sub.u], and let [M.sub.u] = {ab} [union] Min([L.sub.u], [R.sub.u] - {a, b}). Since [absolute value of [L.sub.u]] = [absolute value of [R.sub.u]] - {a, b}], [M.sub.u] is a perfect matching in [P.sub.u]. In addition, a and b are the two rightmost points in [P.sub.u], thus, ab does not intersect any edge in Min([L.sub.u], [R.sub.u] - {a, b}), and hence [M.sub.u] is plane. See vertices [u.sub.0], [u.sub.1], [u.sub.5] in Figure 7.

* If m is not divisible by 4 and u is aright child (Figure 6(c)), then [absolute value of [L.sub.u]] - [absolute value of [R.sub.u]] = 2. Let a, b be the two points assigned to the leftmost leaf in [T.sub.u] and let [M.sub.u] = {ab} [union] Min([L.sub.u] - {a, b}, [R.sub.u]). Since [absolute value of [L.sub.u] - {a, b}] = [absolute value of [R.sub.u]], [M.sub.u] is a perfect matching in [P.sub.u]. In addition, a and b are the two leftmost points in [P.sub.u], thus, ab does not intersect any edge in Min([L.sub.u] - {a, b}, [R.sub.u]), and hence [M.sub.u] is plane. See vertices [u.sub.4], [u.sub.6] in Figure 7.

For each i, where 0 [less than or equal to] i < L, let S(i) be the set of vertices of T in level i; see Figure 7. For each level i let [M.sub.i] = [[union].sub.u[member of]S(i)] [M.sub.u]. Let M = {[M.sub.i] : 0 [less than or equal to] i < L}. In the rest of the proof, we show that M contains [[log.sub.2] n] - 1 edge-disjoint plane matchings in P.

Claim 1: For each i, where 0 [less than or equal to] i < L, Mj is a plane perfect matching in P. Note that if u is the root of the tree, then [P.sub.u] = P. In addition, for each internal node u (including the root), {[L.sub.u], [R.sub.u]} is a partition of the point set [P.sub.u]. This implies that in each level i of the tree, where 0 [less than or equal to] i < L, we have P = [[union].sub.u[member of]S(i)] [P.sub.u]. Moreover, the points in P are assigned to the leaves of T in non-decreasing order of their x-coordinate. Thus, [P.sub.i] = {[P.sub.u] : u [member of] S(i)} is a partition of the point set P; the sets [P.sub.u] with u [member of] S(i) are separated by vertical lines; see Figure 7. Therefore, [M.sub.i] is a perfect plane matching in P; which proves the claim.

Claim 2: For all [M.sub.i], [M.sub.j] [member of] M, where 0 [less than or equal to] i, j < L and i [not equal to] j, [M.sub.i] [intersection] [M.sub.j] = [empty set]. In order to prove that [M.sub.i] and [M.sub.j] are edge-disjoint, we show that for each pair of distinct internal nodes u and v, [M.sub.u] [intersection] [M.sub.v] = [empty set]. If u and v are in the same level, then [P.sub.u] and [P.sub.v] are separated by l(u), thus, [M.sub.u] and [M.sub.v] do not share any edge. Thus, assume that u [member of] S(i) and v [member of] S(j) such that 0 [less than or equal to] i, j < L, i [not equal to] j, and w.l.o.g. assume that i < j .If v [member of] [T.sub.u], then [P.sub.u] and [P.sub.v] are separated by line l(w), where w is the lowest common ancestor of u and v; this implies that [M.sub.u] and [M.sub.v] do not share any edge. Therefore, assume that v [member of] [T.sub.u], and w.l.o.g. assume that v is in the left subtree of [T.sub.u]. Thus, [P.sub.v]--and consequently [M.sub.v]--is to the left of l(u). The case where v is in the right subtree of [T.sub.u] is symmetric. Let m [greater than or equal to] 4 be the number stored at u. We differentiate between three cases:

* If m is divisible by 4, then all the edges in [M.sub.u] cross l(u), while the edges in [M.sub.v] are to the left of l(u). This implies that [M.sub.u] and [M.sub.v] are disjoint.

* If m is not divisible by 4 and u is the root or a left child, then all the edges of [M.sub.u] cross l(u), except the rightmost edge ab which is to the right of l(u). Since [M.sub.v] is to the left of l(u), it follows that Mu and [M.sub.v] are disjoint.

* If m is not divisible by 4 and u is a right child, then all the edges of [M.sub.u] cross l(u), except the leftmost edge ab. If a,b [not member of] [P.sub.v], then ab [not member of] [M.sub.v], and hence [M.sub.u] and [M.sub.v] are disjoint. If a,b [member of] [P.sub.v] then v is the left child of its parent and all the edges in [M.sub.v] cross l(v) (possibly except one edge which is to the right of l(v)), while ab is to the left of l(v). Therefore [M.sub.u] and [M.sub.v] do not share any edge. This completes the proof of the claim.

Claim 3: For every two nodes u and v in the same level of T which store m and m', respectively, [absolute value of m - m'] [less than or equal to] 2.

We prove the claim inductively for each level i of T. For the base case, where i = 1: (a) if n is divisible by four, then both u and v store f and the claim holds, (b) if n is not divisible by four then u stores 2 [ f J and v stores [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the claim holds for i = 1. Now we show that if the claim is true for the ith level of T, then the claim is true for the (i + 1)th level of T. Let u and v, storing m and m', respectively, be in the ith level of T. By the induction hypothesis, the claim holds for the ith level, i.e., [absolute value of m - m'] [less than or equal to] 2. We prove that the claim holds for the (i + 1)th level of T, i.e., for the children of u and v. Since m and m' are even numbers, [absolute value of m - m'] [member of] {0, 2}. If [absolute value of m - m'] = 0, then m = m', and by a similar argument as in the base case, the claim holds for the children of u and v. If [absolute value of m - m'] = 2, then w.l.o.g. assume that m' = m + 2. Let a be the smallest number and [beta] be the largest number stored at the children of u and v (which are at the (i + 1)th level). We show that [beta] - [alpha] [less than or equal to] 2. It is obvious that [alpha] = 2[m/4] and [beta] = m' - 2[m'/4]. Thus,

[beta] - [alpha] = m' - 2[m'/4] - 2[m/4] = m + 2 - 2[m + 2/4] - 2[m/4] (1)

Now, we differentiate between two cases, where m = 4k or m = 4k + 2. If m = 4k, then by Equation 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If m = 4k + 2, then by Equation 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which completes the proof of the claim.

Claim 4: L [greater than or equal to] [[log.sub.2] n] - 1.

It follows from Claim 3 that all the leaves of T are in the last two levels. Since T has n/2 leaves, T has n - 1 nodes. Recall that L is the number of edges in a shortest path from the root to any leaf in T. Thus, L [greater than or equal to] h - 1, where h is the height of T. To give a lower bound on h, one may assume that the last level of T is also full, thus,

n - 1 [less than or equal to] [2.sup.0] + [2.sup.1] + [2.sup.2] + *** + [2.sup.h] [less than or equal to] [2.sup.h+1] - 1

and hence, h [greater than or equal to] [log.sub.2] n - 1. Therefore, L [greater than or equal to] h - 1 [greater than or equal to] [log.sub.2] n - 2. Since L is an integer and n is not a power of two, L > [[log.sub.2] n] - 2 = [[log.sub.2] - 1; which proves the claim.

Claim 1 and Claim 2 imply that M contains L edge-disjoint plane perfect matchings. Claim 4 implies that L [greater than or equal to] [[log.sub.2] n] - 1, which proves the statement of the theorem.

3.4 Non-crossing Plane Matchings

In this section we consider the problem of packing plane matchings into K(P) such that any two different matchings in the packing are non-crossing. Two edge-disjoint plane matchings [M.sub.1] and [M.sub.2] are non-crossing (or compatible), if no edge in [M.sub.1] crosses any edge in [M.sub.2]. For a set P of n points in general position in the plane, with n even, we give tight lower and upper bounds on the number of pairwise non-crossing plane perfect matchings that can be packed into K(P).

Lemma 5 For a set P of n points in general position in the plane, with n even, at most five pairwise non-crossing plane matchings can be packed into K(P).

Proof: Let {[M.sub.1], [M.sub.2], ..., [M.sub.m]} be any maximal set of non-crossing edge-disjoint plane matchings in K(P). Let M = [M.sub.1] [union] [M.sub.2] *** [union] [M.sub.m], and let G be the induced subgraph of K(P) by M. It is obvious that G is an m-regular graph. Since [M.sub.1], ..., [M.sub.m] are plane and pairwise non-crossing, G is an m-regular plane graph. It is well known that every plane graph has a vertex of degree at most 5. Thus, G has a vertex of degree at most five and hence m [less than or equal to] 5; which implies at most five pairwise non-crossing plane matchings can be packed into K(P).

Figure 8 shows a 5-regular geometric graph on a set of 12 points in the plane which contains five noncrossing edge-disjoint plane matchings. In [25], the authors showed how to generate an infinite family of 5-regular planar graphs using the graph in Figure 8. By an extension of the five matchings shown in Figure 8, five non-crossing matchings for this family of graphs is obtained. Thus, the bound provided by Lemma 5 is tight.

It is obvious that if P contains at least four points, the minimum length Hamiltonian cycle in K(P) contains two non-crossing edge-disjoint plane matchings. In the following lemma we show that there exist point sets which contain at most two non-crossing edge-disjoint plane matchings.

Lemma 6 For a set P of n [greater than or equal to] 4 points in convex position in the plane, with n even, at most two pairwise non-crossing plane matchings can be packed into K(P).

Proof: The proof is by contradiction. Consider three pairwise non-crossing plane matchings [M.sub.1], [M.sub.2], [M.sub.3] in K(P). Let G be the induced subgraph of K(P) by [M.sub.1] [union] [M.sub.2] U [M.sub.3]. Note that G is a 3-regular plane graph. Moreover, G is an outerplanar graph. It is well known that every outerplanar graph has a vertex of degree at most 2. This contradicts that every vertex in G has degree 3.

We conclude this section with the following theorem.

Theorem 8 For a set P of n [greater than or equal to] 4 points in general position in the plane, with n even, at least two and at most five pairwise non-crossing plane matchings can be packed into K (P). These bounds are tight.

4 Matching Removal Persistency

In this section we define the matching persistency of a graph. A graph G is matching persistent if by removing any perfect matching M from G, the resulting graph, G - M, has a perfect matching. We define the matching persistency of G, denoted by mp(G), as the size of the smallest set M of edgedisjoint perfect matchings that can be removed from G such that G - M does not have any perfect matching. In other words, if mp(G) = k, then

1. by removing an arbitrary set of k--1 edge-disjoint perfect matchings from G, the resulting graph still contains a perfect matching, and

2. there exists a set of k edge-disjoint perfect matchings such that by removing these matchings from G, the resulting graph does not have any perfect matching.

In particular, G is matching persistent iff mp(G) [greater than or equal to] 2.

Lemma 7 Let [K.sub.n] be a complete graph with n vertices, where n is even, and let M be a set of k edge-disjoint perfect matchings in [K.sub.n]. Then, [K.sub.n] - M is an (n - 1 - k)-regular graph which is (n - 1 - 2k)-connected.

Proof: The regularity is trivial, because [K.sub.n] is (n - 1)-regular and every vertex has degree k in M, thus, [K.sub.n] - M is an (n - 1 - k)-regular graph. Now we prove the connectivity. Consider two vertices u and v in V([K.sub.n]). There are n - 1 many edge-disjoint paths between u and v in [K.sub.n]: n - 2 many paths of length two of the form (u, x, v), where x [member of] V([K.sub.n]) - {u, v} and a path (u, v) of length one; see Figure 9(a). By removing any matching in M from [K.sub.n], at most two paths disappear, because u and v have degree one in each matching. Thus in G - M, there are (n - 1 - 2k) many edge-disjoint paths between u and v, which implies that [K.sub.n] - M is (n - 1 - 2k)-connected.

Lemma 8 Let n to be an even number. Then, mp([K.sub.n]) [greater than or equal to] n/2.

Proof: We show that by removing any set M of k edge-disjoint perfect matchings from [K.sub.n], where 0 [less than or equal to] k < n/2, the resulting graph still has a perfect matching. By Lemma 7, the graph [K.sub.n] - M is an (n - 1 - k)-regular graph which is (n - 1 - 2k)-connected. Since k < n, [K.sub.n] - M is a connected graph and the degree of each vertex is at least f. Thus, by a result of Dirac [17], [K.sub.n] - M has a Hamiltonian cycle and consequently a perfect matching. Therefore, by removing k arbitrary perfect matchings from [K.sub.n], where k < n/2, the resulting graph still has a perfect matching, which proves the claim.

Lemma 9 If n [equivalent to] 0 mod 4, then mp([K.sub.n]) [greater than or equal to] n/2 + 1.

Proof: By Lemma 8, mp([K.sub.n]) [greater than or equal to] n/2. Let M be any set of n edge-disjoint perfect matchings in [K.sub.n]. We will show that [K.sub.n] - M contains a perfect matching. If [K.sub.n] - M contains a Hamiltonian cycle then it has a perfect matching and we are done. Assume [K.sub.n] - M does not contain any Hamiltonian cycle, while it is a (n - 1)-regular graph. A result of Cranston and O [16] implies that [K.sub.n] - M is disconnected. In order for [K.sub.n] - M to be (n - 1)-regular each component has to have at least n vertices. Thus, [K.sub.n] - M consists of two disjoint copies of [K.sub.n]. Each of these components has a Hamiltonian cycle, and hence a perfect matching. Therefore, the union of these two components has a perfect matching.

Theorem 9 If n [equivalent to] 2 mod 4, then mp([K.sub.n]) = n/2.

Proof: By Lemma 8, mp([K.sub.n]) [greater than or equal to] n/2. In order to complete the proof, we show that mp([K.sub.n]) [less than or equal to] n/2. Let H = [K.sub.n/2,n/2] n be a complete bipartite subgraph of [K.sub.n]. Note that n is an odd number and H is an n/2- regular graph. According to Hall's marriage theorem [23], for k [greater than or equal to] 1, every k-regular bipartite graph contains a perfect matching [24]. Since by the iterative removal of perfect matchings from H the resulting graph is still regular, the edges of H can be partitioned into n perfect matchings; see Figure 9(a). It is obvious that [K.sub.n] - H consists of two connected components of odd size. Thus, by removing the n matchings in H, the resulting graph, [K.sub.n] - H, does not have any perfect matching. This proves the claim.

Theorem 10 If n [equivalent to] 0 mod 4, then mp([K.sub.n]) = n/2 + 1.

Proof: By Lemma 9, mp([K.sub.n]) [greater than or equal to] n/2 + 1. In order to complete the proof, we show that mp([K.sub.n]) [less than or equal to] n/2 + 1. Assume n = 4k. Let A = {[a.sub.1], [a.sub.2k-1]} and B = {[b.sub.1], ..., [b.sub.2k+1]} be a partition of vertices of [K.sub.n]. Let [M.sub.i] be a matching consisting of the edges [b.sub.i][b.sub.i+1] and [a.sub.j][b.sub.j+i+1], where + is modulo 2k + 1 and j runs from 1 to 2k - 1. It is easy to see that [M.sub.1], ..., [M.sub.2k+1] are disjoint perfect matchings, and after removing them we have a complete graph on A and a graph on B, which are disjoint. Since each of A and B has an odd number of points, there is no more perfect matching. This proves the claim.

In the rest of this section we consider plane matching removal from geometric graphs.

Let P be a set of n points in general position in the plane, with n even. Given a geometric graph G on P, we say that G is plane matching persistent if by removing any plane perfect matching M from G, the resulting graph, G - M, has a plane perfect matching. We define the plane matching persistency of G, denoted by pmp(G) as the size of the smallest set M of edge-disjoint plane perfect matchings that can be removed from G such that G - M does not have any plane perfect matching. In particular, G is plane matching persistent iff pmp(G) [greater than or equal to] 2.

Aichholzer et al. [4] and Perles (see [29]) showed that by removing any set of at most n/2 - 1 edges from K(P), the resulting graph has a plane perfect matching. This bound is tight [4]; that is, there exists a point set P such that by removing a set H of n/2 edges from K(P) the resulting graph does not have any plane perfect matching. In the examples provided by [4], the n/2 edges in H form a connected component which has n/2 + 1 vertices.

Thus, one may think if the removed edges are disjoint, it may be possible to remove more than n/2 - 1 edges while the resulting graph has a plane perfect matching. In the following lemma we show that by removing any plane perfect matching, i.e., a set of n/2 disjoint edges, from K(P), the resulting graph still has a perfect matching.

Lemma 10 Let P be a set of n points in general position in the plane with n even, then pmp(K (P)) [greater than or equal to] 2.

Proof: Let M be any plane perfect matching in K(P). Assign n/2 distinct colors to the points in P such that both endpoints of every edge in M have the same color. By Theorem 2, P has a plane colored matching, say M'. Since both endpoints of every edge in M have the same color while the endpoints of every edge in M' have distinct colors, M and M' are edge-disjoint. Therefore, by removing any plane perfect matching from K(P), the resulting graph still has a plane perfect matching, which implies that pmp(K(P)) [greater than or equal to] 2.

Theorem 11 For a set P of n [greater than or equal to] 4 points in convex position in the plane with n even, pmp(K (P)) = 2.

Proof: By Lemma 10, pmp(K(P)) [greater than or equal to] 2. In order to prove the theorem, we need to show that pmp(K(P)) [less than or equal to] 2. Let [M.sub.1] and [M.sub.2] be two edge-disjoint plane matchings obtained from CH(P). By Lemma 1, any plane perfect matching in K (P) contains at least two edges of CH (P), while K (P )-{[M.sub.1] [union] [M.sub.2]} does not have convex hull edges, and hence does not have any plane perfect matching. Therefore, pmp(K(P)) [less than or equal to] 2.

Observation 2 The union of two edge-disjoint perfect matchings in any graph is a set of even cycles.

Lemma 11 There exists a point set P in general position such that pmp(K (P)) [greater than or equal to] 3.

Proof: We prove this lemma by providing an example. Figure 10(a) shows a set P = {[a.sub.1], ..., [a.sub.n], [b.sub.1], ..., [b.sub.n], [c.sub.1], ..., [c.sub.n]} of 3n points in general position, where n is an even number. In order to prove that pmp(K(P)) [greater than or equal to] 3, we show that by removing any two edge-disjoint plane matchings from K(P), the resulting graph still has a plane perfect matching. Let [M.sub.1] and [M.sub.2] be any two plane perfect matchings in K(P). Let G be the subgraph of K (P) induced by the edges in [M.sub.1] [union] [M.sub.2]. Note that G is a 2-regular graph and by Observation 2 does not contain any odd cycle. For each 1 [less than or equal to] i [less than or equal to] n, let [t.sub.i] be the triangle which is defined by the three points [a.sub.i], [b.sub.i], and [c.sub.i]. Let T be the set of these n (nested) triangles. Since G does not have any odd cycle, for each [t.sub.i] [member of] T, at least one edge of [t.sub.i] is not in G. Let [M.sub.3] be the matching containing an edge [e.sub.i] from each [t.sub.i] [member of] T such that [e.sub.i] [not member of] G. See Figure 10(b). Now we describe how to complete [M.sub.3], i.e., complete it to a perfect matching. Partition the triangles in T into f pairs of consecutive triangles. For each pair ([t.sub.i]; [t.sub.i+1]) of consecutive triangles we complete [M.sub.3] locally--on [a.sub.i], [b.sub.i], [c.sub.i], [a.sub.i+1], [b.sub.i+1], [c.sub.i+1]--in the following way. Let [t.sub.i] = ([a.sub.i]; [b.sub.i]; [c.sub.i]) and [t.sub.i+1] = ([a.sub.i+1], [b.sub.i+1], [c.sub.i+1]). See Figure 10(c). W.l.o.g. assume that [M.sub.3] contains [a.sub.i][b.sub.i] and [a.sub.i+1][c.sub.i+1], that is [a.sub.i][b.sub.i] [not member of] G and [a.sub.i+1][c.sub.i+1] [not member of] G. If [c.sub.i][b.sub.i+1] [not member of] G, then we complete [M.sub.3] by adding [c.sub.i][b.sub.i+1]. If [c.sub.i][b.sub.i+1] [not member of] G, then [a.sub.i+1][b.sub.i+1] [not member of] G or [c.sub.i+1][b.sub.i+1] [not member of] G because bi+1 has degree two in G. W.l.o.g. assume that [a.sub.i+1][b.sub.i+1] [not member of] G. Then we modify [M.sub.3] by removing [a.sub.i+1][c.sub.i+1] and adding [a.sub.i+1][b.sub.i+1]. Now, if [c.sub.i][c.sub.i+1] [not member of] G, then we complete [M.sub.3] by adding [c.sub.i][c.sub.i+1]. If [c.sub.i][c.sub.i+1] [not member of] G, then by Observation 2, [b.sub.i+1][c.sub.i+1] [not member of] G. We modify [M.sub.3] by removing [a.sub.i+1][b.sub.i+1] and adding [b.sub.i+1][c.sub.i+1]. At this point, since [c.sub.i][b.sub.i+1] and [c.sub.i][c.sub.i+1] are in G, [c.sub.i][a.sub.i+1] [not member of] G and we complete [M.sub.3] by adding [c.sub.i][a.sub.i+1].

5 Conclusion

We considered the problem of packing edge-disjoint plane perfect matchings into a set P of n points in the plane. If P is in general position, we showed how to pack [[log.sub.2] n] - 1 matchings. We also looked at some special cases and variants of this problem. We believe that the number of such matchings is linear. A natural open problem is to improve either the provided lower bound or the trivial upper bound of n - 1, where n > 6. Another problem is to provide point sets with large plane matching persistency.

Ahmad Biniaz

Prosenjit Bose

Anil Maheshwari

Michiel Smid

School of Computer Science, Carleton University, Ottawa, Canada

received 15th Jan. 2015, revised 22ndMay 2015, accepted 28th Aug. 2015.

Acknowledgements

We would like to thank the anonymous reviewers for their valuable comments and suggestions improving the quality of the paper. We are grateful to Thomas Hackl for his valuable comments; specifically for pointing out the outerplanariy of the graph in the proof of Lemma 6, which simplified the proof. We also thank Vida Dujmovic for valuable discussions.

References

[1] The 1979 Putnam exam. In G. L. Alexanderson, L. F. Klosinski, and L. C. Larson, editors, The William Lowell Putnam Mathematical Competition Problems and Solutions: 1965-1984. Mathematical Association of America, USA, 1985.

[2] O. Aichholzer, A. Asinowski, and T. Miltzow. Disjoint compatibility graph of non-crossing matchings of points in convex position. Electr. J. Comb., 22(1):P1.65, 2015.

[3] O. Aichholzer, S. Bereg, A. Dumitrescu, A. G. Olaverri, C. Huemer, F. Hurtado, M. Kano, A. Marquez, D. Rappaport, S. Smorodinsky, D. L. Souvaine, J. Urrutia, and D. R. Wood. Compatible geometric matchings. Comput. Geom., 42(6-7):617-626, 2009.

[4] O. Aichholzer, S. Cabello, R. F. Monroy, D. Flores-Penaloza, T. Hackl, C. Huemer, F. Hurtado, and D. R. Wood. Edge-removal and non-crossing configurations in geometric graphs. Discrete Mathematics & Theoretical Computer Science, 12(1):75-86, 2010.

[5] O. Aichholzer, T. Hackl, M. Korman, M. J. van Kreveld, M. Loffler, A. Pilz, B. Speckmann, and E. Welzl. Packing plane spanning trees and paths in complete geometric graphs. In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG, 2014.

[6] M. Ajtai, V. Chvatal, M. M. Newborn, and E. Szemeredi. Crossing-free subgraphs. Ann. Discrete Math., 12:9-12, 1982.

[7] J. Akiyama and N. Alon. Disjoint simplices and geometric hypergraphs. Annals of the New York Academy of Sciences, 555(1):1-3, 1989.

[8] N. Alon and P. Erdos. Disjoint edges in geometric graphs. Discrete & Computational Geometry, 4:287-290, 1989.

[9] G. Aloupis, L. Barba, S. Langerman, and D. L. Souvaine. Bichromatic compatible matchings. In Symposium on Computational Geometry, pages 267-276, 2013.

[10] S. Avital and H. Hanani. Graphs (in Hebrew). Gilyonot Lematematika, 3:2-8, 1966.

[11] F. Bernhart and P. C. Kainen. The book thickness of a graph. J. Comb. Theory, Ser. B, 27(3):320-331, 1979.

[12] P. Bose, F. Hurtado, E. Rivera-Campo, and D. R. Wood. Partitions of complete geometric graphs into plane trees. Comput. Geom., 34(2):116-125, 2006.

[13] D. Callan. A combinatorial survey of identities for the double factorial. arXiv: 0906.1317, 2009.

[14] J. Cerny. Geometric graphs with no three disjoint edges. Discrete & Computational Geometry, 34(4):679-695, 2005.

[15] J. Cerny, Z. Dvorak, V. Jelinek, and J. Kara. Noncrossing Hamiltonian paths in geometric graphs. Discrete Applied Mathematics, 155(9):1096-1105, 2007.

[16] D. W. Cranston and S. O. Hamiltonicity in connected regular graphs. Inf. Process. Lett., 113(2224):858-860, 2013.

[17] G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 2:69-81, 1952.

[18] A. Dumitrescu. On two lower bound constructions. In Proceedings of the 11th Canadian Conference on Computational Geometry, UBC, Vancouver, British Columbia, Canada, August 15-18, 1999, 1999.

[19] P. Erdos. On the set of distances of n points. The American Mathematical Monthly, 53(5):248-250, 1946.

[20] S. Felsner. Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry. Vieweg, Wiesbaden, 2004.

[21] A. Garcia, M. Noy, and J. Tejel. Lower bounds on the number of crossing-free subgraphs of KN. Comput. Geom., 16(4):211-221, 2000.

[22] W. Goddard, M. Katchalski, and D. J. Kleitman. Forcing disjoint segments in the plane. Eur. J. Comb, 17(4):391-395, 1996.

[23] P. Hall. On representatives of subsets. Journal of the London Mathematical Society, s1-10(1):26-30, 1935.

[24] F. Harary. Graph theory. Addison-Wesley, 1991.

[25] M. Hasheminezhad, B. D. McKay, and T. Reeves. Recursive generation of simple planar 5-regular graphs and pentangulations. J. Graph Algorithms Appl., 15(3):417-436, 2011.

[26] J. Hershberger and S. Suri. Applications of a semi-dynamic convex hull algorithm. BIT, 32(2):249-267, 1992.

[27] H. Hopf and E. Pannwitz. Aufgabe no. 167. Jahresbericht der Deutschen Mathematiker-Vereinigung, 43:114, 1934.

[28] M. Ishaque, D. L. Souvaine, and C. D. Toth. Disjoint compatible geometric matchings. Discrete & Computational Geometry, 49(1):89-131, 2013.

[29] C. Keller and M. Perles. On the smallest sets blocking simple perfect matchings in a convex geometric graph. Israel Journal of Mathematics, 187(1):465-484, 2012.

[30] S. Kundu. Bounds on the number of disjoint spanning trees. Journal of Combinatorial Theory, Series B, 17(2):199-203, 1974.

[31] Y. Kupitz. Extremal problems in combinatorial geometry. Aarhus University Lecture Notes Series, 53, 1979.

[32] C. Lo, J. Matousek, and W. L. Steiger. Algorithms for ham-sandwich cuts. Discrete & Computational Geometry, 11:433-452, 1994.

[33] T. Motzkin. Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products. Bull. Amer. Math. Soc., 54(4):352-360, 1948.

[34] C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 36(1):445-450, 1961.

[35] M. M. Newborn and W. O. J. Moser. Optimal crossing-free Hamiltonian circuit drawings of [K.sub.n]. J. Comb. Theory, Ser. B, 29(1):13-26, 1980.

[36] J. Pach and J. Torocsik. Some geometric applications of Dilworth's theorem. Discrete & Computational Geometry, 12:1-7, 1994.

[37] M. Sharir and A. Sheffer. Counting triangulations of planar point sets. Electr. J. Comb., 18(1), 2011.

[38] M. Sharir and E. Welzl. On the number of crossing-free matchings, cycles, and partitions. SIAM J. Comput., 36(3):695-720, 2006.

[39] D. Sitton. Maximum matchings in complete multipartite graphs. Furman University Electronic Journal of Undergraduate Mathematics, 2:6-16, 1996.

[40] A. Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. New York: Springer, 2009.

[41] J. W. Sutherland. Losung der aufgabe 167. Jahresbericht der Deutschen Mathematiker-Vereinigung, 45:33-35, 1935.

[42] G. Toth. Note on geometric graphs. J. Comb. Theory, Ser. A, 89(1):126-132, 2000.

[43] G. Toth and P. Valtr. Geometric graphs with few disjoint edges. Discrete & Computational Geometry, 22(4):633-642, 1999.

[44] W. T. Tutte. On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society, 36(1):221-230, 1961.

* Research supported by NSERC.

Tab. 1: Number of plane perfect matchings in a point set P of n points (n is even). Matching [for all]P :[greater 3P :[less than than or equal to] or equal to] total [2.sup.n] [21, 33] [2.sup.n] [33] edge-disjoint [[log.sub.2] n] - 1 [n/3] non-crossing 2 2 edge-disjoint Matching 3P :[greater VP :[less than than or or equal to] equal to] total [2.sup.n] [21] O([10.05.sup.n]) [38] edge-disjoint n/5 n - 1 non-crossing 5 5 edge-disjoint

Printer friendly Cite/link Email Feedback | |

Author: | Biniaz, Ahmad; Bose, Prosenjit; Maheshwari, Anil; Smid, Michiel |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Jun 1, 2015 |

Words: | 14129 |

Previous Article: | Symmetries of monocoronal tilings. |

Next Article: | Persisting randomness in randomly growing discrete structures: graphs and search trees. |

Topics: |