Pasar al contenido principal

GRAFOS GEOMETRICOS Y ABSTRACTOS: TEORIA Y APLICACIONES

PID2023-150725NB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2023
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 35
Encontrada(s) 1 página(s)

RUC. Repositorio da Universidade da Coruña
Publicación Artículo científico (JournalArticle)

Upper Bounds on the k-Isolation Number

  • Borg, Peter
  • Lemańska, Magdalena
  • Mora, Mercè
  • Souto Salorio, María José
[Abstract]: The isolation number of a graph G (also called the vertex-edge domination number of G), denoted by ι(G), is the size of a smallest subset D of the vertex set V(G) of G such that G −N[D] (the graph obtained by deleting the closed neighbourhood N[D] of D from G) has no edges. For k ≥ 1, the k-isolation number of G, denoted by ιk(G), is the size of a smallest subset D of V(G) such that the maximum degree of G − N[D] is at most k −1. Thus, ι1(G) = ι(G). Let n and ℓ be the number of vertices and the number of leaves of G, respectively. We show that if n ≥ 3 and G is connected and not a star, then ιk(G) ≤ n−ℓ 2 . We also show that if G is a tree T, then ι(T) ≤ n+ℓ 4 and ιk(T) ≤ n+ℓ 2k+1 for k ≥ 2. These bounds together improve the inequality ιk(T) ≤ n k+2 of Caro and Hansberg except that their inequality is better if k ≥ 2 and k−1 k+2n <ℓ< k k+2n. Each of the new bounds is attainable if it is an integer. For each of them, we characterize the graphs that attain it., The authors are grateful to the anonymous referees for checking the paper and providing constructive remarks that led to an improvement in the presentation. M. Mora is partially supported by grants Gen.Cat.DGR 2021-SGR-00266 from AGAUR and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. M.J. Souto-Salorio is partially supported by grant LATCHING (PID2023-147129OB-C21) funded by MICIU/AEI/10.13039/501100011033 and ERDF, EU, and by grant SCANNER-UDC (PID2020-113230RB-C21) funded by MICIU/AEI/10.13039/501100011033., Agència de Gestió d'Ajuts Universitaris i de Recerca; 2021-SGR-00266
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Geometric thickness of multigraphs is ¿R-Complete

  • Förster, Henry
  • Kindermann, Philipp
  • Miltzow, Tillmann
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Terziadis, Soeren
  • Vogtenhuber, Birgit
