Skip to main content

Resultados relacionados

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

UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Computing largest minimum color-spanning intervals of imprecise points

  • Acharyya, Ankush
  • Keikha, Vahideh
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval 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 interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in time when , 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., A. Acharyya was supported by the DST-SERB 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 PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

The complexity of geodesic spanners using Steiner points

  • de Berg, Sarita
  • Ophelders, Tim
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Staals, Frank
  • Wulms, Jules
A geometric t-spanner G on a set S of n point sites in a metric space P is a subgraph of the complete graph on S such that for every pair of sites p,q the distance in G is a most t times the distance d(p,q) in P. We call a connection between two sites a link. In some settings, such as when P is a simple polygon with m vertices and a link is a shortest path in P, links can consist of T(m) segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce k Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. Surprisingly, we show that Steiner points have only limited utility. For a spanner that uses k Steiner points, we provide an ¿(nm/k) lower bound on the worst-case complexity of any (3 - e)spanner, and an ¿(mn1/(t+1)/k1/(t+1)) lower bound on the worst-case complexity of any (t - e)spanner, for any constant e ¿ (0,1) and integer constant t = 2. These lower bounds hold in all settings. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a 3-spanner with a given maximum complexity using k Steiner points. On the positive side, for trees we show how to build a 2t-spanner that uses k Steiner points of complexity O(mn1/t/k1/t + nlog(n/k)), for any integer t = 1. We generalize this result to forests, and apply it to obtain a 2v2t-spanner in a simple polygon with total complexity O(mn1/t(logk)1+1/t/k1/t + nlog2 n). When a link in the spanner can be any path between two sites, we show how to improve the spanning ratio in a simple polygon to (2k + e), for any constant e ¿(0,2k), and how to build a 6t-spanner in a polygonal domain with the same complexity., Tim Ophelders: partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s,t) , which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s,t) , which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path SGPw(s,t) , which is a shortest path whose edges are edges of the tessellation. The ratios ¿SGPw(s,t)¿¿SPw(s,t)¿ , ¿SVPw(s,t)¿¿SPw(s,t)¿ , ¿SGPw(s,t)¿¿SVPw(s,t)¿ provide estimates on the quality of the approximation. Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that ¿SGPw(s,t)¿¿SPw(s,t)¿=23v˜1.15 in the worst case, and this is tight., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Dynamic embeddings of dynamic single-source upward planar graphs

  • van der Hoog, Ivor
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Rotenberg, Eva
A directed graph G is upward planar if it admits a planar embedding where each edge is y-monotone. Unlike planarity testing, upward planarity testing is NP-hard except in restricted cases, such as when the graph has the single-source property (i.e., each connected component has one source). In this paper, we present a dynamic data structure for maintaining an upward combinatorial embedding -¿E (G) of a single-source upward planar graph subject to edge deletions, edge contractions, directed edge insertions across a face, and single-source-preserving vertex splits through specified corners (i.e., the gaps between pairs of consecutive edges that share a vertex and a face). We furthermore support changes to the embedding -¿E (G) in the form of subgraph flips that mirror or slide the placement of a subgraph that is connected to the rest of the graph via at most two vertices. Updates that are incompatible with the current upward planar embedding are identified and rejected. All update operations are supported as long as the graph remains upward planar. In addition, we support queries that can tell whether two vertices can be connected with a directed edge while the graph remains single-source (we call these uplinkability queries). If a pair of vertices are not uplinkable, we facilitate one-flip-linkable queries: These point to a flip that makes them uplinkable, if any such flip exists. We dynamically maintain a linear-size data structure on G which supports incidence queries between a vertex and a face, and uplinkability queries for vertex pairs. We support all updates and queries in O(log2 n) worst-case time., This research was supported by Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic Network Analysis”. Ivor van der Hoog: This project has additionally received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Eva Rotenberg: This research was additionally supported by Carlsberg Foundation Young Researcher Fellowship CF21-0302 “Graph Algorithms with Geometric Applications”., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Continuous mean distance of a weighted graph

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances between all pairs of vertices. This parameter provides a natural measure of the compactness of the graph, and has been intensively studied, together with several variants, including its version for weighted graphs. The continuous analog of the (discrete) mean distance is the mean of the distances between all pairs of points on the edges of the graph. Despite being a very natural generalization, to the best of our knowledge this concept has been barely studied, since the jump from discrete to continuous implies having to deal with an infinite number of distances, something that increases the difficulty of the parameter. In this paper, we show that the continuous mean distance of a weighted graph can be computed in time roughly quadratic in the number of edges, by two different methods that apply fundamental concepts in discrete algorithms and computational geometry. We also present structural results that allow for a faster computation of this continuous parameter for several classes of weighted graphs. Finally, we study the relation between the (discrete) mean distance and its continuous counterpart, mainly focusing on the relevant question of convergence when iteratively subdividing the edges of the weighted graph., This work was supported by grants PID2019-104129GB-I00/ AEI/ 10.13039/501100011033, Gen. Cat. 2017SGR1640, and PID2019-103900GB-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Shortest coordinated motion for square robots

  • Esteban Pascual, Guillermo
  • Halperin, Dan
  • Ruíz, Víctor
  • Sacristán Adinolfi, Vera|||0000-0003-0203-256X
  • 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, 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. We present an adaptation of the tools developed for the case of discs by Kirkpatrick and Liu [Characterizing minimum-length coordinated motions for two discs. Proceedings 28th CCCG, 252-259, 2016; CoRR abs/1607.04005, 2016.] to the case of squares. Certain aspects of the case of squares are more complicated, requiring additional and more involved arguments over the case of discs. Our contribution can serve as a basic component in optimizing the coordinated motion of two squares among obstacles, as well as for local planning in sampling-based algorithms, which are often used in practice, in the same setting., Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Graphs attaining the upper bound on the isolation number

  • Lemanska, Magdalena
  • Mora Giné, Mercè|||0000-0001-6923-0320
  • Souto Salorio, María josé
