Search

We prove concentration inequality results for geometric graph properties of an instance of the Cooper–Frieze [5] preferential attachment model withedge-steps. More precisely, we investigate a random graph model that at each time$t\in \mathbb{N}$, with probabilitypadds a new vertex to the graph (avertex-stepoccurs) or with probability$1-p$an edge connecting two existent vertices is added (anedge-stepoccurs). We prove concentration results for theglobal clustering coefficientas well as theclique number. More formally, we prove that the global clustering, with high probability, decays as$t^{-\gamma(p)}$for a positive function$\gamma$ofp, whereas the clique number of these graphs is, up to subpolynomially small factors, of order$t^{(1-p)/(2-p)}$.

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set $$P$$ and a region R belonging to a family $${\mathcal {R}}$$ , we define $$G \cap R$$ to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t $${\mathcal {R}}$$ is a geometric graph G on $$P$$ such that for any region $$R \in {\mathcal {R}}$$ , the graph $$G\cap R$$ is a t-spanner for $$K(P) \cap R$$ , where $$K(P)$$ is the complete geometric graph on P. For any set $$P$$ of n points and any constant $$\varepsilon > 0$$ , we prove that $$P$$ admits local $$(1 + \varepsilon )$$ -spanners of sizes $$O(n \log ^{6} n)$$ and $$O(n \log n)$$ w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local $$(1 + \varepsilon )$$ -spanners with O(n) edges and $$O(n \log ^2 n)$$ edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively.

We give a statement of a multipoint boundary value problem on a geometric graph. The characteristics of the graph admitting such a statement are described. The form of the boundary value problem adjoint to the problem posed is found. An analog of the Keldysh residue theorem is obtained for the Green’s function of the spectral multipoint boundary value problem on the graph.

We classify $n$-dimensional geometric graph manifolds with nonnegative scalar curvature, and first show that if $n>3$, the universal cover splits off a codimension 3 Euclidean factor. We then proceed with the classification of the 3-dimensional case by showing that such a manifold is either a lens space or a prism manifold with a very rigid metric. This allows us to also classify the moduli space of such metrics: it has infinitely many connected components for lens spaces, while it is connected for prism manifolds., 19 pages, 3 figures. Second version with an additional corollary and improved exposition. arXiv admin note: substantial text overlap with arXiv:1611.06572

We study boundary conditions for the diffusion operator defined on a star-shaped geometric graph consisting of three edges with a common vertex. We show that if the edge lengths are pairwise distinct, then there do not exist degenerate boundary conditions for the diffusion operator. If the edge lengths coincide and the potentials are symmetric, then the characteristic determinant of a boundary value problem for the diffusion operator cannot be a constant other than zero, and the set of boundary value problems for which the characteristic determinant is identically zero is infinite (a continuum). We show that, for the diffusion operator on the star-shaped graph, the set of boundary value problems whose spectrum fills the entire plane consists of eighteen classes, each of which contains eight to nine arbitrary constants. Recall that for the diffusion operator defined on an interval this set consists of two problems.

The complete twisted graph of order n, denoted by $$T_n$$ , is a complete simple topological graph with vertices $$u_1, u_2, \ldots , u_n$$ such that two edges $$u_iu_j$$ and $$u_{i'}u_{j'}$$ cross if and only if $$ i

In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required [Formula: see text] state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and, when the algorithm has knowledge of the incoming port (the preceding node on the route), the first stateless local geometric routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions). We also show that [Formula: see text] state bits are necessary in planar subdivisions in which faces may have three or more reflex vertices.

Este documento expresa como la representación escrita en forma analítica de un teorema del conjunto de los números reales, acompañada de un gráfico geométrico, confirma la veracidad y validez de la demostración además de mostrarla de una manera visual.

We study conditions for the solvability of boundary value problems for differential equations of arbitrary order on a geometric graph. The boundary conditions are given by func-tionals that are linear combinations of the one-sided limits of the solution and its derivatives calculated at all graph vertices. The dimensions of the linear spaces of solutions of homogeneous mutually adjoint boundary value problems are proved to be the same. Conditions for the solvability and unique solvability of a degenerate boundary value problem are established. A generalized Green’s function is constructed, its uniqueness is proved, and its properties are described. A theorem on the uniform convergence of the sequence of solutions of the degenerate boundary value problem under the condition of uniform convergence of its right-hand sides is proved.

