Presentation
Shortcut sets for Euclidean graphs
Author/s | Cáceres, José
Garijo Royo, Delia González Herrera, Antonio Márquez Pérez, Alberto Puertas, María Luz |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I Universidad de Sevilla. Departamento de Didáctica de las Matemáticas |
Publication Date | 2015-07 |
Deposit Date | 2024-04-30 |
Published in |
|
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 ... 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. |
Citation | 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). |
Files | Size | Format | View | Description |
---|---|---|---|---|
Shortcut sets for Euclidean ... | 629.9Kb | [PDF] | View/ | |