ML p(r)ior | The Price of Order

### The Price of Order

2016-02-01
1602.00399 | cs.CG
We present tight bounds on the spanning ratio of a large family of ordered $\theta$-graphs. A $\theta$-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $\theta = 2 \pi/m$. An ordered $\theta$-graph is constructed by inserting the vertices one by one and connecting each vertex to the closest previously-inserted vertex in each cone. We show that for any integer $k \geq 1$, ordered $\theta$-graphs with $4k + 4$ cones have a tight spanning ratio of $1 + 2 \sin(\theta/2) / (\cos(\theta/2) - \sin(\theta/2))$. We also show that for any integer $k \geq 2$, ordered $\theta$-graphs with $4k + 2$ cones have a tight spanning ratio of $1 / (1 - 2 \sin(\theta/2))$. We provide lower bounds for ordered $\theta$-graphs with $4k + 3$ and $4k + 5$ cones. For ordered $\theta$-graphs with $4k + 2$ and $4k + 5$ cones these lower bounds are strictly greater than the worst case spanning ratios of their unordered counterparts. These are the first results showing that ordered $\theta$-graphs have worse spanning ratios than unordered $\theta$-graphs. Finally, we show that, unlike their unordered counterparts, the ordered $\theta$-graphs with 4, 5, and 6 cones are not spanners.

Highlights - Most important sentences from the article

# Related Articles

2019-05-06
1905.01921 | cs.DM

A graph $G$ is \emph{nonsingular (singular)} if its adjacency matrix $A(G)$ is nonsingular (singular… show more

Highlights - Most important sentences from the article

2019-03-25
1903.10087 | math.CO

The cop throttling number $th_c(G)$ of a graph $G$ for the game of Cops and Robbers is the minimum o… show more

Highlights - Most important sentences from the article

2017-05-27
1705.09797 | cs.DM

Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,… show more Highlights - Most important sentences from the article 2019-05-08 1905.06895 | cs.DS We show that the graph transformation problem of turning a simple graph into an Eulerian one by a mi… show more Highlights - Most important sentences from the article 2014-01-09 1401.2127 | cs.CG We present improved upper bounds on the spanning ratio of constrained$\theta$-graphs with at least … show more Highlights - Most important sentences from the article 2019-02-13 1902.04828 | math.CO In this paper, we generalize the concept of complete coloring and achromatic number to 2-edge-colore… show more Highlights - Most important sentences from the article 2018-12-08 1812.03250 | cs.DM Given a graph$G=(V,E)$and a set$S_0\subseteq V$, an irreversible$k$-threshold conversion process… show more Highlights - Most important sentences from the article 2019-01-06 1901.01476 | cs.CG$\Theta_6$-Graphs graphs are important geometric graphs that have many applications especially in wi… show more Highlights - Most important sentences from the article 2019-03-13 1903.05363 | cs.CG We study$c$-crossing-critical graphs, which are the minimal graphs that require at least$c$edge-c… show more Highlights - Most important sentences from the article 2018-11-09 1811.04801 | cs.DM The$k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorph… show more Highlights - Most important sentences from the article 2018-10-16 1810.06872 | cs.CC A semitotal dominating set of a graph$G$with no isolated vertex is a dominating set$D$of$G$suc… show more Highlights - Most important sentences from the article 2016-08-26 1608.07413 | cs.DM A \emph{long unichord} in a graph is an edge that is the unique chord of some cycle of length at lea… show more Highlights - Most important sentences from the article 2017-04-07 1704.02237 | cs.CC Given a graph$F$, let$I(F)$be the class of graphs containing$F$as an induced subgraph. Let$W[F… show more

Highlights - Most important sentences from the article

2018-08-03
1808.01298 | cs.CG

We present a routing algorithm for the Theta-4-graph that computes a path between any two vertices s… show more

Highlights - Most important sentences from the article

2018-10-10
1810.04379 | cs.DS

A graph is $H$-free if it does not contain an induced subgraph isomorphic to $H$. For every integer … show more

Highlights - Most important sentences from the article

2016-06-21
1606.06577 | math.CO

A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is non-hamiltonian, there exists a vertex $w$ in… show more

Highlights - Most important sentences from the article