A geometric graph is called self-approaching, if for each (ordered) pair of vertices of the graph, there exists a self-approaching (directed) path between them. A path from a vertex u to a vertex v of the graph is called self-approaching, if for any point (not just vertex) x on the path, the distance between x and any point that starts at u and moves toward x is decreasing. A path is called an increasing-chord, if it is self-approaching from both sides, source to destination and destination to source. A geometric graph is called a self-approaching t-spanner, for t > 1 , if for each pair ( u , v ) of vertices of the graph, there exists a self-approaching path from u to v of length at most t times the Euclidean distance between u and v. In 2015, Dehkordi et al. (2015) [16] left the problem of the existence of an increasing-chord planar geometric graph for a set of points that lie along the sides of an acute triangle, as an open problem, but they did not mention anything about the case of an obtuse triangle. In this paper, we show that for each set of points on the boundary of an obtuse triangle, there exists an increasing-chord planar geometric graph. Moreover, we show that for each set of points on the boundary of an acute triangle, there exists an increasing-chord planar geometric graph using at most three Steiner points. We also introduce weakly self-approaching geometric graphs (spanners) as a variation of self-approaching geometric graphs (spanners). A weakly self-approaching path is defined similarly to a self-approaching path, except that when a point p on the path moves from the source to the destination, the Euclidean distance between p and the destination vertex (but not all the points on the path) decreases. A weakly self-approaching geometric graph (spanner) is defined by replacing “self-approaching” by “weakly self-approaching” in the above definition. In this paper, we show that for every point set S ⊆ R d , there is a weakly self-approaching planar geometric graph spanning S. Furthermore, this study shows how to test in polynomial time, whether a given geometric graph is weakly self-approaching. Notably, the corresponding decision problem in the context of self-approaching geometric graphs in R d with d ≥ 3 is NP-hard. We also propose some algorithms for constructing a weakly self-approaching geometric t-spanner for a given point set and a real constant t > 1 . Also, we show that for every point set S on the boundary of any triangle, there exists an increasing-chord t-spanner spanning S and a weakly self-approaching t-spanner spanning S, both with O ( k n ) edges, in which k depends only on t.

We study the boundary conditions of the Sturm-Liouville problem posed on a star-shaped geometric graph consisting of three edges with a common vertex. We show that the Sturm-Liouville problem has no degenerate boundary conditions in the case of pairwise distinct edge lengths. However, if the edge lengths coincide and all potentials are the same, then the characteristic determinant of the Sturm-Liouville problem cannot be a nonzero constant and the set of Sturm-Liouville problems whose characteristic determinant is identically zero and whose spectrum accordingly coincides with the entire plane is infinite (a continuum). It is shown that, for one special case of the boundary conditions, this set consists of eighteen classes, each having from two to four arbitrary constants, rather than of two problems as in the case of the Sturm-Liouville problem on an interval.

The boundary conditions of the Sturm–Liouville problem defined on a star-shaped geometric graph of three edges are studied. It is shown that, if the lengths of the edges are different, then the Sturm–Liouville problem does not have degenerate boundary conditions. If the lengths of the edges and the potentials are identical, then the characteristic determinant of the Sturm–Liouville problem cannot be equal to a constant different from zero. However, the set of Sturm–Liouville problems for which the characteristic determinant is identically zero is infinite (continuum). In this way, in contrast to the Sturm–Liouville problem defined on an interval, the set of boundary value problems on a star-shaped graph whose spectrum completely fills the entire plane is much richer. In the particular case when the minor $${{A}_{{124}}}$$ of the coefficient matrix is nonzero, this set consists of not two problems, as in the case of the Sturm–Liouville problem given on an interval, but rather of 18 classes, each containing two to four arbitrary constants.

The inverse Sturm-Liouville problem with nonseparated boundary conditions on a star-shaped geometric graph consisting of three edges with a common vertex is studied. It is shown that the Sturm-Liouville problem with general boundary conditions cannot be reconstructed uniquely from four spectra. A class of nonseparated boundary conditions is obtained for which two uniqueness theorems for the solution of the inverse Sturm-Liouville problem are proved. In the first theorem, the data used to reconstruct the Sturm-Liouville problem are the spectrum of the boundary value problem itself and the spectra of three auxiliary problems with separated boundary conditions. In the second theorem, instead of the spectrum of the problem itself, one only deals with five of its eigenvalues. It is shown that the Sturm-Liouville problem with these nonseparated boundary conditions can be reconstructed uniquely if three spectra of auxiliary problems and five eigenvalues of the problem itself are used as the reconstruction data. Examples of unique reconstruction of potentials and boundary conditions of the Sturm-Liouville problem posed on the graph under study are given.

