2016/02/01 by Prosenjit Bose, Pat Morin, Bose, Prosenjit +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1602.00399
openalex publication_date 2016/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present tight bounds on the spanning ratio of a large family of ordered θ-graphs. 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. We show that for any integer k ≥ 1, ordered θ-graphs with 4k + 4 cones have a tight spanning ratio of 1 + 2 sin(θ/2) / (cos(θ/2) - sin(θ/2)). We also show that for any integer k ≥ 2, ordered θ-graphs with 4k + 2 cones have a tight spanning ratio of 1 / (1 - 2 sin(θ/2)). We provide lower bounds for ordered θ-graphs with 4k + 3 and 4k + 5 cones. For ordered θ-graphs with 4k + 2 and 4k + 5 cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered θ-graphs have worse spanning ratios than unordered θ-graphs. Finally, we show that, unlike their unordered counterparts, the ordered θ-graphs with 4, 5, and 6 cones are not spanners.