Cáceres, JoséGarijo Royo, DeliaGonzález Herrera, AntonioMárquez Pérez, AlbertoPuertas, María Luz2024-04-302024-04-302015-07Cáceres, J., Garijo Royo, D., González Herrera, A., Márquez Pérez, A. y Puertas, M.L. (2015). Shortcut sets for Euclidean graphs. En XVI Spanish Meeting on Computational Geometry (EGC 2015), Barcelona (España).https://hdl.handle.net/11441/157349A 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.application/pdf4engAttribution-NonCommercial-NoDerivatives 4.0 Internacionalhttp://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/conferenceObjectinfo:eu-repo/semantics/openAccess