Suppose [Formula: see text] is a subgraph of a convex complete graph [Formula: see text] and [Formula: see text] contains no boundary edge of [Formula: see text] and [Formula: see text]. We determine necessary and sufficient conditions on [Formula: see text] such that [Formula: see text] admits a triangulation. For [Formula: see text], we investigate the possibility of placing [Formula: see text] in [Formula: see text] such that [Formula: see text] admits a triangulation for certain families of graphs [Formula: see text]. These results are then applied to determine the convex skewness of the convex graphs of the form [Formula: see text].

In this short note, we prove that the degree-three dilation of the square lattice [Formula: see text] is [Formula: see text]. This disproves a conjecture of Dumitrescu and Ghosh. We give a computer-assisted proof of a local-global property for the uncountable set of geometric graphs achieving the optimal dilation.

Temporal graphs are the modeling of pairwise and historical interaction in recordings of a dataset. A temporal matching formalizes the planning of pair working sessions of a required duration. We depict algorithms finding temporal matchings maximizing the total workload, by an exact algorithm and an approximation. The exact algorithm is a dynamic programming solving the general case in \(O^*((\gamma +1)^n)\) time, where n is the number of vertices, \(\gamma \) represents the desired duration of each pair working session, and \(O^*\) only focuses on exponential factors. When the input data is embedded in an Euclidean space, called geometric data, our approximation is based on a new notion of temporal velocity. We revise a known notion of static density [van Leeuwen, 2009] and result in a polynomial time approximation scheme for temporal geometric graphs of bounded density. We confront our implementations to known opensource implementation (Our source code is available at https://github.com/Talessseed/Temporal-matching-of-historical-and-geometric-graphs).

A graph whose vertex set is a set P of points in the plane and whose edges are line segments joining pairs of elements of P is called a geometric graph. In this paper we survey several results on geometric graphs on colored point sets. Of particular interest are bicolored point sets \(P= R \cup B\) in which the elements of P can considered to be colored red or blue. We will pay particular attention to perfect matchings, spanning trees and paths whose vertex sets are colored point sets. In the last section of this paper we give some results on point sets whose elements are labelled with the integers \(\{1, \ldots , n\}\) such that different elements of P receive different labels.

We consider the development of hyperbolic transport models for the propagation in space of an epidemic phenomenon described by a classical compartmental dynamics. The model is based on a kinetic description at discrete velocities of the spatial movement and interactions of a population of susceptible, infected and recovered individuals. Thanks to this, the unphysical feature of instantaneous diffusive effects, which is typical of parabolic models, is removed. In particular, we formally show how such reaction-diffusion models are recovered in an appropriate diffusive limit. The kinetic transport model is therefore considered within a spatial network, characterizing different places such as villages, cities, countries, etc. The transmission conditions in the nodes are analyzed and defined. Finally, the model is solved numerically on the network through a finite-volume IMEX method able to maintain the consistency with the diffusive limit without restrictions due to the scaling parameters. Several numerical tests for simple epidemic network structures are reported and confirm the ability of the model to correctly describe the spread of an epidemic.

International audience; We are given the adjacency matrix of a geometric graph and the task of recovering the latent positions. We study one of the most popular approaches which consists in using the graph distances and derive error bounds under various assumptions on the link function. In the simplest case where the link function is an indicator function, the bound is (nearly) optimal as it (nearly) matches an information lower bound.

In video action recognition based on deep learning, the design of the neural network is focused on how to acquire effective spatial information and motion information quickly. This paper proposes a kind of deep network that can obtain both spatial information and motion information in video classification. It is called MDFs (the multidimensional motion features of deep feature map net). This method can be used to obtain spatial information and motion information in videos only by importing image frame data into a neural network. MDFs originate from the definition of 3D convolution. Multiple 3D convolution kernels with different information focuses are used to act on depth feature maps so as to obtain effective motion information at both spatial and temporal. On the other hand, we split the 3D convolution at space dimension and time dimension, and the spatial network feature map has reduced the dimensions of the original frame image data, which realizes the mitigation of computing resources of the multichannel grouped 3D convolutional network. In order to realize the region weight differentiation of spatial features, a spatial feature weighted pooling layer based on the spatial-temporal motion information guide is introduced to realize the attention to high recognition information. By means of multilevel LSTM, we realize the fusion between global semantic information acquisition and depth features at different levels so that the fully connected layers with rich classification information can provide frame attention mechanism for the spatial information layer. MDFs need only to act on RGB images. Through experiments on three universal experimental datasets of action recognition, UCF10, UCF11, and HMDB51, it is concluded that the MDF network can achieve an accuracy comparable to two streams (RGB and optical flow) that requires the import of both frame data and optical flow data in video classification tasks.

We study graphs that are formed by independently-positioned needles (i.e., line segments) in the unit square. To mathematically characterize the graph structure, we derive the probability that two line segments intersect and determine related quantities such as the distribution of intersections, given a certain number of line segments $N$. We interpret intersections between line segments as nodes and connections between them as edges in a spatial network that we refer to as random-line graph (RLG). Using methods from the study of random-geometric graphs, we show that the probability of RLGs to be connected undergoes a sharp transition if the number of lines exceeds a threshold $N^*$., 7 pages, 4 figures

The chordless cycle sizes of spatially embedded networks are demonstrated to follow an exponential growth law similar to random graphs if the number of nodes N x is below a critical value N * . For covalent polymer networks, increasing the network size, as measured by the number of cross-link nodes, beyond N * results in a crossover to a new regime in which the characteristic size of the chordless cycles h * no longer increases. From this result, the onset and intensity of finite-size effects can be predicted from measurement of h * in large networks. Although such information is largely inaccessible with experiments, the agreement of simulation results from molecular dynamics, Metropolis Monte Carlo, and kinetic Monte Carlo suggests the crossover is a fundamental physical feature which is insensitive to the details of the network generation. These results show random graphs as a promising model to capture structural differences in confined physical networks.

We extend the notion of universal graphs to a geometric setting. A geometric graph is universal for a class H of planar graphs if it contains an embedding, that is, a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) edges that is universal for n -vertex forests; this generalises a well-known result by Chung and Graham, which states that there exists an (abstract) graph with n vertices and O(nlogn) edges that contains every n -vertex forest as a subgraph. The upper bound of O(nlogn) edges cannot be improved, even if more than n vertices are allowed. We also prove that every n -vertex convex geometric graph that is universal for n -vertex outerplanar graphs has a near-quadratic number of edges, namely Ωh(n2−1/h) , for every positive integer h ; this almost matches the trivial O(n2) upper bound given by the n -vertex complete convex geometric graph. Finally, we prove that there exists an n -vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n -vertex caterpillars., Combinatorics, Probability & Computing, ISSN:0963-5483, ISSN:1469-2163

