Shortcut sets for Euclidean graphs

Abstract

A Euclidean graph G is the locus of a rectilinear embedding of a planar graph in the Euclidean plane. A shortcut set S is a collection of segments with end points on G such that the Euclidean graph obtained from G byadding the segments in S has smaller diameter than G. The minimum cardinality of a shortcut set is the shortcut number scn(G). In this work, we first provide a tight upper bound on scn(G). We then show that it is possible, in polynomial time, to determine if scn(G) = 1 and, in that case, to construct a shortcut set that minimizes the diameter among all possible shortcut sets. Finally, we compute the shortcut number in some families of Euclidean graphs.