We say that a (multi)graph has geometric thickness t if there exists a straight-line drawing and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t. This problem was shown to be NP-hard for (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is -complete already for thickness 30. Moreover, our reduction shows that the problem is -complete for 4392-planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are -complete., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Bowties and hourglasses: intersections of double-wedges or: stabbing and avoiding line segments

  • Bertschinger, Daniel
  • Förster, Henry
  • Klute, Fabian Maximilian|||0000-0002-7791-3604
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Schnider, Patrick
  • Vogtenhuber, Birgit
We study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be both bowties (which do not contain a vertical line) or hourglasses (which contain a vertical line), in contrast to earlier studies that focused on arrangements of only bowties. This generalization changes the setting drastically, in particular, with respect to all arguments involving the point-line duality. Namely, a point in the intersection of all double-wedges is equivalent to a line that stabs a set of segments Y (corresponding to the bowties) while it avoids a different set of segments A (corresponding to the complement of the hourglasses). We show that in this general setting, the intersection of n double-wedges may consist of O(n2) interior-disjoint regions. Further, we discuss Gallai-type results for arrangements of segments and anti-segments, and we provide algorithms for computing the intersection of such arrangements with worst-case optimal running time. Finally, we also prove that we can find a single intersection point in almost optimal running time, assuming that 3SUM admits no truly subquadratic-time algorithm., This work was initiated at the 6th DACH Workshop on Arrangements and Drawings in Stels, Switzerland. We thank the organizers for making this workshop possible, especially in those times, and the other participants for fruitful discussions. H.F. was supported by DFG grant KA812-18/2. F.K. and I.P. were partially supported by grant PID2023150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. I.P. is a Serra Húnter Fellow. B.V. was partially supported by the Austrian Science Fund within the collaborative D-A-CH project Arrangements and Drawings as FWF project I 3340-N35. We thank the anonymous reviewers for their comments, which helped us strengthen our results.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Upper bounds on the k-isolation number

  • Borg, Peter
  • Lemanska, Magdalena
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Souto Salorio, María josé
The isolation number of a graph G (also called the vertex-edge domination number of G), denoted by i(G), is the size of a smallest subset D of the vertex set V(G) of G such that G -N[D] (the graph obtained by deleting the closed neighbourhood N[D] of D from G) has no edges. For k >= 1, the k-isolation number of G, denoted by ik(G), is the size of a smallest subset D of V(G) such that the maximum degree of G -N[D] is at most k-1. Thus, i1(G) =i(G). Let n and l be the number of vertices and the number of leaves of G, respectively. We show that if n>=3 and G is connected and not a star, then ik(G) <= (n-l)/2. We also show that if G is a tree T, then i(T) <= (n+l)/4 and ik(T) <= (n+l)/(2k+1) for k>=2. These bounds together improve the inequality ik(T) <= n/(k+2) of Caro and Hansberg except that their inequality is better if k>=2 and (k-1)/(k+2) * n < l < k/(k+2) *n. Each of the new bounds is attainable if it is an integer. For each of them, we characterize the graphs that attain it., The authors are grateful to the anonymous referees for checking the paper and providing constructive remarks that led to an improvement in the presentation. M. Mora is partially supported by grants Gen.Cat.DGR 2021-SGR-00266 from AGAUR and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. M.J. Souto-Salorio is partially supported by grant LATCHING (PID2023-147129OB-C21) funded by MICIU/AEI/10.13039/501100011033 and ERDF, EU, and by grant SCANNER-UDC (PID2020-113230RB-C21) funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On the number of quadrilaterals in higher order Voronoi diagrams

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Antimagic and product antimagic graphs with pendant edges

  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Tey Carrera, Joaquín
Let G = (V, E) be a simple graph of size m and L a set of m distinct real numbers. An L-labeling of G is a bijection f : E --> L. We say that f is an antimagic L-labeling if the induced vertex sum f+ : V --> R defined as f+(u) = Suv¿E f(uv) is injective. Similarly, f is a product antimagic L-labeling of G if the induced vertex product fo : V --> R defined as fo(u) = ¿uv¿E f(uv) is injective. A graph G is antimagic (resp. product antimagic) if it has an antimagic (resp. a product antimagic) L-labeling for L = {1,2,...,m}. Hartsfield and Ringel conjectured that every simple connected graph distinct from K2 is antimagic, but the conjecture remains widely open. We prove, among other results, that every connected graph of size m, >= 3, admits an antimagic L-labeling for every arithmetic sequence L of m positive real numbers, if every vertex of degree at least three is a support vertex. As a corollary, we derive that these graphs are antimagic, reinforcing the veracity of the conjecture by Hartsfield and Ringel. Moreover, these graphs admit also a product antimagic L-labeling provided that the smallest element of L is at least one. The proof is constructive., M. Mora is partially supported by grants PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033 and Gen. Cat. SGR2023 (2021SGR00266)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The farthest color voronoi diagram in the plane

  • Mantas, Ioannis
  • Papadopoulou, Evanthia|||0000-0003-0144-7384
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Wang, Zeyu|||0009-0004-4207-198X
The farthest-color Voronoi diagram (FCVD) is defined on a set of n points in the plane, where each point is labeled with one of m colors. The colored points constitute a family P of m clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is O(na(m)+ str(P)), where str(P) is a parameter reflecting the number of straddles between pairs of clusters, which is O(m(n-m)). The bound reduces to O(n + str(P)) if the clusters are pairwise non-crossing. We also present a lower bound, establishing that the complexity of the FCVD can be O(n+m^2), even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in O((n + str(P))log^3n)-time, and in certain special cases in O(n log(n)) time., Apreliminary and, partial portion of this work was presented at the 14th Latin American Theoretical Informatics Symposium (LATIN 2020) [23]. I. M., E. P., and Z.W were supported in part by the Swiss National Science Foundation, projects SNF 200021E-154387, SNF 200021E-201356. R. S. was supported by project PID2023-150725NB-I00/ MICIU/ AEI/ 10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Crossing-free monochromatic trees for bicolored point sets

  • Fernández Goycoolea, José
  • Hernán Herrera, Luis|||0000-0001-7338-7611
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos|||0000-0002-0095-1725
© 2026 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study the problem of connecting the points of a bicolored point set S = R U B by monochromatic non-overlapping geometric trees. As has been done for similar geometric problems, we characterize the minimum number of trees required in terms of the number t of non-monochromatic edges in the convex hull. Then, we propose an algorithm to construct this forest aiming to maintain the trees’ diameter long. The algorithm constructs two non-overlapping caterpillar trees when t <= 2, and a forest of trees composed of linked caterpillars if t > 2. Moreover, a process to flatten such caterpillars into paths when possible is discussed and exemplified. A qualitative comparison with an existing algorithm is also presented., Supported by project DICYT 042332PL, Vicerrector´ıa de Investigaci´on, Desarrollo e Innovaci´on USACH (Chile). Supported by grant PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computing largest minimum color-spanning intervals of imprecise points

  • Acharyya, Ankush
  • Keikha, Vahideh
  • Saumell, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
The authors would like to thank Ramesh K. Jallu and Maarten Löffler for fruitful discussions. A. Acharyya was supported by the Science and Engineering Research Board, Department of Science and Technology, India, grant number SRG/2022/002277. V. Keikha was supported by the CAS PPPLZ grant L100302301, and the institutional support RVO: 67985807. M. Saumell was supported by the Czech Science Foundation, grant number 23-04949X. R. Silveira was partially supported by grant PID2023-150725NB-I00/ MCIN/ AEI/ 10.13039/501100011033., We study a geometric facility location problem under imprecision. Given n unit segments on the real line, each with one of k colors, the goal is to place a point on each segment such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given segment of each color. We prove that if the input segments are pairwise disjoint, the problem can be solved in O(n) time, even for segments of arbitrary length. For overlapping segments, the problem becomes much more difficult. Nevertheless, we show that it can be solved in O(nlog^2n) time when k = 2, by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Coloraciones por entornos en jaulas de Moore

  • Hernando Martín, María del Carmen|||0000-0002-3864-6566
  • Araujo Pardo, Gabriela
A k-coloring of a graph G is a k-partition = S1 Sk of V(G) into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices uv belonging to the same color Si, the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number, denoted by NL(G), is the minimum cardinality of a neighbor-locating coloring of G. In this paper we study the neighbor-locating coloring of graphs that are Moore cages.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Sibson's formula for higher order Voronoi diagrams

  • Claverol Aguas, Mercè|||0000-0002-9138-8594
  • Heras Parrilla, Andrea de las
  • Huemer, Clemens|||0000-0001-7557-0823
  • Lara, Dolores
Let S be a set of n points in general position in . The order-k Voronoi diagram of S, , is a subdivision of into cells whose points have the same k nearest points of S. Sibson, in his seminal paper from 1980 (A vector identity for the Dirichlet tessellation), gives a formula to express a point Q of S as a convex combination of other points of S using ratios of volumes of the intersection of cells of and the cell of Q in . The natural neighbour interpolation method is based on Sibson's formula. We generalize his result to express Q as a convex combination of other points of S by using ratios of volumes from Voronoi diagrams of any given order., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • Tuttle, Tyler
Let ¿(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x,y ¿ S, where every geodesic disk containing x and y contains ¿(n) points of S. We establish upper and lower bounds for ¿(n), and show that n 5 +1 = ¿(n) = n 4 +1. We also show that there always exist two points x,y ¿ S such that every geodesic disk with x and y on its boundary contains at least 16 665 (n - 2) ˜ n-2 41.6 points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of n 3 +1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of n-2 two-colored version of the problem., G. E., D. O. and R. S. are partially supported by grants PID2019-104129GB-I00 and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. P. B. and T. T. are supported in part by NSERC., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the number of drawings of a combinatorial triangulation

  • Cruces, Belén
  • Huemer, Clemens|||0000-0001-7557-0823
  • Lara, Dolores
C. H. was supported by Grant PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033 and by Gen. Cat. DGR 2021-SGR-00266, In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and n additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation T and a point set S such that T can be drawn on S in at least O(1, 31^n) ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The voronoi diagram of rotating rays with applications to floodlight illumination

  • Alegria, Carlos
  • Mantas, Ioannis
  • Papadopoulou, Evanthia|||0000-0003-0144-7384
  • Savic, Marko
  • Seara Ojea, Carlos|||0000-0002-0095-1725
  • Suderland, Martin|||0000-0002-6604-6381
34 p. This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/[10.1007/s00453-025-01368-y], We study the Voronoi Diagram of Rotating Rays, a Voronoi structure where the input sites are rays and the distance function between a point and a site/ray is their counterclockwise angular distance. This novel Voronoi diagram is motivated by illumination and coverage problems, where a domain must be covered by floodlights, which are wedges of uniform angle, and the goal is to find the minimum angle necessary to cover the domain. This angle is called the Brocard angle and it is encoded in the Voronoi diagram of rotating rays. We study the diagram in the plane and present its structural properties, its combinatorial complexity bounds, and a construction algorithm. If the rays are induced by a convex polygon, we show how to construct the rotating rays Voronoi diagram within the polygon in optimal linear time. We can thus compute the Brocard angle of the polygon in the same time. Floodlights are used to model devices with limited sensing range, like surveillance cameras or directional antennas. In this context, the Brocard angle reveals the minimum range necessary for a set of devices to cover a domain., Acknowledgements: Initial discussions took place at the Intensive Research Program in Discrete, Combinatorial and Computational Geometry in Barcelona, Spain, in 2018. We are grateful to the 44 organizers for providing the platform to meet and collaborate. We also thank Hendrik Schrezenmaier 45 for early discussions related to the results of Section 3.1. Funding: Carlos Alegría: Supported by projects MIUR Proj. “AHeAD” no 20174LF3T8 and European Union’s Horizon 2020 No. 734922. Ioannis Mantas: Supported in part by SNF project 200021E_154387. Evanthia Papadopoulou: Supported in part by SNF projects 200021E_154387 and 200021E_201356. Marko Savić: Supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2022-14/200125), and the Provincial Secretariat for Higher Education and Scientific Research, Province of Vojvodina. Carlos Seara: Supported by projects PID2023-150725NB-I00 funded by Ministerio de Ciencia e Innovación/AEI/10.13039/501100011033 and European Union’s Horizon 2020 No. 734922. Martin Suderland: Supported in part by SNF project 200021E_201356., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Shortest coordinated motions for square robots

  • Esteban, Guillermo
  • Halperin, Dan
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations (feasible in the sense that the two squares are interior disjoint), find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. In this paper we present an adaptation of the tools developed for the case of disks to the case of squares. We show that in certain aspects the case of squares is more complicated, requiring additional and more involved arguments over the case of disks., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. G. E. and R. I. S. were partially supported by projects PID2019-104129GB-I00 and PID2023-150725NBI00, funded by MICIU/AEI/10.13039/501100011033. Work by D. H. has been supported in part by the Israel Science Foundation (grant nos. 1736/19 and 2261/23), by NSF/US-Israel-BSF (grant no. 2019754), by the Blavatnik Computer Science Research Fund, and by the Shlomo Shmelzer Institute for Smart Transportation at Tel Aviv University., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Containment results on points and spheres

  • Heras Parrilla, Andrea de las
  • Flores Peñaloza, David
  • Huemer, Clemens|||0000-0001-7557-0823
  • Orden Martin, David
Let S be a set of n points in general position in R d . We show several containment results for points from S in spheres determined by d + 1 points of S. Among them, we prove a Delaunay-type criterion for point sets in R 3 . Also, we show bounds on the expected number of points from S contained in a sphere determined by four points chosen uniformly at random from S ¿ R 3 . A tight upper bound construction is provided, obtained by inversion of points on the moment curve. We also show a lower bound and prove that it is best possible for n = 7. In order to do so, we solve the recurrence relation T(n) = l n n-5 T(n - 1)m with base case T(7) = 29. This is of independent interest, since most recurrence relations of this type seem not to have a solution in closed form., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Shortest descending path is not solvable within ACMQ

  • Franco Sánchez, Victor|||0009-0007-4163-2476
  • Herrero Bravo, Alex
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
In this paper, we consider the Shortest Descending Path (SDP) Problem. The SDP Problem is the problem of computing a shortest path between two given points on a polyhedral terrain, with the additional constraint that the path may never increase in z coordinate. No polynomial algorithm is known to compute an SDP. In this paper, we present a construction demonstrating that an SDP is not computable within the ACMQ model, even in a terrain consisting of only three triangles. This result provides evidence of the diff iculty of solving the problem exactly.
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Domination in cylindrical graphs

  • Martínez García, José Antonio
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Puertas González, María Luz
  • Tejel Altarriba, Francisco Javier
The domination number ¿(Cm ¿ Pn) of the Cartesian product Cm ¿ Pn of a cycle and a path has been computed when m = 0, 2 (mod 5). In the remaining cases m = 1, 3, 4 (mod 5), exact formulae for ¿(Cm ¿ Pn) have been determined when either n = 22 or m = 30. For the rest of the cases, only lower and upper bounds for ¿(Cm ¿ Pn) are known. In this paper, we study ¿(Cm ¿ Pn) when m = 1, 3, 4 (mod 5). In particular, we compute ¿(Cm ¿ Pn) if 30 = m = 1 (mod 5) and n = 22, and we provide tighter lower and upper bounds for ¿(Cm ¿ Pn) if m = 3, 4 (mod 5)., Peer Reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Domination in cylindrical graphs

Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Coloraciones por entornos en jaulas de Moore

  • Hernando Martín, María del Carmen
  • Araujo Pardo, Gabriela
A k-coloring of a graph G is a k-partition = S1 Sk of V(G) into independent sets, called colors. A k-coloring is called neighbor-locating if for every pair of vertices uv belonging to the same color Si, the set of colors of the neighborhood of u is different from the set of colors of the neighborhood of v. The neighbor-locating chromatic number, denoted by NL(G), is the minimum cardinality of a neighbor-locating coloring of G. In this paper we study the neighbor-locating coloring of graphs that are Moore cages., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Shortest descending path is not solvable within ACMQ

  • Franco Sánchez, Victor
  • Herrero Bravo, Alex
  • Silveira, Rodrigo Ignacio
In this paper, we consider the Shortest Descending Path (SDP) Problem. The SDP Problem is the problem of computing a shortest path between two given points on a polyhedral terrain, with the additional constraint that the path may never increase in z coordinate. No polynomial algorithm is known to compute an SDP. In this paper, we present a construction demonstrating that an SDP is not computable within the ACMQ model, even in a terrain consisting of only three triangles. This result provides evidence of the diff iculty of solving the problem exactly., Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Geometric thickness of multigraphs is ¿R-Complete

  • Förster, Henry
  • Kindermann, Philipp
  • Miltzow, Tillmann
  • Parada Muñoz, Irene María de
  • Terziadis, Soeren
  • Vogtenhuber, Birgit
We say that a (multi)graph has geometric thickness t if there exists a straight-line drawing and a t-coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t. This problem was shown to be NP-hard for (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is -complete already for thickness 30. Moreover, our reduction shows that the problem is -complete for 4392-planar graphs, where a graph is k-planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are -complete., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Containment results on points and spheres

  • Heras Parrilla, Andrea de las
  • Flores Peñaloza, David
  • Huemer, Clemens
  • Orden Martin, David
Let S be a set of n points in general position in R d . We show several containment results for points from S in spheres determined by d + 1 points of S. Among them, we prove a Delaunay-type criterion for point sets in R 3 . Also, we show bounds on the expected number of points from S contained in a sphere determined by four points chosen uniformly at random from S ¿ R 3 . A tight upper bound construction is provided, obtained by inversion of points on the moment curve. We also show a lower bound and prove that it is best possible for n = 7. In order to do so, we solve the recurrence relation T(n) = l n n-5 T(n - 1)m with base case T(7) = 29. This is of independent interest, since most recurrence relations of this type seem not to have a solution in closed form., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The farthest color voronoi diagram in the plane

  • Mantas, Ioannis
  • Papadopoulou, Evanthia
  • Silveira, Rodrigo Ignacio
  • Wang, Zeyu
The farthest-color Voronoi diagram (FCVD) is defined on a set of n points in the plane, where each point is labeled with one of m colors. The colored points constitute a family P of m clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is O(na(m)+ str(P)), where str(P) is a parameter reflecting the number of straddles between pairs of clusters, which is O(m(n-m)). The bound reduces to O(n + str(P)) if the clusters are pairwise non-crossing. We also present a lower bound, establishing that the complexity of the FCVD can be O(n+m^2), even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in O((n + str(P))log^3n)-time, and in certain special cases in O(n log(n)) time., Apreliminary and, partial portion of this work was presented at the 14th Latin American Theoretical Informatics Symposium (LATIN 2020) [23]. I. M., E. P., and Z.W were supported in part by the Swiss National Science Foundation, projects SNF 200021E-154387, SNF 200021E-201356. R. S. was supported by project PID2023-150725NB-I00/ MICIU/ AEI/ 10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
  • Tuttle, Tyler
Let ¿(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x,y ¿ S, where every geodesic disk containing x and y contains ¿(n) points of S. We establish upper and lower bounds for ¿(n), and show that n 5 +1 = ¿(n) = n 4 +1. We also show that there always exist two points x,y ¿ S such that every geodesic disk with x and y on its boundary contains at least 16 665 (n - 2) ˜ n-2 41.6 points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of n 3 +1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of n-2 two-colored version of the problem., G. E., D. O. and R. S. are partially supported by grants PID2019-104129GB-I00 and PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033. P. B. and T. T. are supported in part by NSERC., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Shortest coordinated motions for square robots

  • Esteban, Guillermo
  • Halperin, Dan
  • Silveira, Rodrigo Ignacio
We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations (feasible in the sense that the two squares are interior disjoint), find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. In this paper we present an adaptation of the tools developed for the case of disks to the case of squares. We show that in certain aspects the case of squares is more complicated, requiring additional and more involved arguments over the case of disks., Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature. G. E. and R. I. S. were partially supported by projects PID2019-104129GB-I00 and PID2023-150725NBI00, funded by MICIU/AEI/10.13039/501100011033. Work by D. H. has been supported in part by the Israel Science Foundation (grant nos. 1736/19 and 2261/23), by NSF/US-Israel-BSF (grant no. 2019754), by the Blavatnik Computer Science Research Fund, and by the Shlomo Shmelzer Institute for Smart Transportation at Tel Aviv University., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The voronoi diagram of rotating rays with applications to floodlight illumination

  • Alegria, Carlos
  • Mantas, Ioannis
  • Papadopoulou, Evanthia
  • Savic, Marko
  • Seara Ojea, Carlos
  • Suderland, Martin
34 p. This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/[10.1007/s00453-025-01368-y], We study the Voronoi Diagram of Rotating Rays, a Voronoi structure where the input sites are rays and the distance function between a point and a site/ray is their counterclockwise angular distance. This novel Voronoi diagram is motivated by illumination and coverage problems, where a domain must be covered by floodlights, which are wedges of uniform angle, and the goal is to find the minimum angle necessary to cover the domain. This angle is called the Brocard angle and it is encoded in the Voronoi diagram of rotating rays. We study the diagram in the plane and present its structural properties, its combinatorial complexity bounds, and a construction algorithm. If the rays are induced by a convex polygon, we show how to construct the rotating rays Voronoi diagram within the polygon in optimal linear time. We can thus compute the Brocard angle of the polygon in the same time. Floodlights are used to model devices with limited sensing range, like surveillance cameras or directional antennas. In this context, the Brocard angle reveals the minimum range necessary for a set of devices to cover a domain., Acknowledgements: Initial discussions took place at the Intensive Research Program in Discrete, Combinatorial and Computational Geometry in Barcelona, Spain, in 2018. We are grateful to the 44 organizers for providing the platform to meet and collaborate. We also thank Hendrik Schrezenmaier 45 for early discussions related to the results of Section 3.1. Funding: Carlos Alegría: Supported by projects MIUR Proj. “AHeAD” no 20174LF3T8 and European Union’s Horizon 2020 No. 734922. Ioannis Mantas: Supported in part by SNF project 200021E_154387. Evanthia Papadopoulou: Supported in part by SNF projects 200021E_154387 and 200021E_201356. Marko Savić: Supported by the Ministry of Education, Science and Technological Development of the Republic of Serbia (Grant No. 451-03-68/2022-14/200125), and the Provincial Secretariat for Higher Education and Scientific Research, Province of Vojvodina. Carlos Seara: Supported by projects PID2023-150725NB-I00 funded by Ministerio de Ciencia e Innovación/AEI/10.13039/501100011033 and European Union’s Horizon 2020 No. 734922. Martin Suderland: Supported in part by SNF project 200021E_201356., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Domination in cylindrical graphs

  • Martínez García, José Antonio
  • Mora Giné, Mercè
  • Puertas González, María Luz
  • Tejel Altarriba, Francisco Javier
The domination number ¿(Cm ¿ Pn) of the Cartesian product Cm ¿ Pn of a cycle and a path has been computed when m = 0, 2 (mod 5). In the remaining cases m = 1, 3, 4 (mod 5), exact formulae for ¿(Cm ¿ Pn) have been determined when either n = 22 or m = 30. For the rest of the cases, only lower and upper bounds for ¿(Cm ¿ Pn) are known. In this paper, we study ¿(Cm ¿ Pn) when m = 1, 3, 4 (mod 5). In particular, we compute ¿(Cm ¿ Pn) if 30 = m = 1 (mod 5) and n = 22, and we provide tighter lower and upper bounds for ¿(Cm ¿ Pn) if m = 3, 4 (mod 5)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Crossing-free monochromatic trees for bicolored point sets

  • Fernández Goycoolea, José
  • Hernán Herrera, Luis
  • Pérez Lantero, Pablo
  • Seara Ojea, Carlos
© 2026 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, We study the problem of connecting the points of a bicolored point set S = R U B by monochromatic non-overlapping geometric trees. As has been done for similar geometric problems, we characterize the minimum number of trees required in terms of the number t of non-monochromatic edges in the convex hull. Then, we propose an algorithm to construct this forest aiming to maintain the trees’ diameter long. The algorithm constructs two non-overlapping caterpillar trees when t <= 2, and a forest of trees composed of linked caterpillars if t > 2. Moreover, a process to flatten such caterpillars into paths when possible is discussed and exemplified. A qualitative comparison with an existing algorithm is also presented., Supported by project DICYT 042332PL, Vicerrector´ıa de Investigaci´on, Desarrollo e Innovaci´on USACH (Chile). Supported by grant PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Shortest paths in portalgons

  • Ophelders, Tim
  • Löffler, Maarten
  • Silveira, Rodrigo Ignacio
  • Staals, Frank
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons., They allowed us to significantly improve the presentation of our paper. R.S. was partially supported by MICIU through project PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Antimagic and product antimagic graphs with pendant edges

  • Mora Giné, Mercè
  • Tey Carrera, Joaquín
Let G = (V, E) be a simple graph of size m and L a set of m distinct real numbers. An L-labeling of G is a bijection f : E --> L. We say that f is an antimagic L-labeling if the induced vertex sum f+ : V --> R defined as f+(u) = Suv¿E f(uv) is injective. Similarly, f is a product antimagic L-labeling of G if the induced vertex product fo : V --> R defined as fo(u) = ¿uv¿E f(uv) is injective. A graph G is antimagic (resp. product antimagic) if it has an antimagic (resp. a product antimagic) L-labeling for L = {1,2,...,m}. Hartsfield and Ringel conjectured that every simple connected graph distinct from K2 is antimagic, but the conjecture remains widely open. We prove, among other results, that every connected graph of size m, >= 3, admits an antimagic L-labeling for every arithmetic sequence L of m positive real numbers, if every vertex of degree at least three is a support vertex. As a corollary, we derive that these graphs are antimagic, reinforcing the veracity of the conjecture by Hartsfield and Ringel. Moreover, these graphs admit also a product antimagic L-labeling provided that the smallest element of L is at least one. The proof is constructive., M. Mora is partially supported by grants PID2023-150725NB-I00 funded by MICIU/AEI/10.13039/501100011033 and Gen. Cat. SGR2023 (2021SGR00266)., Peer Reviewed, Postprint (published version)
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Scientific basis of sherry wine food pairing: integrating consumer perception, sensory analysis and volatile profiling

  • Bienvenido, Daniel
  • Durán Guerrero, Enrique
  • Orden Martín, David|||0000-0001-5403-8467
  • Rodríguez Dodero, Carmen
Sherry wines from the Jerez–Xérès–Sherry PDO are globally renowned for their unique sensory complexity, yet their food pairing guidelines have traditionally remained empirical. This study aims to establish a scientific foundation for these harmonies by integrating consumer perception, descriptive sensory analysis, and volatile compound profiling. Three Sherry styles (Fino, Oloroso, and Pedro Ximénez) were evaluated against fifteen food matrices using consumer tastings (Likert and Linking tests via the SensoGraph application), an expert consensus group, and GC–MS techniques (SBSE and HSSE). Results indicate that Fino exhibits a strong affinity for saline and umami profiles, while Oloroso harmonizes best with umami taste and substantial body. Conversely, Pedro Ximénez is driven by sweetness and persistence, with saltiness acting as a primary antagonist. At the molecular level, the research suggested the existence of potential chemical correspondences, such as the furan family in the PX–chocolate pairing. However, findings suggest that pairing success depends more on the perceptual relevance and odor potency of shared molecules than on the absolute count of common compounds. This study provides certain evidence that pairing quality is determined by specific sensory and chemical interactions, transitioning Sherry wine gastronomy from intuitive tradition toward a systematic, indicative model., Agencia Estatal de Investigación, Universidad de Alcalá
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Contribución de congreso (ConferenceOutput)

On geodesic disks enclosing many points

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo|||0000-0002-0751-7729
  • Orden Martín, David|||0000-0001-5403-8467
  • Silveira, Rodrigo I.
  • Tuttle, Tyler
19th International Symposium on Algorithms and Data Structures (WADS 2025)., Let Π(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x, y ∈ S, where every geodesic disk containing x and y contains Π(n) points of S. We establish upper and lower bounds for Π(n), and show that ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +1. We also show that there always exist two points x, y ∈ S such that every geodesic disk with x and y on its boundary contains at least 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem., Agencia Estatal de Investigación
e_Buah Biblioteca Digital Universidad de Alcalá
Publicación Artículo científico (JournalArticle)

Check-all-that-apply and storyworld possible selves: what consumer research methods can do for the study of narrative engagement

  • Martínez Martínez, María Ángeles|||0000-0001-6473-1249
  • Orden Martín, David|||0000-0001-5403-8467
  • Fernández Fernández, Encarnación
The empirical study of literary experiences affords the opportunity to investigate the extent to which the interpretations of literary critics may coincide with the meaning construction operations of flesh-and-blood readers. The present study explores the analytical potential of a statistics-based Check-all-that-apply (CATA) methodology, traditionally used in consumer research, in the study of real reader response. To this purpose, an online questionnaire designed along CATA lines is used to investigate the emergence of storyworld possible selves during narrative interaction with the graphic short story "City" (Wasco, 2015). The findings are compared to those of two previous studies of this short story, one literary (Herman & Vervaeck, 2019) and the other empirical (Martínez & Herman, 2020), and suggest that a CATA methodology can enlighten aspects of readerly response not previously addressed, particularly regarding the idiosyncratic construction of the main character in ways relevant to individual readers" construction of themselves., Agencia Estatal de Investigación, Universidad de Alcalá