Counting the number of Hamiltonian cycles that are contained in a geometric graph is #P-complete even if the graph is known to be planar. A relaxation for problems in plane geometric graphs is to allow the geometric graphs to be 1-plane, that is, each of its edges is crossed at most once. We consider the following question: For any set P of n points in the plane, how many 1-plane Hamiltonian cycles can be packed into a complete geometric graph Kn? We investigate the problem by taking three different situations of P, namely, when P is in convex position and when P is in wheel configurations position. Finally, for points in general position we prove the lower bound of k - 1 where n = 2k + h and 0 ? h < 2k. In all of the situations, we investigate the constructions of the graphs obtained.

In the present paper, we investigate the initial boundary value problem describing oscillation process on a geometric graph with hysteresis type boundary conditions. The analogue of the d'A...

A geometric graph in the plane is angle-monotone of width \(\gamma \) if every pair of vertices is connected by an angle-monotone path of width \(\gamma \), a path such that the angles of any two edges in the path differ by at most \(\gamma \). Angle-monotone graphs have good spanning properties.

In this paper we study weighted distances in scale-free spatial network models: hyperbolic random graphs (HRG), geometric inhomogeneous random graphs (GIRG) and scale-free percolation (SFP). In HRGs, $n=\Theta(\mathrm{e}^{R/2})$ vertices are sampled independently from the hyperbolic disk with radius $R$ and two vertices are connected either when they are within hyperbolic distance $R$, or independently with a probability depending on the hyperbolic distance. In GIRGs and SFP, each vertex is given an independent weight and location from an underlying measured metric space and $\mathbb{Z}^d$, respectively, and two vertices are connected independently with a probability that is a function of their distance and weights. We assign i.i.d. weights to the edges of the random graphs and study the weighted distance between two uniformly chosen vertices. In SFP, we study the weighted distance from the origin of vertex-sequences with norm tending to infinity. In particular, we study the case when the parameters are so that the degree distribution in the graph follows a power law with exponent $\tau\in(2,3)$ (infinite variance), and the edge-weight distribution is such that it produces an explosive age-dependent branching process with power-law offspring distribution. We show that in all three models, typical distances within the giant/infinite component converge in distribution, solving an open question in [Explosion and distances in scale-free percolation (2017)]. The main tools of our proof are to couple the models to infinite versions, to follow the shortest paths to infinity and to connect these paths using weight-dependent percolation on the graphs: delete edges attached to vertices with higher weight with higher probability. We realise this using the edge-weights: only short edges connected to high weight vertices will stay, yielding arbitrarily short upper bounds for the connections., Comment: 49 pages, 4 figures

