Ponencia
Shortcut sets for Euclidean graphs
Autor/es | Cáceres, José
Garijo Royo, Delia González Herrera, Antonio Márquez Pérez, Alberto Puertas, María Luz |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I Universidad de Sevilla. Departamento de Didáctica de las Matemáticas |
Fecha de publicación | 2015-07 |
Fecha de depósito | 2024-04-30 |
Publicado en |
|
Resumen | 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 ... 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. |
Cita | Cá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). |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Shortcut sets for Euclidean ... | 629.9Kb | [PDF] | Ver/ | |