A set D of vertices of a graph is isolating if the set of vertices not belonging to D or not having a neighbour in D is independent. The isolation number of a graph G, denoted by ¿(G), is the minimum cardinality of an isolating set. It is known that ¿(G) = n/3 if G is a connected graph of order n, n = 3, different from a cycle of order 5. Moreover, trees attaining this upper bound have been characterized. In this work we characterize all unicyclic and block graphs of order n such that ¿(G) = n/3., Partially supported by projects PID2020-113230RB-C21 and PID2019-104129GBI00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and Gen.Cat. DGR2021-SGR-00266., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication 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
Publication Contribución de congreso (ConferenceOutput)

On k-plane insertion into plane drawings

  • Katheder, Julia
  • Kindermann, Philipp
  • Klute, Fabian Maximilian|||0000-0002-7791-3604
  • Parada Muñoz, Irene María de|||0000-0003-3147-0083
  • Rutter, Ignaz
We introduce the k-Plane Insertion into Plane drawing (k-PIP) problem: given a plane drawing of a planar graph G and a set F of edges, insert the edges in F into the drawing such that the resulting drawing is k-plane. In this paper, we show that the problem is NP-complete for every k = 1, even when G is biconnected and the set F of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that k = 1 and G is a triangulation., Julia Katheder: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 364468267. Fabian Klute: F. K. is supported by a “María Zambrano grant for attracting international talent” and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Ignaz Rutter: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 541433306., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Spanning ratio of shortest paths in weighted square tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path SPw(s, t), which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path SGPw(s, t), which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio kSGPw(s,t)k kSPw(s,t)k is at most v 2 2+v 2 ˜ 1.08, irrespective of the weight assignment., P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is funded by an FPU of the Universidad de Alcalá., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Shortest paths in portalgons

  • Löffler, M.
  • Ophelders, Tim
  • Silveira, Rodrigo Ignacio|||0000-0003-0202-4543
  • 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., Tim Ophelders: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Rodrigo I. Silveira: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Some results on the laplacian spectra of Token graphs

  • Dalfó Simó, Cristina|||0000-0002-8438-9353
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel|||0000-0003-1337-4952
  • Huemer, Clemens|||0000-0001-7557-0823
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
This version of the contribution has been accepted for publication, after peer review 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/978-3-030-83823-2_11. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use http://www.spingernature.com/gp/open-research/policies/accepted-manuscript-terms., We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this work, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1=h=k=n2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G) . Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G¯¯¯¯ . This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs., The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by PID2019-104129GBI00/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. F. J. Zaragoza Mart´ınez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