We consider a point cloud $$X_n := \{ {\mathbf {x}}_1, \ldots , {\mathbf {x}}_n \}$$ uniformly distributed on the flat torus $${\mathbb {T}}^d : = \mathbb {R}^d / \mathbb {Z}^d $$, and construct a geometric graph on the cloud by connecting points that are within distance $$\varepsilon $$ of each other. We let $${\mathcal {P}}(X_n)$$ be the space of probability measures on $$X_n$$ and endow it with a discrete Wasserstein distance $$W_n$$ as introduced independently in Chow et al. (Arch Ration Mech Anal 203:969–1008, 2012), Maas (J Funct Anal 261:2250–2292, 2011) and Mielke (Nonlinearity 24:1329–1346, 2011) for general finite Markov chains. We show that as long as $$\varepsilon = \varepsilon _n$$ decays towards zero slower than an explicit rate depending on the level of uniformity of $$X_n$$, then the space $$({\mathcal {P}}(X_n), W_n)$$ converges in the Gromov–Hausdorff sense towards the space of probability measures on $${\mathbb {T}}^d$$ endowed with the Wasserstein distance. The analysis presented in this paper is a first step in the study of stability of evolution equations defined over random point clouds as the number of points grows to infinity.

Many machine learning algorithms used for dimensional reduction and manifold learning leverage on the computation of the nearest neighbours to each point of a dataset to perform their tasks. These proximity relations define a so-called geometric graph, where two nodes are linked if they are sufficiently close to each other. Random geometric graphs, where the positions of nodes are randomly generated in a subset of $\mathbb{R}^{d}$, offer a null model to study typical properties of datasets and of machine learning algorithms. Up to now, most of the literature focused on the characterization of low-dimensional random geometric graphs whereas typical datasets of interest in machine learning live in high-dimensional spaces ($d \gg 10^{2}$). In this work, we consider the infinite dimensions limit of hard and soft random geometric graphs and we show how to compute the average number of subgraphs of given finite size $k$, e.g. the average number of $k$-cliques. This analysis highlights that local observables display different behaviors depending on the chosen ensemble: soft random geometric graphs with continuous activation functions converge to the naive infinite dimensional limit provided by Erd\"os-R\'enyi graphs, whereas hard random geometric graphs can show systematic deviations from it. We present numerical evidence that our analytical insights, exact in infinite dimensions, provide a good approximation also for dimension $d\gtrsim10$.

The concept of an Ω-weakly regular problem is introduced. On the basis of the Zhuravlev operator approach combined with the neural network paradigm, it is shown that, for each such problem, a correct algorithm and a six-level spatial neural network reproducing the computations executed by this algorithm can be constructed. Moreover, the set of Ω-weakly regular problems includes the set of Ω-regular problems. It turns out that a three-level spatial network (μ-block) is a forward propagation network whose inner loop under estimation of the class membership for each test object consists of a single iteration. As a result, the amount of computations required for the six-level network is reduced noticeably.

Here we develop an epidemic model that accounts for long-range dispersal of pathogens between plants. This model generalizes the classical compartmental models–Susceptible-Infected-Susceptible (SIS) and Susceptible-Infected-Recovered (SIR)–to take into account those factors that are key to understand epidemics in real plant populations. These ingredients are the spatial characteristics of the plots and fields in which plants are embedded and the effect of long-range dispersal of pathogens. The spatial characteristics are included through the use of random rectangular graphs which allow to consider the effects of the elongation of plots and fields, while the long-range dispersal is implemented by considering transformations, such as the Mellin and Laplace transforms, of a generalization of the adjacency matrix of the geometric graph. Our results point out that long-range dispersal favors the propagation of pathogens while the elongation of plant plots increases the epidemic threshold and decreases dramatically the number of affected plants. Interestingly, our model is able of reproducing the existence of patchy regions of infected plants and the absence of a clear propagation front centered in the initial infected plants, as it is observed in real plant epidemics.

