### 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.

**Login to like/save this paper, take notes and configure your recommendations**

# 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

**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

**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

**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

**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

**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

**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

**2019-01-06**

1901.01476 | cs.CG

$\Theta_6$-Graphs graphs are important geometric graphs that have many
applications especially in wi… show more

**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

**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

**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

**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

**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

**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

**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

**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