اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
111
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 triangula
tion 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.
In an $mathsf{L}$-embedding of a graph, each vertex is represented by an $mathsf{L}$-segment, and two segments intersect each other if and only if the corresponding vertices are adjacent in the graph. If the corner of each $mathsf{L}$-segment in an $
mathsf{L}$-embedding lies on a straight line, we call it a monotone $mathsf{L}$-embedding. In this paper we give a full characterization of monotone $mathsf{L}$-embeddings by introducing a new class of graphs which we call non-jumping graphs. We show that a graph admits a monotone $mathsf{L}$-embedding if and only if the graph is a non-jumping graph. Further, we show that outerplanar graphs, convex bipartite graphs, interval graphs, 3-leaf power graphs, and complete graphs are subclasses of non-jumping graphs. Finally, we show that distance-hereditary graphs and $k$-leaf power graphs ($kle 4$) admit $mathsf{L}$-embeddings.
A emph{Stick graph} is an intersection graph of axis-aligned segments such that the left end-points of the horizontal segments and the bottom end-points of the vertical segments lie on a `ground line, a line with slope $-1$. It is an open question to
decide in polynomial time whether a given bipartite graph $G$ with bipartition $Acup B$ has a Stick representation where the vertices in $A$ and $B$ correspond to horizontal and vertical segments, respectively. We prove that $G$ has a Stick representation if and only if there are orderings of $A$ and $B$ such that $G$s bipartite adjacency matrix with rows $A$ and columns $B$ excludes three small `forbidden submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of $A$ and $B$ permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of $A$ is given, we present an $O(|A|^3|B|^3)$-time algorithm. When neither ordering is given, we present some partial results about graphs that are, or are not, Stick representable.
We study online routing algorithms on the $Theta$6-graph and the half-$Theta$6-graph (which is equivalent to a variant of the Delaunay triangulation). Given a source vertex s and a target vertex t in the $Theta$6-graph (resp. half-$Theta$6-graph), th
ere exists a deterministic online routing algorithm that finds a path from s to t whose length is at most 2 st (resp. 2.89 st) which is optimal in the worst case [Bose et al., siam J. on Computing, 44(6)]. We propose alternative, slightly simpler routing algorithms that are optimal in the worst case and for which we provide an analysis of the average routing ratio for the $Theta$6-graph and half-$Theta$6-graph defined on a Poisson point process. For the $Theta$6-graph, our online routing algorithm has an expected routing ratio of 1.161 (when s and t random) and a maximum expected routing ratio of 1.22 (maximum for fixed s and t where all other points are random), much better than the worst-case routing ratio of 2. For the half-$Theta$6-graph, our memoryless online routing algorithm has an expected routing ratio of 1.43 and a maximum expected routing ratio of 1.58. Our online routing algorithm that uses a constant amount of additional memory has an expected routing ratio of 1.34 and a maximum expected routing ratio of 1.40. The additional memory is only used to remember the coordinates of the starting point of the route. Both of these algorithms have an expected routing ratio that is much better than their worst-case routing ratio of 2.89.
An $S$-hypersimplex for $S subseteq {0,1, dots,d}$ is the convex hull of all $0/1$-vectors of length $d$ with coordinate sum in $S$. These polytopes generalize the classical hypersimplices as well as cubes, crosspolytopes, and halfcubes. In this pape
r we study faces and dissections of $S$-hypersimplices. Moreover, we show that monotone path polytopes of $S$-hypersimplices yield all types of multipermutahedra. In analogy to cubes, we also show that the number of simplices in a pulling triangulation of a halfcube is independent of the pulling order.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
