Search

© 2024 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, Let R and B be two point sets in the plane with . Let be a perfect matching that matches points of R with points of B and maximizes , the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point o of the plane (the center of ) such that for all ., P. P-L. was partially supported by project DICYT 042332PL Vicerrector´ıa de Investigaci´on, Desarrollo e Innovaci´on USACH (Chile). C. S. was supported by Project PID2019-104129GB-I00/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation., Peer Reviewed, Postprint (published version)

© 2024 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, A set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by , is the minimum cardinality of an isolating set of G. It is known that , if G is a connected graph of order n, , distinct from . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number equal to . Moreover, we provide a family of general graphs attaining this upper bound on the isolation number., Award-winning, Postprint (author's final draft)

F. Klute was supported by the Netherlands Organisation for Scientific Research (NWO) project no. 612.001.651 and the Austrian Science Foundation (FWF) grant J4510. I. Parada was supported by the Margarita Salas Fellowship 2021UPC‐MS‐67392 funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). F. Klute and I. Parada were supported by grant PID2019104129GB‐I00 funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (published version)

Let $S$ be a set of $n$ points in general position in $\mathbb{R}^d$. The order-$k$ Voronoi diagram of $S$, $V_k(S)$, is a subdivision of $\mathbb{R}^d$ 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$ by using ratios of volumes of the intersection of cells of $V_2(S)$ and the cell of $Q$ in $V_1(S)$. 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., This research has been supported by projects 2021SGR00266 and PID2019-104129GB-I00/MCIN/ AEI/ 10.13039/501100011033., Award-winning, Postprint (published version)

The version of record of this article, first published in Journal of global optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10898-024-01402-3, Let P be a set of n points in R3 in general position, and let RCH(P) be the rectilinear convex hull of P. In this paper we obtain an optimal O(n log n) time and O(n) space algorithm to compute RCH(P). We also obtain an efficient O(n log2 n) time and O(n log n) space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of P as we rotate R3 around the Z-axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in R3. Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in R3., Pablo Pérez-Lantero: Partially supported by project DICYT 042332PL Vicerrectoría de Investigación Desarrollo e Innovación USACH (Chile). Carlos Seara: Partially supported by project PID2019-104129GB-I00 funded by MICIU/AEI/10.13039/501100011033. Jorge Urrutia: Supported in part by SEP-CONACYT of México, Proyecto 80268, and by PAPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica, UNAM., Peer Reviewed, Postprint (published version)

We use production matrices to count several classes of geometric graphs. We present novel production matrices for non-crossing partitions, connected geometric graphs, and k-angulations, which provide another, simple and elegant, way of counting the number of such objects. Counting geometric graphs is then equivalent to calculating the powers of a production matrix. Applying the technique of Riordan Arrays to these production matrices, we establish new formulas for the numbers of geometric graphs as well as combinatorial identities derived from the production matrices. Further, we obtain the characteristic polynomial and the eigenvectors of such production matrices., This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922. This research is also supported by PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033. C. H. and R. I. S. were supported by MINECO MTM2015-63791-R and Gen. Cat. 2017SGR1336 and 2017SGR1640. G. E. is also funded by an FPU of the Universidad de Alcalá., Postprint (author's final draft)

An antimagic labeling of a connected graph G is a bijection from the set of edges E(G) to {1, 2, . . . , |E(G)|} such that all vertex sums are pairwise distinct, where the vertex sum at vertex v is the sum of the labels assigned to edges incident to v. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic; however the conjecture remains open, even for trees. In this note we prove that trees whose vertices of even degree induce a path are antimagic, extending a result given by Liang, Wong, and Zhu [Anti-magic labeling of trees, Discrete Math. 331 (2014) 9–14]., A. Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR); M. Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT; and C. Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCARISE project 734922-CONNECT., Peer Reviewed, Postprint (published version)

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)

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)

A k-coloring of a graph G is a partition of the vertices of G into k independent sets, which are called colors. A k-coloring is neighbor-locating if any two vertices belonging to the same color can be distinguished from each other by the colors of their respective neighbors. The neighbor-locating chromatic number ¿NL (G) is the minimum cardinality of a neighbor-locating coloring of G. In this paper, we determine the neighbor-locating chromatic number of paths, cycles, fans and wheels. Moreover, a procedure to construct a neighbor-locating coloring of minimum cardinality for these families of graphs is given. We also obtain tight upper bounds on the order of trees and unicyclic graphs in terms of the neighbor-locating chromatic number. Further partial results for trees are also established., Peer Reviewed, Postprint (published version)

