ML p(r)ior | The Price of Order

The Price of Order

2016-02-01
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-05-06

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

Highlights - Most important sentences from the article

2019-03-25

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

Highlights - Most important sentences from the article

2017-05-27

Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,… show more
PDF

Highlights - Most important sentences from the article

2019-05-08

We show that the graph transformation problem of turning a simple graph into an Eulerian one by a mi… show more
PDF

Highlights - Most important sentences from the article

2014-01-09

We present improved upper bounds on the spanning ratio of constrained $\theta$-graphs with at least … show more
PDF

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
PDF

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
PDF

Highlights - Most important sentences from the article

2019-01-06

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

Highlights - Most important sentences from the article

2019-03-13

We study $c$-crossing-critical graphs, which are the minimal graphs that require at least $c$ edge-c… show more
PDF

Highlights - Most important sentences from the article

2018-11-09

The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorph… show more
PDF

Highlights - Most important sentences from the article

2018-10-16

A semitotal dominating set of a graph $G$ with no isolated vertex is a dominating set $D$ of $G$ suc… show more
PDF

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
PDF

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
PDF

Highlights - Most important sentences from the article

2018-08-03

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

Highlights - Most important sentences from the article

2018-10-10

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

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
PDF

Highlights - Most important sentences from the article