Let S be a set of n points in the plane in general position such that the integers 1 , 2 , … , n are assigned to the points bijectively. Set h be an integer with 1 ≤ h n ( n + 1 ) ∕ 2 . In this paper we consider the problem of finding two vertex-disjoint simple geometric paths consisting of all points of S such that the sum of labels of the points in one path is equal to h and the paths have as few crossings as possible. We prove that there exists such a pair of paths with at most two crossings between them.

Many real-world networks, from infrastructure networks to social and communication networks, can be formulated as flow networks. How to realistically measure the transport efficiency of these networks is of fundamental importance. The shortest-path-based efficiency measurement has limitations, as it assumes that flow travels only along those shortest paths. Here, we propose a new metric named current-flow efficiency, in which we calculate the average reciprocal effective resistance between all pairs of nodes in the network. This metric takes the multipath effect into consideration and is more suitable for measuring the efficiency of many real-world flow equilibrium networks. Moreover, this metric can handle a disconnected graph and can thus be used to identify critical nodes and edges from the efficiency-loss perspective. We further analyze how the topological structure affects the current-flow efficiency of networks based on some model and real-world networks. Our results enable a better understanding of flow networks and shed light on the design and improvement of such networks with higher transport efficiency.

Let G = ( V , E ) be an edge weighted geometric graph (not necessarily planar) such that every edge is horizontal or vertical. The weight of an edge u v ∈ E is the L 1 -distance between its endpoints. Let W G ( u , v ) denotes the length of a shortest path between a pair of vertices u and v in G. The graph G is said to be a Manhattan network for a given point set P in the plane if P ⊆ V and ∀ p , q ∈ P , W G ( p , q ) = ‖ p q ‖ 1 . In addition to P, the graph G may also include a set T of Steiner points in its vertex set V. In the Manhattan network problem, the objective is to construct a Manhattan network of small size (the number of Steiner points) for a set of n points. This problem was first considered by Gudmundsson et al. [EuroCG 2007]. They give a construction of a Manhattan network of size Θ ( n log ⁡ n ) for general point sets in the plane. We say a Manhattan network is planar if it has a planar embedding. In this paper, we construct a planar Manhattan network for convex point sets in linear time using O ( n ) Steiner points. We also show that, even for convex point sets, the construction in Gudmundsson et al. [EuroCG 2007] needs Ω ( n log ⁡ n ) Steiner points, and the network may not be planar.

Let P = ( p 1 , … , p n ) be a geometric path in the plane. For a real number 0 γ 180 ° , P is called an angle-monotone path with width γ if there exists a closed wedge of angle γ such that the vector of every edge ( p i , p i + 1 ) of P lies in this wedge. Let G be a geometric graph in the plane. The graph G is called angle-monotone with width γ if there exists an angle-monotone path with width γ between any two vertices. Let γ min be the smallest width such that every set of points in the plane has a plane angle-monotone graph with width γ min . It has been shown that 90 ° γ min ≤ 120 ° . In this paper, we show that γ min = 120 ° . This solves an open problem posed by Bonichon et al. [GD 2016].

A unit disk graph G on a given set P of points in the plane is a geometric graph where an edge exists between two points p , q ∈ P if and only if | p q | ≤ 1 . A spanning subgraph G ′ of G is a k-hop spanner if and only if for every edge p q ∈ G , there is a path between p , q in G ′ with at most k edges. We obtain the following results for unit disk graphs in the plane. (i) Every n-vertex unit disk graph has a 5-hop spanner with at most 5.5n edges. We analyze the family of spanners constructed by Biniaz (2020) and improve the upper bound on the number of edges from 9n to 5.5n. (ii) Using a new construction, we show that every n-vertex unit disk graph has a 3-hop spanner with at most 11n edges. (iii) Every n-vertex unit disk graph has a 2-hop spanner with O ( n log ⁡ n ) edges. This is the first nontrivial construction of 2-hop spanners. (iv) For every sufficiently large positive integer n, there exists a set P of n points on a circle, such that every plane hop spanner on P has hop stretch factor at least 4. Previously, no lower bound greater than 2 was known. (v) For every finite point set on a circle, there exists a plane (i.e., crossing-free) 4-hop spanner. As such, this provides a tight bound for points on a circle. (vi) The maximum degree of k-hop spanners cannot be bounded from above by a function of k for any positive integer k.