The complexity of geodesic spanners using Steiner points

  • de Berg, Sarita
  • Ophelders, Tim
  • Parada Muñoz, Irene María de
  • Staals, Frank
  • Wulms, Jules
A geometric t-spanner G on a set S of n point sites in a metric space P is a subgraph of the complete graph on S such that for every pair of sites p,q the distance in G is a most t times the distance d(p,q) in P. We call a connection between two sites a link. In some settings, such as when P is a simple polygon with m vertices and a link is a shortest path in P, links can consist of T(m) segments and thus have non-constant complexity. The spanner complexity is a measure of how compact a spanner is, which is equal to the sum of the complexities of all links in the spanner. In this paper, we study what happens if we are allowed to introduce k Steiner points to reduce the spanner complexity. We study such Steiner spanners in simple polygons, polygonal domains, and edge-weighted trees. Surprisingly, we show that Steiner points have only limited utility. For a spanner that uses k Steiner points, we provide an ¿(nm/k) lower bound on the worst-case complexity of any (3 - e)spanner, and an ¿(mn1/(t+1)/k1/(t+1)) lower bound on the worst-case complexity of any (t - e)spanner, for any constant e ¿ (0,1) and integer constant t = 2. These lower bounds hold in all settings. Additionally, we show NP-hardness for the problem of deciding whether a set of sites in a polygonal domain admits a 3-spanner with a given maximum complexity using k Steiner points. On the positive side, for trees we show how to build a 2t-spanner that uses k Steiner points of complexity O(mn1/t/k1/t + nlog(n/k)), for any integer t = 1. We generalize this result to forests, and apply it to obtain a 2v2t-spanner in a simple polygon with total complexity O(mn1/t(logk)1+1/t/k1/t + nlog2 n). When a link in the spanner can be any path between two sites, we show how to improve the spanning ratio in a simple polygon to (2k + e), for any constant e ¿(0,2k), and how to build a 6t-spanner in a polygonal domain with the same complexity., Tim Ophelders: partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Shortest coordinated motion for square robots

  • Esteban Pascual, Guillermo
  • Halperin, Dan
  • Ruíz, Víctor
  • Sacristán Adinolfi, Vera
  • 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, 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. We present an adaptation of the tools developed for the case of discs by Kirkpatrick and Liu [Characterizing minimum-length coordinated motions for two discs. Proceedings 28th CCCG, 252-259, 2016; CoRR abs/1607.04005, 2016.] to the case of squares. Certain aspects of the case of squares are more complicated, requiring additional and more involved arguments over the case of discs. Our contribution can serve as a basic component in optimizing the coordinated motion of two squares among obstacles, as well as for local planning in sampling-based algorithms, which are often used in practice, in the same setting., Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Some results on the laplacian spectra of Token graphs

  • Dalfó Simó, Cristina
  • Duque, Frank
  • Fabila Monroy, Ruy
  • Fiol Mora, Miquel Àngel
  • Huemer, Clemens
  • Trujillo Negrete, Ana Laura
  • Zaragoza Martínez, Francisco
This version of the contribution has been accepted for publication, after peer review 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/978-3-030-83823-2_11. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use http://www.spingernature.com/gp/open-research/policies/accepted-manuscript-terms., We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this work, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1=h=k=n2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G) . Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G¯¯¯¯ . This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs., The research of C. Dalf´o and M. A. Fiol has been partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalf´o has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by PID2019-104129GBI00/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2017SGR1336. F. J. Zaragoza Mart´ınez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This work has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication 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
Publication Contribución de congreso (ConferenceOutput)

