The Price of Order

André van Renssen

A θ-graph partitions the plane around each vertex into m disjoint cones, each having aperture θ = 2π/m. An ordered θ-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone.

In this talk, we improve the upper bound on the spanning ratio of a large family of ordered θ-graphs. We also show, however, that the bounds on the spanning ratio of unordered θ-graphs do not carry over to the ordered setting, showing for the first time that the nice properties of the ordered θ-graphs come at a price.