View article

Let V be a set of n points in R ². The θ-graph of V is a geometric graph with vertex set V that has been studied extensively and which has several nice properties. We introduce a new variant of θ-graphs which we call ordered θ-graphs. These are graphs that are built incrementally by inserting the vertices one by one so that the resulting graph depends on the insertion order. We show that careful insertion orders can produce graphs with desirable properties including low spanning ratio, logarithmic maximum degree and logarithmic diameter.