Fixed-orientation equilateral triangle matching of point sets

Given a point set P   and a class CC of geometric objects, GC(P)GC(P) is a geometric graph with vertex set P such that any two vertices p and q   are adjacent if and only if there is some C∈CC∈C containing both p and q but no other points from P  . We study G▽(P)G▽(P) graphs where ▽ is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x  -axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Θ6Θ6 graphs and TD-Delaunay graphs.The main result in our paper is that for point sets P   in general position, G▽(P)G▽(P) always contains a matching of size at least ⌈|P|−13⌉ and this bound is tight. We also give some structural properties of G✡(P)G✡(P) graphs, where ✡ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G✡(P)G✡(P) is simply a path. Through the equivalence of G✡(P)G✡(P) graphs with Θ6Θ6 graphs, we also derive that any Θ6Θ6 graph can have at most 5n−115n−11 edges, for point sets in general position.