Shortest paths in portalgons

  • Löffler, M.
  • Ophelders, Tim
  • 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., Tim Ophelders: Partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260. Rodrigo I. Silveira: Partially funded by MICINN through project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Continuous mean distance of a weighted graph

  • Garijo Royo, Delia
  • Marquez Pérez, Alberto
  • Silveira, Rodrigo Ignacio
We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances between all pairs of vertices. This parameter provides a natural measure of the compactness of the graph, and has been intensively studied, together with several variants, including its version for weighted graphs. The continuous analog of the (discrete) mean distance is the mean of the distances between all pairs of points on the edges of the graph. Despite being a very natural generalization, to the best of our knowledge this concept has been barely studied, since the jump from discrete to continuous implies having to deal with an infinite number of distances, something that increases the difficulty of the parameter. In this paper, we show that the continuous mean distance of a weighted graph can be computed in time roughly quadratic in the number of edges, by two different methods that apply fundamental concepts in discrete algorithms and computational geometry. We also present structural results that allow for a faster computation of this continuous parameter for several classes of weighted graphs. Finally, we study the relation between the (discrete) mean distance and its continuous counterpart, mainly focusing on the relevant question of convergence when iteratively subdividing the edges of the weighted graph., This work was supported by grants PID2019-104129GB-I00/ AEI/ 10.13039/501100011033, Gen. Cat. 2017SGR1640, and PID2019-103900GB-I00., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Algorithmic geometry with infinite time computation

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

Dynamic embeddings of dynamic single-source upward planar graphs

  • van der Hoog, Ivor
  • Parada Muñoz, Irene María de
  • Rotenberg, Eva
A directed graph G is upward planar if it admits a planar embedding where each edge is y-monotone. Unlike planarity testing, upward planarity testing is NP-hard except in restricted cases, such as when the graph has the single-source property (i.e., each connected component has one source). In this paper, we present a dynamic data structure for maintaining an upward combinatorial embedding -¿E (G) of a single-source upward planar graph subject to edge deletions, edge contractions, directed edge insertions across a face, and single-source-preserving vertex splits through specified corners (i.e., the gaps between pairs of consecutive edges that share a vertex and a face). We furthermore support changes to the embedding -¿E (G) in the form of subgraph flips that mirror or slide the placement of a subgraph that is connected to the rest of the graph via at most two vertices. Updates that are incompatible with the current upward planar embedding are identified and rejected. All update operations are supported as long as the graph remains upward planar. In addition, we support queries that can tell whether two vertices can be connected with a directed edge while the graph remains single-source (we call these uplinkability queries). If a pair of vertices are not uplinkable, we facilitate one-flip-linkable queries: These point to a flip that makes them uplinkable, if any such flip exists. We dynamically maintain a linear-size data structure on G which supports incidence queries between a vertex and a face, and uplinkability queries for vertex pairs. We support all updates and queries in O(log2 n) worst-case time., This research was supported by Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic Network Analysis”. Ivor van der Hoog: This project has additionally received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Eva Rotenberg: This research was additionally supported by Carlsberg Foundation Young Researcher Fellowship CF21-0302 “Graph Algorithms with Geometric Applications”., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On approximating shortest paths in weighted triangular tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
We study the quality of weighted shortest paths when a continuous 2-dimensional space is discretized by a weighted triangular tessellation. In order to evaluate how well the tessellation approximates the 2-dimensional space, we study three types of shortest paths: a weighted shortest path SPw(s,t) , which is a shortest path from s to t in the space; a weighted shortest vertex path SVPw(s,t) , which is a shortest path where the vertices of the path are vertices of the tessellation; and a weighted shortest grid path SGPw(s,t) , which is a shortest path whose edges are edges of the tessellation. The ratios ¿SGPw(s,t)¿¿SPw(s,t)¿ , ¿SVPw(s,t)¿¿SPw(s,t)¿ , ¿SGPw(s,t)¿¿SVPw(s,t)¿ provide estimates on the quality of the approximation. Given any arbitrary weight assignment to the faces of a triangular tessellation, we prove upper and lower bounds on the estimates that are independent of the weight assignment. Our main result is that ¿SGPw(s,t)¿¿SPw(s,t)¿=23v˜1.15 in the worst case, and this is tight., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Graphs attaining the upper bound on the isolation number

  • Lemanska, Magdalena
  • Mora Giné, Mercè
  • Souto Salorio, María josé
