Matchings in higher-order Gabriel graphs ?
Given a set P of n points in the plane, the order-k Gabriel graph on P , denoted by k-GG k - GG , has an edge between two points p and q if and only if the closed disk with diameter pq contains at most k points of P, excluding p and q . We study matching problems in k-GG k - GG graphs. We show that a Euclidean bottleneck matching of P  is contained in 10-GG 10 - GG , but 8-GG 8 - GG may not have any Euclidean bottleneck matching. In addition we show that 0-GG 0 - GG has a matching of size at least n ? 1 4 and this bound is tight. We also prove that 1-GG 1 - GG has a matching of size at least 2 ( n ? 1 ) 5 and 2-GG 2 - GG has a perfect matching. Finally we consider the problem of blocking the edges of k-GG k - GG .
matching higher-order gabriel graphs gabriel graphs