For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least Cn/2 different plane perfect matchings, where Cn/2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k=164n2-3532nn--v+122564n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 572n2-n4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k=0,1,2 , and maximize the number of perfect matchings with (n/22) crossings and with (n/22)-1 crossings., Research on this work was initiated at the 16th European Research Week on Geometric Graphs which was held from November 18 to 22, 2019, near Strobl (Austria). We thank all participants for the good atmosphere as well as for discussions on the topic. Further, we thank Clemens Huemer for bringing this problem to our attention in the course of a meeting of the H2020-MSCA-RISE Project 734922 - CONNECT. O. A. and R. P. supported by FWF Grant W1230. P. S. supported by ERC Grant ERC StG 716424-CASe. D. P., I. P., and B. V. supported by FWF Project I 3340-N35. I. P. supported by the Independent Research Fund Denmark Grant 2020-2023 (9131-00044B) “Dynamic Network Analysis” and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU)., Peer Reviewed, Postprint (published version)

Three polynomials are defined for sets S of n points in general position in the plane: The Voronoi polynomial with coefficients the numbers of vertices of the order-k Voronoi diagrams of S, the circle polynomial with coefficients the numbers of circles through three points of S enclosing k points, and the E=k polynomial with coefficients the numbers of (at most k)-edges of S. We present several formulas for the rectilinear crossing number of S in terms of these polynomials and their roots. We also prove that the roots of the Voronoi polynomial lie on the unit circle if and only if S is in convex position. Further, we present bounds on the location of the roots of these polynomials., Postprint (published version)

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least is NP-hard. Further we present some special graphs and their total angular resolution., Peer Reviewed, Postprint (published version)

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)

In a given set S of n points in the plane, how close are four points of S to be cocircular? We define several measures to study this question, and present bounds on this almost-cocircularity in a point set. Algorithms for cocircularity are presented as well., Peer Reviewed, Postprint (published version)

The version of record of this article, first published in Results in Mathematics, is available online at Publisher’s website: http://dx.doi.org/10.1007/s00025-023-01902-w, 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., Peer Reviewed, Postprint (published version)