A set D of vertices of a graph is isolating if the set of vertices not belonging to D or not having a neighbour in D is independent. The isolation number of a graph G, denoted by ¿(G), is the minimum cardinality of an isolating set. It is known that ¿(G) = n/3 if G is a connected graph of order n, n = 3, different from a cycle of order 5. Moreover, trees attaining this upper bound have been characterized. In this work we characterize all unicyclic and block graphs of order n such that ¿(G) = n/3., Partially supported by projects PID2020-113230RB-C21 and PID2019-104129GBI00/MCIN/AEI/10.13039/501100011033 of the Spanish Ministry of Science and Innovation, and Gen.Cat. DGR2021-SGR-00266., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On k-plane insertion into plane drawings

  • Katheder, Julia
  • Kindermann, Philipp
  • Klute, Fabian Maximilian
  • Parada Muñoz, Irene María de
  • Rutter, Ignaz
We introduce the k-Plane Insertion into Plane drawing (k-PIP) problem: given a plane drawing of a planar graph G and a set F of edges, insert the edges in F into the drawing such that the resulting drawing is k-plane. In this paper, we show that the problem is NP-complete for every k = 1, even when G is biconnected and the set F of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that k = 1 and G is a triangulation., Julia Katheder: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 364468267. Fabian Klute: F. K. is supported by a “María Zambrano grant for attracting international talent” and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Irene Parada: I. P. is a Serra Húnter Fellow. Partially supported by grant 2021UPC-MS-67392 funded by the Spanish Ministry of Universities and the European Union (NextGenerationEU) and by grant PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Ignaz Rutter: Funded by the Deutsche Forschungsgemeinschaft (DFG)– 541433306., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Computing largest minimum color-spanning intervals of imprecise points

  • Acharyya, Ankush
  • Keikha, Vahideh
  • Saumell Mendiola, Maria
  • Silveira, Rodrigo Ignacio
We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval 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 interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in time when , 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., A. Acharyya was supported by the DST-SERB 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 PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033., Peer Reviewed, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Spanning ratio of shortest paths in weighted square tessellations

  • Bose, Prosenjit
  • Esteban Pascual, Guillermo
  • Orden Martin, David
  • Silveira, Rodrigo Ignacio
Continuous 2-dimensional space is often discretized by considering a grid of weighted square cells. In this work we study how well a weighted tessellation approximates the space, with respect to shortest paths. In particular, we consider a shortest path SPw(s, t), which is a shortest path from s to t in the continuous weighted 2D-space, and a shortest grid path SGPw(s, t), which is a shortest path in the tessellated weighted 2D-space. Our main result is that the ratio kSGPw(s,t)k kSPw(s,t)k is at most v 2 2+v 2 ˜ 1.08, irrespective of the weight assignment., P. B. is partially supported by NSERC. G. E., D. O. and R. I. S. are partially supported by H2020-MSCA-RISE project 734922 - CONNECT and project PID2019-104129GB-I00 funded by MCIN/AEI/10.13039/501100011033. G. E. and D. O. are also supported by PIUAH21/IA-062 and CM/JIN/2021-004. G. E. is funded by an FPU of the Universidad de Alcalá., Peer Reviewed, Postprint (author's final draft)
e_Buah Biblioteca Digital Universidad de Alcalá
Publication 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