Optimal Bounds on Theta-Graphs: More is not Always Better.

Abstract

We present tight upper and lower bounds on the spanning ratio of a large family of -graphs. We show that graphs with 4k+2 cones (k 1 and integer) have a spanning ratio of 1 + 2 sin(= 2), where is 2= (4k + 2). We also show that -graphs with 4k + 4 cones have spanning ratio at least 1 + 2 tan(= 2) + 2 tan 2 (= 2), where is 2= (4k + 4). This is somewhat surprising since, for equal values of k, the spanning ratio of -graphs with 4k + 4 cones is greater than that of -graphs with 4k + 2 cones, showing that increasing the number of cones can make the spanning ratio worse.