Ahmad Biniaz
Given a set P of n points and a class C of geometric objects, 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 ∈ C containing both p and q but no other points from P. We study G△(P) graphs where △ is the class of upward equilateral triangles. For point sets in general position, these graphs have been shown to be equivalent to half-Θ6 graphs and TD-Delaunay graphs. We show that G△(P) contains a matching of size at least ⌈(n-1)/3⌉ and this bound is tight. We also give some structural properties of Θ6 graphs, which contains both upward and downward equilateral triangles. We show that the block cut point graph of Θ6 is simply a path. We also show that any Θ6 can have at most 5n - 11 edges. Finally we prove that Θ6 has an strong matching of size at least ⌈n/5⌉ where triangles related to the edges of the matching do not overlap.
This is joint work with Jasine Babu, Anil Maheshwari, and Michiel Smid.