20130204
Fixedorientation equilateral triangle matching of point sets
Publication
Publication
Given a point set P and a class of geometric objects, 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 downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the xaxis 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 graphs and TDDelaunay graphs. The main result in our paper is that for point sets P in general position, G ∇(P) always contains a matching of size at least ⌈n  2/3⌉ and this bound cannot be improved above ⌈n  1/3⌉. We also give some structural properties of GStar of David(P) graphs, where Star of David 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 GStar of David(P) is simply a path. Through the equivalence of GStar of David(P) graphs with Θ6 graphs, we also deduce that any Θ6 graph can have at most 5n  11 edges, for point sets in general position.
Additional Metadata  

Keywords  Delaunay graphs, Geometric graphs, Matchings 
Persistent URL  dx.doi.org/10.1007/9783642360657_4 
Citation 
Babu, J. (Jasine), Biniaz, A. (Ahmad), Maheshwari, A, & Smid, M. (2013). Fixedorientation equilateral triangle matching of point sets. doi:10.1007/9783642360657_4
