We consider two classes of higher order proximity graphs dened on a set of points in the plane, namely, the k-Delaunay graph and the k-Gabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, chromatic number, and minimum number of layers nec- essary to partition the edges of the graphs so that no two edges of the same layer cross. 1 Introduction and basic notation Let S be a set of n points in the plane in general posi- tion (no three are collinear and no four are concyclic). A proximity graph on S is a geometric graph where two points are adjacent if they satisfy some specic proxim- ity criterion. Proximity graphs have been widely studied due to their theoretical interest and to their applications in situations where it is necessary to extract the \shape" of a set of points (see (10) for a survey). Adjacency in many proximity graphs is dened in terms of an empty region associated to any pair of points. To provide more exibility the denition of the graphs can be relaxed to allow up to k points to lie in the neighborhood region. This gives rise to higher order proximity graphs. In this paper we deal with two such graphs. We consider the k-Delaunay graph of S (denoted k-DG(S)), where a straight-line segment connects points pi;pj2 S if there exists a circleC(pi;pj) throughpi and pj with at most k points of S in its interior. The stan- dard Delaunay triangulation corresponds to 0-DG(S) and will be denoted by DT(S): We also study the k-Gabriel graph of S (denoted by k-GG(S)), where a straight-line segment connects points pi;pj2 S if the closed disk centered at the midpoint of