The non-stationary linearized Hoff equation is considered in the article. For this equation, a solution is obtained both on the domain and on the geometric graph. For the five-edged graph, the Sturm -- Liouville problem is solved to obtain a numerical solution of the non-stationary linearized Hoff equation on the graph. A numerical method for solving this equation on a graph is described. The graphics for obtained numerical solution are constructed at different instants of time for given values of the equation parameters and functions. The article besides the introduction and the bibliography contains four parts. The first part contains information on abstract non-stationary Sobolev type equations, and solutions for the non-stationary linearized Hoff equation on the domain are constructed. In the second one we consider the Sturm -- Liouville problem on a graph and construct necessary spaces and operators on graphs. In the third one we study the solvability of the non-stationary linearized Hoff equation on the five-edged graph, and finally, in the last part we describe the numerical solution of the equation on the graph and the graphics of these solutions at different instants of time.

This paper is devoted to consideration of a boundary value problem for a system of functional differential equations determined on a geometric graph. The boundary conditions of the problem are determined by the conditions for the connection of the edges of the graph. There is an algorithm that reduces the system of equations on the graph to the system determined on the set Θ of disjoint segments of the real axis. The Azbelev’s W-method is applied to the system determined on the set Θ; what makes it possible to obtain effective conditions for the unique solvability of the original system. An example is given.

Let G be a complete convex geometric graph on 2m vertices, and let F be a family of subgraphs of G. A blocker for F is a set of edges, of smallest possible size, that meets every element of F. In [C. Keller and M. A. Perles, On the smallest sets blocking simple perfect matchings in a convex geometric graph, Israel J. Math. 187 (2012), pp. 465-484], we gave an explicit description of all blockers for the family of simple perfect matchings (SPMs) of G. In this paper we show that the family of simple Hamiltonian paths (SHPs) in G has exactly the same blockers as the family of SPMs. Our argument is rather short, and provides a much simpler proof of the result of [KP12]., Comment: 7 pages, 4 figures

A variety of medical image segmentation problems present significant technical challenges, including heterogeneous pixel intensities, noisy/ill-defined boundaries and irregular shapes with high variability. The strategy of estimating optimal segmentations within a statistical framework that combines image data with priors on anatomical structures promises to address some of these technical challenges. However, methods that rely on local optimization techniques and/or local shape penalties (e.g., smoothness) have been proven to be inadequate for many difficult segmentation problems. These challenging segmentation problems can benefit from the inclusion of global shape priors within a maximum-a-posteriori estimation framework, which biases solutions toward an object class of interest. In this paper, we propose a maximum-a-posteriori formulation that relies on a generative image model by incorporating both local and global shape priors. The proposed method relies on graph cuts as well as a new shape parameters estimation that provides a global updates-based optimization strategy. We demonstrate our approach on synthetic datasets as well as on the left atrial wall segmentation from late-gadolinium enhancement MRI, which has been shown to be effective for identifying myocardial fibrosis in the diagnosis of atrial fibrillation. Experimental results prove the effectiveness of the proposed approach in terms of the average surface distance between extracted surfaces and the corresponding ground-truth, as well as the clinical efficacy of the method in the identification of fibrosis and scars in the atrial wall.

This paper deals with the problem of geometric pattern formation by a group of autonomous agents. The patterns are formed by the trajectories of the agents modelled with single integrator kinematics. To achieve this, a distributed control law, which is an extension of the consensus protocol, is presented. The control law allows the freedom to generate different circular formations or trochoidal curves, for any underlying graph topology, which represents the interaction among the agents. The existence of spanning tree is the only condition that the graph needs to satisfy. The patterns is achieved by manipulating the location of the eigenvalues of the overall system in order to achieve the desired pattern. The patterns are annular which can either be closed or can cover the entire space. The patterns are not only aesthetically appealing but can also be used in civilian applications like search, exploration and surveillance. We validate the control law with various examples that present appealing patterns.

Latest research in the field of fully autonomous driving led to a new control approach based on decentralized control algorithms for macroscopic traffic scenarios. This control approach balances the traffic load (density) within a road network segment of limited area to maximize the vehicle throughput and to avoid traffic jams. However, it is necessary to divide the road network into multiple individual segments of limited area in an appropriate way. Due to the lack of a methodology to locate such locations for limited areas within a road network, this work presents an adopted technique that solves this problem by modelling the road network as spatial network and by using graph centrality indices. The presented method was implemented into a software framework and validated by simulation.

First, we estimate the connectivity properties of a predefined (fixed node locations) spatial network which optimizes a connectivity functional that balances construction and transportation costs. In this case we obtain a Gaussian distribution for the connectivity. However, when we consider these spatial networks in a growing process, we obtain a power law distribution for the connectivity. If the transportation costs in the functional involve the shortest geometrical path, we obtain a scaling exponent γ = 2.5 . However, if the transportation costs in the functional involve just the shortest path, we obtain γ = 2.2 . Both cases may be useful to analyze in some real networks.