En este trabajo estudiamos la dimensión métrica y la dimensión métrica tolerante en grafos periplanos maximales. Concretamente, damos cotas ajustadas de ambos parámetros y caracterizamos los grafos que alcanzan las cotas inferiores., Postprint (author's final draft)

The version of record is available online at: http://dx.doi.org/10.1007/s40840-023-01582-3, The metric representation of a vertex u in a connected graph G respect to an ordered vertex subset is the vector of distances . A vertex subset W is a resolving set of G if , for every with . Thus, a resolving set with n elements provides a set of metric representation vectors with cardinal equal to the order of the graph. In this paper, we address the reverse point of view; that is, we characterize the finite subsets that are realizable as the set of metric representation vectors of a graph G with respect to some resolving set W. We also explore the role that the strong product of paths plays in this context. Moreover, in the case , we characterize the sets that are uniquely realizable as the set of metric representation vectors of a graph G with respect to a resolving set W., This work was partially supported by the grants of the Spanish Ministry of Science and Innovation PID2021-123278OB-I00 and PID2019-104129GB-I00, both funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, and Gen. Cat. DGR 2021-SGR-00266., Peer Reviewed, Postprint (author's final draft)

The version of record of this article, first published in Journal of Combinatorial Optimization, is available online at Publisher’s website: http://dx.doi.org/10.1007/s10878-023-01010-z, Given n > 0, let S ¿ [0,1]2 be a set of n points, chosen uniformly at random. Let R¿B be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed axis-aligned rectangles that cover exactly two points of S of the same color, and is strong in the sense that all of its rectangles are pairwise disjoint. We prove that almost surely M(n) = 0.83n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm that runs over the random point set as a Markov chain., Author Corujo was supported by grants from the Université Paris-Dauphine (France) and the ITI IRMIA++. Author Flores-Peñaloza was supported by project PAPIIT IN120520 (UNAM, Mexico). Author Huemer was supported by projects PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033 and Gen. Cat. DGR 2021-SGR-00266. Author Pérez-Lantero was supported by projects CONICYT FONDECYT/Regular 1160543 (Chile), DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Author Seara was supported by project PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/ 501100011033 and Gen. Cat. DGR 2021-SGR-00266., Postprint (author's final draft)

Huemer et al. (Discrete Math., 2019) proved that for any two point sets R and B with |R| = |B|, the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. In this work we study the perfect matching that maximizes the total Euclidean distance. First, we prove that this setting does not always ensure the common intersection property of the disks. Second, we extend the study for sets of 2n uncolored points. As the main result, we prove that in this case all disks of the matching do have a common point., Postprint (published version)

Postprint (published version)

We present an edge labeling of order-k Voronoi diagrams, Vk(S), of point sets S in the plane, and study properties of the regions defined by them. Among them, we show that Vk(S) has a small orientable cycle and path double cover, and we identify configurations that cannot appear in V3(S)., Postprint (published version)

We prove that every set of n red and n blue points in the plane contains a red and a blue point such that every circle through them encloses at least points of the set. This is a two-colored version of a problem posed by Neumann-Lara and Urrutia. We also show that every set S of n points contains two points such that every circle passing through them encloses at most points of S. The proofs make use of properties of higher order Voronoi diagrams, in the spirit of the work of Edelsbrunner, Hasan, Seidel and Shen on this topic. Closely related, we also study the number of collinear edges in higher order Voronoi diagrams and present several constructions., Peer Reviewed, Postprint (author's final draft)

A total dominating set of a graph is a subset of such that every vertex in is adjacent to at least one vertex in . The total domination number of , denoted by , is the minimum cardinality of a total dominating set of . A near-triangulation is a biconnected planar graph that admits a plane embedding such that all of its faces are triangles except possibly the outer face. We show in this paper that for any near-triangulation of order , with two exceptions., Peer Reviewed, Postprint (author's final draft)

An antimagic labeling of a graph G is a bijection from the set of edges E(G) to {1,2,…,|E(G)|}, such that all vertex sums are pairwise distinct, where the vertex sum at vertex u is the sum of the labels assigned to the edges incident to u. A graph is called antimagic when it has an antimagic labeling. Hartsfield and Ringel conjectured that every simple connected graph other than K2 is antimagic and the conjecture remains open even for trees. Here, we prove that caterpillars are antimagic by means of an O(nlogn) algorithm., Antoni Lozano is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR). Mercè Mora is supported by projects Gen. Cat. DGR 2017SGR1336, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Carlos Seara is supported by projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and H2020-MSCA-RISE project 734922-CONNECT. Joaquin Tey is supported by project PRODEP-12612731., Peer Reviewed, Postprint (author's final draft)

In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if ß(G) denotes the metric dimension of a maximal outerplanar graph G of order n, we prove that 2=ß(G)=¿2n5¿ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of G is 2 and to build a resolving set S of size ¿2n5¿ for G. Moreover, we characterize all maximal outerplanar graphs with metric dimension 2., Peer Reviewed, Postprint (author's final draft)

Let S[0,1]2 be a set of n points, randomly and uniformly selected. Let RB be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely M(n)=0.83n for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain., Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640, Postprint (author's final draft)

Preprint

For a given set of points U on a sphere S, the order k spherical Voronoi diagram SVk(U) decomposes the surface of S into regions whose points have the same k nearest points of U. We study properties for SVk(U), using different tools: the geometry of the sphere, a labeling for the edges of SVk(U), and the inversion transformation. Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct SV1(U). We generalize their construction for spherical Voronoi diagrams from order 1 to any order k. We use that construction to prove formulas for the numbers of vertices, edges, and faces in SVk(U). Among the properties of SVk(U), we also show that SVk(U) has a small orientable cycle double cover., Peer Reviewed, Postprint (published version)

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)

For a given set of points U on a sphere S, the order k spherical Voronoi diagram SV_k(U) decomposes the surface of S into regions whose points have the same k nearest points of U. We study properties for SV_k(U), using different tools: the geometry of the sphere, a labeling for the edges of SV_k(U), and the inversion transformation. Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct SV_1(U). We generalize their construction for spherical Voronoi diagrams from order 1 to any order k. We use that construction to prove formulas for the numbers of vertices, edges, and faces in SV_k(U). Among the properties of SV_k(U), we also show that SV_k(U) has a small orientable cycle double cover., Postprint (published version)

A subset S of vertices of a connected graph G is a distance-equalizer set if for every two distinct vertices x,y¿V(G)\S there is a vertex w¿S such that the distances from x and y to w are the same. The equidistant dimension of G is the minimum cardinality of a distance-equalizer set of G. This paper is devoted to introduce this parameter and explore its properties and applications to other mathematical problems, not necessarily in the context of graph theory. Concretely, we first establish some bounds concerning the order, the maximum degree, the clique number, and the independence number, and characterize all graphs attaining some extremal values. We then study the equidistant dimension of several families of graphs (complete and complete multipartite graphs, bistars, paths, cycles, and Johnson graphs), proving that, in the case of paths and cycles, this parameter is related to 3-AP-free sets. Subsequently, we show the usefulness of distance-equalizer sets for constructing doubly resolving sets., Peer Reviewed, Postprint (published version)

The version of record of this article, first published in Discrete & Computational Geometry, is available online at Publisher’s website: https://doi.org/10.1007/s00454-022-00395-8, Let S be a set of n points in general position in the plane, and let Xk,(S) be the number of convex k-gons with vertices in S that have exactly points of S in their interior. We prove several equalities for the numbers Xk,(S). This problem is related to the Erd¿os–Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well., Research of C.H. was partially supported by project MTM2015-63791-R (MINECO/ FEDER), PID-2019-104129GB-I00/MCIN/AEI/10.13039/501100011033, and by project Gen. Cat. DGR 2017SGR1336. D.O. was partially supported by project PAPIIT IG100721 and CONACyT 282280. P. P-L. was partially supported by project DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. Research of B.V. was partially supported by the Austrian Science Fund (FWF) within the collaborative DACH project Arrangements and Drawings as FWF Project I 3340-N35. We thank an anonymous referee for helpful comments. This project has been supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922, Postprint (author's final draft)

Huemer et al. (Discrete Mathematics, 2019) proved that for any two point sets R and B with |R|=|B| , the perfect matching that matches points of R with points of B, and maximizes the total squared Euclidean distance of the matched pairs, has the property that all the disks induced by the matching have a common point. Each pair of matched points p¿R and q¿B induces the disk of smallest diameter that covers p and q. Following this research line, in this paper we consider the perfect matching that maximizes the total Euclidean distance. First, we prove that this new matching for R and B does not always ensure the common intersection property of the disks. Second, we extend the study of this new matching for sets of 2n uncolored points in the plane, where a matching is just a partition of the points into n pairs. As the main result, we prove that in this case all disks of the matching do have a common point., We thank the GeoGebra open source software and its developers [17]. S. B. was supported in part by NSF award CCF-1718994. D. F-P. was partially supported by PAPIIT IN120520 (UNAM, Mexico). C. H. and C. S. were partially supported by project MICINN 2020-2024 PID2019-104129GB-I00/ MCIN/ AEI/ 10.13039/501100011033. P. P-L. was partially supported by projects DICYT 041933PL Vicerrectoría de Investigación, Desarrollo e Innovación USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02., Postprint (published version)

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)

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)

The version of record is available online at: http://dx.doi.org/10.1007/s00009-022-02096-1, An ordered set S of vertices of a graph G is a resolving set for G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set. In this paper we study resolving sets tolerant to several failures in three-dimensional grids. Concretely, we seek for minimum cardinality sets that are resolving after removing any k vertices from the set. This is equivalent to finding (k+1)-resolving sets, a generalization of resolving sets, where, for every pair of vertices, the vector of distances to the vertices of the set differs in at least k + 1 coordinates. This problem is also related with the study of the (k+1)-metric dimension of a graph, defined as the minimum cardinality of a (k + 1)-resolving set. In this work, we first prove that the metric dimension of a three-dimensional grid is 3 and establish some properties involving resolving sets in these graphs. Secondly, we determine the values of k = 1 for which there exists a (k + 1)-resolving set and construct such a resolving set of minimum cardinality in almost all cases., This project 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)