Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal Routing in Sparse and Lightweight Geometric Graphs
317
0
0.0
(
0
)
Added by
Andr\\'e van Renssen
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$-competitive. However, a Delaunay triangulation can have $Omega(n)$ vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set $V$ of $n$ points in the Euclidean plane, of a planar geometric graph on $V$ that has small weight (within a constant factor of the weight of a minimum spanning tree on $V$), constant degree, and that admits a local routing strategy that is $O(1)$-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an $O(1)$-competitive routing strategy.
rate research
Read More
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is $x$- and $y$-monotone. Angle-monotone graphs are $sqrt 2$-spanners and they are increasing-chord graphs. Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are angle-monotone graphs. We give a polynomial time algorithm to recognize angle-monotone geometric graphs. We prove that every point set has a plane geometric graph that is generalized angle-monotone---specifically, we prove that the half-$theta_6$-graph is generalized angle-monotone. We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex $s$ to any vertex $t$ whose length is within $1 + sqrt 2$ times the Euclidean distance from $s$ to $t$. Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
Random graphs are mathematical models that have applications in a wide range of domains. We study the following model where one adds ErdH{o}s--Renyi (ER) type perturbation to a random geometric graph. More precisely, assume $G_mathcal{X}^{*}$ is a random geometric graph sampled from a nice measure on a metric space $mathcal{X} = (X,d)$. The input observed graph $widehat{G}(p,q)$ is generated by removing each existing edge from $G_mathcal{X}^*$ with probability $p$, while inserting each non-existent edge to $G_mathcal{X}^{*}$ with probability $q$. We refer to such random $p$-deletion and $q$-insertion as ER-perturbation. Although these graphs are related to the objects in the continuum percolation theory, our understanding of them is still rather limited. In this paper we consider a localized version of the classical notion of clique number for the aforementioned ER-perturbed random geometric graphs: Specifically, we study the edge clique number for each edge in a graph, defined as the size of the largest clique(s) in the graph containing that edge. The clique number of the graph is simply the largest edge clique number. Interestingly, given a ER-perturbed random geometric graph, we show that the edge clique number presents two fundamentally different types of behaviors, depending on which type of randomness it is generated from. As an application of the above results, we show that by using a filtering process based on the edge clique number, we can recover the shortest-path metric of the random geometric graph $G_mathcal{X}^*$ within a multiplicative factor of $3$, from an ER-perturbed observed graph $widehat{G}(p,q)$, for a significantly wider range of insertion probability $q$ than in previous work.
Let $Vsubsetmathbb{R}^2$ be a set of $n$ sites in the plane. The unit disk graph $DG(V)$ of $V$ is the graph with vertex set $V$ in which two sites $v$ and $w$ are adjacent if and only if their Euclidean distance is at most $1$. We develop a compact routing scheme for $DG(V)$. The routing scheme preprocesses $DG(V)$ by assigning a label $l(v)$ to every site $v$ in $V$. After that, for any two sites $s$ and $t$, the scheme must be able to route a packet from $s$ to $t$ as follows: given the label of a current vertex $r$ (initially, $r=s$) and the label of the target vertex $t$, the scheme determines a neighbor $r$ of $r$. Then, the packet is forwarded to $r$, and the process continues until the packet reaches its desired target $t$. The resulting path between the source $s$ and the target $t$ is called the routing path of $s$ and $t$. The stretch of the routing scheme is the maximum ratio of the total Euclidean length of the routing path and of the shortest path in $DG(V)$, between any two sites $s, t in V$. We show that for any given $varepsilon>0$, we can construct a routing scheme for $DG(V)$ with diameter $D$ that achieves stretch $1+varepsilon$ and label size $O(log Dlog^3n/loglog n)$ (the constant in the $O$-Notation depends on $varepsilon$). In the past, several routing schemes for unit disk graphs have been proposed. Our scheme is the first one to achieve poly-logarithmic label size and arbitrarily small stretch without storing any additional information in the packet.
We study biplane graphs drawn on a finite planar point set $S$ in general position. This is the family of geometric graphs whose vertex set is $S$ and can be decomposed into two plane graphs. We show that two maximal biplane graphs---in the sense that no edge can be added while staying biplane---may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over $n$-element point sets.
Let $mathcal{D}$ be a set of $n$ disks in the plane. The disk graph $G_mathcal{D}$ for $mathcal{D}$ is the undirected graph with vertex set $mathcal{D}$ in which two disks are joined by an edge if and only if they intersect. The directed transmission graph $G^{rightarrow}_mathcal{D}$ for $mathcal{D}$ is the directed graph with vertex set $mathcal{D}$ in which there is an edge from a disk $D_1 in mathcal{D}$ to a disk $D_2 in mathcal{D}$ if and only if $D_1$ contains the center of $D_2$. Given $mathcal{D}$ and two non-intersecting disks $s, t in mathcal{D}$, we show that a minimum $s$-$t$ vertex cut in $G_mathcal{D}$ or in $G^{rightarrow}_mathcal{D}$ can be found in $O(n^{3/2}text{polylog} n)$ expected time. To obtain our result, we combine an algorithm for the maximum flow problem in general graphs with dynamic geometric data structures to manipulate the disks. As an application, we consider the barrier resilience problem in a rectangular domain. In this problem, we have a vertical strip $S$ bounded by two vertical lines, $L_ell$ and $L_r$, and a collection $mathcal{D}$ of disks. Let $a$ be a point in $S$ above all disks of $mathcal{D}$, and let $b$ a point in $S$ below all disks of $mathcal{D}$. The task is to find a curve from $a$ to $b$ that lies in $S$ and that intersects as few disks of $mathcal{D}$ as possible. Using our improved algorithm for minimum cuts in disk graphs, we can solve the barrier resilience problem in $O(n^{3/2}text{polylog} n)$ expected time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