© 2021 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 affine invariant 2D triangulation methods. That is, methods that produce the same triangulation for a point set S for any (unknown) affine transformation of S. Our work is based on a method by Nielson (1993) that uses the inverse of the covariance matrix of S to define an affine invariant norm, denoted , and an affine invariant triangulation, denoted . We revisit the -norm from a geometric perspective, and show that can be seen as a standard Delaunay triangulation of a transformed point set based on S. We prove that it retains all of its well-known properties such as being 1-tough, containing a perfect matching, and being a constant spanner of the complete geometric graph of S. We show that the -norm extends to a hierarchy of related geometric structures such as the minimum spanning tree, nearest neighbor graph, Gabriel graph, relative neighborhood graph, and higher order versions of these graphs. In addition, we provide different affine invariant sorting methods of a point set S and of the vertices of a polygon P that can be combined with known algorithms to obtain other affine invariant triangulation methods of S and of P. Our sorting methods provide a novel alternative to computing affine invariant geometric structures that are computationally simpler than using the -norm. In this work we focus on the theoretical part of affine invariant methods and as such do not provide experimental results. P.B. and P.C. were partially supported by NSERC. P.C. was supported by CONACyT and by the Fonds de la Recherche Scientifique-FNRS under Grant n° MISU F 6001 1. R.S. was supported by projects PID2019-104129GB-I00/ AEI/ 10.13039/ 501100011033 and Gen. Cat. 2017-SGR-1640. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922

We study noncrossing geometric graphs and their disjoint compatible geometric matchings. Given a cycle (a polygon) P we want to draw a set of pairwise disjoint straight-line edges with endpoints on the vertices of P so that these new edges neither cross nor contain any edge of the polygon. We prove NP-completeness of deciding whether there is such a perfect matching. For any n-vertex polygon, with \(n\ge 4\), we show that such a matching with \(< n/7\) edges is not maximal, that is, it can be extended by another compatible matching edge. We also construct polygons with maximal compatible matchings with n/7 edges, demonstrating the tightness of this bound. Tight bounds on the size of a minimal maximal compatible matching are also obtained for the families of d-regular geometric graphs for each \(d\in \{0,1,2\}\). Finally we consider a related problem. We prove that it is NP-complete to decide whether a noncrossing geometric graph G admits a set of compatible noncrossing edges such that G together with these edges has minimum degree five .

Let $P$ be a set of $n$ points in the plane in general position. We show that at least $\lfloor n/3\rfloor$ plane spanning trees can be packed into the complete geometric graph on $P$. This improves the previous best known lower bound $\Omega\left(\sqrt{n}\right)$. Towards our proof of this lower bound we show that the center of a set of points, in the $d$-dimensional space in general position, is of dimension either $0$ or $d$.

We investigate spatial random graphs defined on the points of a Poisson process in d-dimensional space, which combine scale-free degree distributions and long-range effects. Every Poisson point is assigned an independent weight. Given the weight and position of the points, we form an edge between any pair of points independently with a probability depending on the two weights of the points and their distance. Preference is given to short edges and connections to vertices with large weights. We characterize the parameter regime where there is a non-trivial percolation phase transition and show that it depends not only on the power-law exponent of the degree distribution but also on a geometric model parameter. We apply this result to characterize robustness of age-based spatial preferential attachment networks.

In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order type of S. We introduce the concept of exit edges, which prevent the order type from changing under continuous motion of vertices. That is, in the geometric graph on S whose edges are the exit edges, in order to change the order type of S, at least one vertex needs to move across an exit edge. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number., Journal of Graph Algorithms and Applications, 24 (4), ISSN:1526-1719

International audience; The eccentricity of a node v in a network is the maximum distance from v to any other node. In social networks, the reciprocal of eccentricity is used as a measure of importance of nodes in the network. Our work focuses on networks with prescribed structural properties, such as the number of nodes, the number of edges or the maximum degree. Specifically, we determine the maximum value of eccentricity centralization and (some) optimal networks for the families of bipartite networks with given partition sizes, networks with fixed maximum degree and fixed number of edges, tree networks with fixed maximum degree and fixed number of vertices, and networks with fixed number of nodes or edges. As a by-product, we introduce and study a new way of enumerating the nodes of a tree, which might be of independent interest.