Approximate Strong Edge-Colouring of Unit Disk Graphs

Abstract

We show that the strong chromatic index of unit disk graphs is efficiently 6-approximable. This improves on 8-approximability as shown by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan [1]. We also show that strong edge-6-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time $(7/6-\varepsilon )$-approximation unless P = NP.

1 Introduction

A strong edge-k -colouring is a partition of the edges of a graph G into k parts so that each part induces a matching (meaning that there exists no edge in G between two edges of the same matching). The strong chromatic index is the least k for which the graph admits a strong edge-k-colouring. If the vertices of the graph represent communicating nodes, say, in a wireless network, then an optimal strong edge-colouring may represent an optimal discrete assignment of frequencies to transmissions in the network so as to avoid both primary and secondary interference [1, 18, 20]. It is then relevant to model the network geometrically, i.e. as a unit disk graph [9]. Our interest is in approximative algorithmic aspects of strong edge-colouring in this model. This was considered by Barrett, Istrate, Kumar, Marathe, Thite, and Thulasidasan [1] who showed that the strong chromatic index of unit disk graphs is efficiently 8-approximable. We revisit the problem and make some further advances.

• We prove efficient 6-approximability.

• We prove an efficient online 8-competitive algorithm.

• We show impossibility of efficient $(7/6-\varepsilon )$-approximability unless P=NP.

It is $\exists \mathbb R$-complete to decide if a given graph has an embedding as a unit disk graph [11], but both of the approximation algorithms we use are robust, in the sense that they efficiently output a valid strong edge-colouring upon the input of any abstract graph. Our contribution is to prove that they are guaranteed to output a colouring with good approximation ratio upon the input of a unit disk graph (regardless of any embedding).

Our work parallels and contrasts with work on the chromatic number of unit disk graphs, for which the best approximation ratio known has stubbornly remained 3 since 1991 [19]. Finding an optimal approximation for strong chromatic index may be similarly difficult.

1.1 Graph Colouring Preliminaries

In this subsection, we highlight some graph theoretic notation, concepts and observations that are relevant to our study. For other standard background, consult e.g. [6]. Given a graph $G = (V,E)$, the minimum degree, clique number, chromatic number and maximum degree of G are denoted by $\delta (G)$, $\omega (G)$, $\chi (G)$ and $\varDelta (G)$, respectively. The degeneracy of G is defined as $\delta ^*(G) = \max \{\delta (H) \,|\, H\subseteq G\}$ and G is called k-degenerate if $\delta ^*(G) \le k$. A simple but useful set of inequalities for graph colouring is as follows. For any graph G,

$$\begin{aligned} \omega (G) \le \chi (G) \le \delta ^*(G)+1 \le \varDelta (G)+1. \end{aligned}$$

(1)

Note that the second inequality in (1) is algorithmic, in the sense that it follows from the use of an efficient greedy algorithm that always assigns the least available colour, provided we consider the vertices one by one in a suitable order, namely, according to degeneracy. Moreover, a greedy algorithm taking any ordering uses at most $\varDelta (G)+1$ colours.

The line graph L(G) of G is the graph where a vertex in L(G) corresponds to an edge in G and there is an edge between two vertices in L(G) if the corresponding edges in G share a vertex. The square $G^2$ of G is the graph formed from G by adding all edges between pairs of vertices that are connected by a 2-edge path in G. The strong chromatic index of G (as defined above) is denoted $\chi _2'(G)$. Note that $\chi _2'(G) = \chi (L(G)^2)$. The strong clique number $\omega _2'(G)$ of G is $\omega (L(G)^2)$. Obviously, (1) implies that

$$\begin{aligned} \omega _2'(G) \le \chi _2'(G) \le \delta ^*(L(G)^2)+1 \le \varDelta (L(G)^2)+1. \end{aligned}$$

(2)

It is worth reiterating that the following greedy algorithm efficiently generates a strong edge-$(\delta ^*(L(G)^2)+1)$-colouring: order the edges of G by repeatedly removing from G an edge e for which $\deg _{L(G)^2}(e)$ is lowest, and then colour the edges sequentially according to the reverse of this ordering, at each step assigning as a colour the least positive integer that does not conflict with previously coloured edges. Again similarly, with an arbitrary ordering of the edges the greedy algorithm produces a strong edge-$(\varDelta (L(G)^2)+1)$-colouring. Our main results then follow from (2) by suitable bounds on $\delta ^*(L(G)^2)$ and $\varDelta (L(G)^2)$.

The strong chromatic index is a well-studied parameter in graph theory. Most notably, Erdős and Nešetřil conjectured in the 1980s that $\chi _2'(G) \le 1.25\varDelta (G)^2$ for all graphs G [7]. About a decade later, Molloy and Reed [17] proved the existence of some minuscule but fixed $\varepsilon >0$ such that $\chi _2'(G) \le (2-\varepsilon )\varDelta (G)^2$ for all graphs G. Recently there have been improvements [2, 3] and extensions [10, 21], but all rely on Molloy and Reed’s original approach, a reduction to a Ramsey-type colouring result. The conjecture remains wide open.

1.2 Unit Disk Graph Preliminaries

A graph $G=(V,E)$ is said to be a unit disk graph if there exists a mapping $p: V\rightarrow {\mathbb R}^2$ from its vertices to the plane such that $uv\in E$ if and only if the Euclidean distance between p(u) and p(v) is at most 1. Any explicit mapping p that certifies that G is a unit disk graph is called an embedding. When we have an embedding p, we often make no distinction between a vertex u and its corresponding point p(u) in the plane.

The class of unit disk graphs is popular due to its elegance and its versatility in capturing real-world optimisation problems [5]. For example, an embedded unit disk graph may represent placement of transceivers so that circles of radius 1/2 centred at the points represent transmission areas. Indeed, the class was originally introduced in 1980 to model frequency assignment [9], with chromatic number being one of the first studied parameters. Clark, Colbourn and Johnson [5] published a proof that it is NP-hard to compute the chromatic number of unit disk graphs. They also showed the clique number of unit disk graphs is polynomial-time computable. Therefore, any upper bound C on the extremal ratio $r := \sup \{\chi (G)/\omega (G) \,|\, G \text { is a unit disk graph}\}$ (algorithmic or not) implies an efficient C-approximation of the chromatic number: simply output $C\cdot \omega (G)$. In 1991, Peeters [19] noted a simple 3-approximation which also shows $r\le 3$: after lexicographically ordering the vertices of G according to any fixed embedding, a basic geometric argument proves that G is $3(\omega (G)-1)$-degenerate (and then apply (1)). Since 3-colourability of unit disk graphs is NP-complete, there is no efficient $(4/3-\varepsilon )$-approximation unless P=NP. It is known that $r\ge 3/2$ [15]. The best approximation ratio known is 3.

1.3 Approximate Strong Edge-Colouring Preliminaries

Mahdian [13, 14] showed in 2000 that it is NP-hard to compute the strong chromatic index, even restricted to bipartite graphs of large fixed girth. More recently, Chalermsook, Laekhanukit and Nanongkai [4] showed that in general there is no polynomial-time $(n^{1/3-\varepsilon })$-approximation algorithm (where n is the number of vertices in the input) unless NP = ZPP.

To the best of our knowledge, no previous work has shown NP-hardness upon restriction to the class of unit disk graphs. Nevertheless, Barrett et al. [1] have initiated the study of approximate strong edge-colouring for unit disk graphs. With an argument similar to in [19], they showed that $\delta ^*(L(G)^2) \le 8 \omega _2'(G)$ for any unit disk graph G, which by (2) certifies an 8-approximation for the strong chromatic index. Kanj, Wiese and Zhang [12] noted an efficient online 10-competitive algorithm with essentially the same analysis as in [1].

1.4 Main Results and Outline

Our work improves significantly on [1] in several ways. In Sect. 2, we describe the following.

Theorem 1

For any unit disk graph G, $\delta ^*(L(G)^2) \le 6 (\omega _2'(G)-1)$.

Corollary 1

The greedy algorithm under a reverse degeneracy ordering of the edges is an efficient 6-approximation for the strong chromatic index of unit disk graphs.

The proof of Theorem 1 is rather involved. It shows that, for any embedded unit disk graph, some well-chosen edge-ordering certifies the required degeneracy bound. It would be very interesting to improve on the approximation ratio of 6. We prove the following in Sect. 3.

Theorem 2

For any unit disk graph G, $\varDelta (L(G)^2) \le 8 (\chi _2'(G)-1)$.

Corollary 2

The greedy algorithm is an efficient online 8-competitive algorithm¹ for the strong chromatic index of unit disk graphs.

The proof of Theorem 2 differs fairly from previous work [1, 12] and from the proof of Theorem 1. Indeed the bound we give make use of the strong chromatic index $\chi _2'(G)$ instead of the strong clique number $\omega _2'(G)$. To prove Theorem 2, it suffices to solve the following kissing number-type problem. Given two intersecting unit disks $C_1$ and $C_2$ in ${\mathbb R}^2$, what is the size of a largest collection of pairwise non-intersecting unit disks such that each one intersects $C_1\,\cup \,C_2$? The corresponding problem in ${\mathbb R}^3$ seems quite natural.

In Appendix, we prove the following.

Theorem 3

Strong edge-k-colourability of unit disk graphs is NP-complete, where $k=6$ or $k=\left( {\begin{array}{c}\ell \\ 2\end{array}}\right) +4\ell +6$ for some fixed $\ell \ge 5$.

Corollary 3

It is NP-hard to compute the strong chromatic index of unit disk graphs. Moreover, it cannot be efficiently $(7/6-\varepsilon )$-approximated unless P=NP.

For $k\le 3$, strong edge-k-colourability is polynomially-time solvable. The complexity for $k \in \{4,5\}$ remains open. The proof of Theorem 3 borrows from ideas in the work of Gräf, Stumpf and Weißenfels [8], but with extra non-trivial difficulties for strong edge-colouring.

1.5 Further Discussion

We can state more general versions of our approximation results that not only lend a more geometric flavour but also highlight a potential conceptual obstacle to further improvements on our approximation results. We call a graph $G=(V,E)$ a twin unit disk graph if there exists a mapping $p: V\rightarrow {\mathbb R}^2\times {\mathbb R}^2, u \mapsto (p(u)_1,p(u)_2)$ from its vertices to pairs of points in the plane such that

• the Euclidean distance between $p(u)_1$ and $p(u)_2$ is at most 1 for every $u\in V$; and

• $uv\in E$ if and only if the Euclidean distance between $p(u)_1$ and $p(v)_1$, between $p(u)_1$ and $p(v)_2$, between $p(u)_2$ and $p(v)_1$, or between $p(u)_2$ and $p(v)_2$ is at most 1.

Equivalently, this is the intersection class over unions of pairs of intersecting unit disks in ${\mathbb R}^2$.

Note that, for any unit disk graph G, both G and $L(G)^2$ are twin unit disk graphs. (Indeed we represent $L(G)^2$ by setting $p(e)_1=p_1$ and $p(e)_2=p_2$ for any edge $e=p_1p_2$ in G.) So it is NP-hard to determine the chromatic number of twin unit disk graphs.

We have the following stronger versions of Theorems 1 and 2, which imply efficient 6-approximation and online 8-competitive algorithms for the chromatic number of twin unit disk graphs (by (1)).

Theorem 4

For any twin unit disk graph G, $\delta ^*(G) \le 6 (\omega (G)-1)$.

Theorem 5

For any twin unit disk graph G, $\varDelta (G) \le 8 (\chi (G)-1)$.

Malesińska et al. [15] showed that there are unit disk graphs G for which $\delta (G) = 3(\omega (G)-1)$. In Appendix, we also show that there are twin unit disk graphs G for which $\delta (G) \ge 4(\omega (G)-2)+1$, and so the factor 6 in Theorem 4 cannot be improved below 4.

If we were able to efficiently compute or well approximate the clique number of twin unit disk graphs or, in particular, the strong clique number of unit disk graphs, then we would have a strong incentive to bound $r_2' := \sup \{\chi _2'(G)/\omega _2'(G) \,|\, G \text { is a unit disk graph}\}.$ This is a natural optimisation problem regardless. We only know $r_2' \le 6$ by Theorem 1, and $r_2' \ge 4/3$ by considering the cycle $C_7$ on seven vertices (since $\chi _2'(C_7)=4$ while $\omega _2'(C_7)=3$). Relatedly, we believe that the following problem is worth investigating.

Conjecture 1

It is NP-hard to compute the clique number of twin unit disk graphs.

2 A 6-approximation

In this section we discuss the proof of Theorem 4, which has Theorem 1 as a special case.

To make the reader more familiar with the problem and the notations, we first present a much shorter argument for a weaker approximation. The proof is nearly the same as what Barrett et al. [1] used for an upper bound on the approximation ratio of 8, but with a small twist.

Proposition 1

For any twin unit disk graph G, $\delta ^*(G) \le 7 (\omega (G)-1)$.

Proof

Let $G=(V,E)$ be a twin unit disk graph. Fix any embedding $p: V\rightarrow {\mathbb R}^2\times {\mathbb R}^2$ of G in the plane. Equipped with such an embedding, we first define an ordering of V and then use it to certify the promised degeneracy property.

The ordering we use for this result, a lexicographic ordering, is the same used in [1]. This lexicographic order considers first the y-coordinate and then the x-coordinate, (i.e. (a, b) is before (c, d) if and only if $b<d$ or ($b=d$ and $a\le c$)). Throughout this paper, we simply refer to it as the lexicographic order on ${\mathbb R}^2$. Let $(x_1,y_1),(x_2,y_2),\dots$ be a sequence of points in ${\mathbb R}^2$ defined by listing the elements of $\cup _{u\in V} \{p(u)_1,p(u)_2\}$ according to the lexicographic order on ${\mathbb R}^2$. We consider the points of this sequence in order and add vertices at the end of our current ordering of V as follows. When considering point $(x_j,y_j)$ for some $j\ge 1$, we add all vertices $u\in V$ for which there is some $i\le j$ such that $\{p(u)_1,p(u)_2\} = \{(x_i,y_i),(x_j,y_j)\}$, and we do so according to the lexicographic order on ${\mathbb R}^2$.

It suffices to show that each vertex $u\in V$ has at most $7(\omega (G)-1)$ neighbours that precede it in the lexicographic ordering. To do so, we show that every such neighbour v of u satisfies that either $p(v)_1$ or $p(v)_2$ is contained in one of seven unit $(\pi /3)$-sectors (each of which is centred around either $p(u)_1$ or $p(u)_2$). This is enough, since the set of vertices that map one of their twin points into one such sector induces a clique in G that includes u. The proof differs from what Barrett et al. did in [1] by the fact that we use seven unit $(\pi /3)$-sectors instead of eight.

Let $u\in V$ and suppose without loss of generality that $p(u)_1$ is before $p(u)_2$ in lexicographic order. First observe that, if $v\in V$ is before u in the lexicographic order, then both $p(v)_1$ and $p(v)_2$ must be in the region of ${\mathbb R}^2$ that has smaller or equal y-coordinate compared to $p(u)_2$. If, moreover $uv\in E$, then $p(v)_1$ or $p(v)_2$ must lie in either a unit half-disk centred at $p(u)_2$ or in the unit disk centred at $p(u)_1$. We partition the unit disk centred at $p(u)_1$ into six unit $(\pi /3)$-sectors such that the line segment $[p(u)_1,p(u)_2]$ lies along the boundary between two of the sectors. Note that any of the points in the two sectors incident to $[p(u)_1,p(u)_2]$ also lies in the unit disk centred at $p(u)_2$. Figure 1 depicts the construction, with sectors separated by solid lines. Therefore, the four other sectors together with the three sectors that partition the unit half-disk centred at $p(u)_2$ are the seven unit $(\pi /3)$-sectors that we desire.    $\square$

Fig. 1.

The seven sectors one of which must contain $p(v)_1$ or $p(v)_2$.

It turns out that for Theorem 4 we can take the same approach as in Proposition 1, except with an ordering that is more subtle and an analysis that is substantially longer and more difficult. Since our arguments are “only” geometric, we feel that the ratio 6 can be improved, especially in Theorem 1. It should be possible to exploit the structural graph properties of $L(G)^2$, but our efforts have so far failed. This might be difficult.

2.1 Proof Outline of Theorem 4

Let $G=(V,E)$ be a twin unit disk graph. Fix any embedding $p: V\rightarrow {\mathbb R}^2\times {\mathbb R}^2$ of G in the plane. Without loss of generality, we may assume that this embedding satisfies for all $u\in V$ that $p(u)_1$ is before $p(u)_2$ according to the lexicographic order on ${\mathbb R}^2$. We define a preorder $\preceq$ on V as follows. For any $u,v\in V$,

$$\begin{aligned} u\,{\preceq }\, v\text { if and only if }p(u)_1\text {\,is not after }p(v)_1\text {\,according to the lexicographic order on }{\mathbb R}^2. \end{aligned}$$

Note that if $p(u)_1 = p(v)_1$, then both $u\preceq v$ and $v\preceq u$.

For any $u\in V$, we define $N^-(u)$ as the set of $v\in V$, $v\ne u$ such that $v\in N(u)$ and $v \preceq u$. It suffices to show that $|N^-(u)| \le 6(\omega (G)-1)$ for each $u\in V$.

Fix such a vertex $u\in V$. Let $h^+$ be the open half-plane of points above $p(u)_1$ and $h^-$ the closed half-plane of points not above $p(u)_1$. For a point w, let $\mathcal {C}_w$ (respectively $\mathcal {D}_w$) denote the circle (respectively the closed disk) with radius 1 centred at w. Let $\mathbf {X}(u)$ be the union of $\mathbf {X}^-(u):=(\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})\,\cap \,h^-$ and the set $\mathbf {X}^+(u)$ of elements of $(\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})\,\cap \,h^+$ at distance at most 1 from a point of $h^-\setminus (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})$.

Similarly to the proof of Proposition 1, we aim to cover $\mathbf {X}(u)$ with six sections that each correspond to a clique of G. Instead of requiring that these sections have diameter at most 1 (as we do for proving Proposition 1), we make use of sections having the following weaker property:

a section $S\subseteq \mathbb {R}^2$ is small if it can be partitioned into two parts $S^+$ and $S^-$ of diameter at most 1 and such that

• 1. $S^+\subseteq h^+$; and

• 2. for all points $q\in S^-$, $p_2\in S^+$ and $p_1\in h^-\setminus (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})$ such that $p_1$ and $p_2$ are at distance at most 1, the point q is at distance at most 1 from $p_1$ or $p_2$.

This property is always satisfied if S has diameter at most 1, as it then suffices to take $S^-:=S$ and $S^+:=\varnothing$.

Let $S=S^+\,\cup \,S^-$ be a section, with $S^+\subseteq h^+$. Let C be the set of vertices v such that one of $p(v)_1$ and $p(v)_2$ is in $S^-$, or ($p(v)_2\in S^+$ and $p(v)_1\in h^-\setminus (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})$). We say that S induces a clique if ($v,w \in C \implies vw$ is an edge).

Let S be a small section, with $S^+$ and $S^-$ as in the definition. Then S induces a clique. Indeed, take $v,w\in C$ as defined above, and let us prove that vw is an edge. If p(v) and p(w) both contain a point in $S^+$ or both contain a point in $S^-$, then these points are at distance at most 1 because $S^+$ and $S^-$ have diameter at most 1, which implies that vw is an edge. Using the definition of C, we may therefore assume without loss of generality that $p(v)_1\in S^-$, $p(w)_2\in S^+$ and $p(w)_1\in h^-\setminus (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})$, which implies that $p(v)_1$ is at distance at most 1 from $p(w)_1$ or $p(w)_2$ because S is small.

The theorem then follows from the following statement:

Claim 1

For every vertex u, $\mathbf {X}(u)$ can be covered by six sections $S_1,\dots ,S_6$ that induces a clique.

Let us first see why Claim 1 implies $|N^-(u)|\le 6(\omega (G)-1)$ (and therefore Theorem 4). For each section $S_i$, let $S_i^+$ and $S_i^-$ be as in the definition of inducing a clique. For every $i\in \{1,\dots ,6\}$, let $C_i$ be the set of vertices v such that one of $p(v)_1$ and $p(v)_2$ is in $S_i^-$, or ($p(v)_2\in S^+_i$ and $p(v)_1\in h^-\setminus (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})$). By definition, all $C_i$ are cliques.

It remains to show that $\bigcup _{i=1}^6C_i$ covers $N^-(u)$. A vertex v is in $N^-(u)$ if $p(v)_1\in h^-$ and one of $p(v)_1$ and $p(v)_2$ is in $\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2}$. In the case where one of $p(v)_1$ and $p(v)_2$ is in $S_i^-$ for some $i\in \{1,\dots ,6\}$, then $v\in C_i$. We can now assume that p(v) does not intersect $\bigcup _{i=1}^6S_i^-$. We know that $S_i^+\subseteq h^+$ for every $i\in \{1,\dots ,6\}$ and that $\bigcup _{i=1}^6S_i$ covers $\mathbf {X}^-(u)$, so p(v) does not intersect $\mathbf {X}^-(u)=(\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})\,\cap \,h^-$. This enforces that $p(v)_1\in h^-\setminus (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})$ and $p(v)_2\in (\mathcal {D}_{p(u)_1}\,\cup \,\mathcal {D}_{p(u)_2})\,\cap \,h^+$. Since $p(v)_1$ and $p(v)_2$ are at distance at most 1, the point $p(v)_2$ belongs to $\mathbf {X}^+(u)$, so there is $i\in \{1,\dots ,6\}$ with $p(v)_i\in S^+_i$. As a consequence, the vertex v is in the clique $C_i$.

It remains to prove Claim 1. Due to space limitations, parts of this proof are postponed to Appendix. In the following, we mainly describe the construction of the sections.

Construction of the Sections. Let $\rho$ be the length and $\theta$ the argument of the vector $p(u)_2-p(u)_1$. Without loss of generality, we may assume that the position of $p(u)_1$ is (0, 0) and that both coordinates of $p(u)_2$ are not negative, so that $0\le \theta \le \pi /2$. The position of $p(u)_2$ is therefore $\rho (\cos (\theta ),\sin (\theta ))$.

We have three different constructions of the sections $S_1,\dots ,S_6$ depending on $\theta$ and $\rho$. We distinguish a first case when $\theta \le \pi /6$, a second case when $\pi /6<\theta$ and $\rho \le 2\cos \theta$, and a last one when $2\cos \theta <\rho$.

If $w_1$, $w_2$ and $w_3$ are three points pairwise at distance 1, the thickened triangle with vertices $w_1$, $w_2$ and $w_3$ is the area $\mathcal {D}_{w_1} \cap \mathcal {D}_{w_2} \cap \mathcal {D}_{w_3}$. A thickened triangle has diameter 1.

First Case: $\mathbf{0\le \theta \le \pi /6}$

Claim 2

Sections $S_4$ and $S_6$ have diameter at most 1 and Sections $S_1$ and $S_2$ are small.

Fig. 2.

The six sections when $0\le \theta <\pi /6$. (Color figure online)

Let a be the lower intersection of $\mathcal {C}_{p(u)_1}$ and $\mathcal {C}_{p(u)_2}$. Let $a'$ be the point $(-1,0)$ (so $a'$ is the leftmost intersection of $\mathcal {C}_{p(u)_1}$ and the abscissa line). Likewise, let $a''$ be the point $p(u)_2 + (1,0)$. Figure 2 shows the six sections we are defining now. Section $S_1$ (in yellow in Fig. 2) is defined as the intersection between $\mathcal {D}_{p(u)_1}$, $\mathcal {D}_{a'}$, and the half-plane above the line through $p(u)_1$ and the point $b:=(-\sqrt{3}/2,-1/2)$. Let Section $S_2$ (in red in Fig. 2) be the intersection between $\mathcal {D}_{p(u)_2}$, $\mathcal {D}_{a''}$ and the half-plane above the line through $p(u)_2$ and the point $c:=p(u)_2+(\sqrt{3}/2,-1/2)$. Let Section $S_3$ (in purple) be the thickened triangle with vertices $p(u)_1$, b and $q_1:=(0,-1)$. Section $S_4$ (in green) is defined as $\mathcal {D}_{p(u)_1} \cap \mathcal {D}_{p(u)_2} \cap \mathcal {D}_{a}\setminus (\mathcal {D}_b\,\cup \,\mathcal {D}_c)$. Section $S_5$ in cyan is the thickened triangle with vertices $p(u)_2$, c and $q_2:= p(u)_2+(0,-1)$. Lastly, let $S_6=\mathbf {X}(u)\setminus (\bigcup _{i=1}^5 S_i)$ be the remaining section.

These six sections cover $\mathbf {X}(u)$ by the definition of $S_6$. Sections $S_3$ and $S_5$ are thickened triangles so they have diameter 1. To prove the proposition in this case, it is enough to show the following property.

For some values of $\rho$ (for instance $\rho =1)$, when $\theta$ is greater than $\pi /6$, the Euclidean distance between $q_1$ and a is bigger than 1, hence so is the diameter of $S_6$. Therefore we have different constructions when $\pi /6< \theta$.

Fig. 3.

The six sections when $\pi /6 < \theta$ and $\rho \le 2\cos \theta$. (Color figure online)

Second Case: ${\varvec{\pi /6< \theta }}$ and ${\varvec{\rho \le 2\cos (\theta )}}$. Figure 3 depicts the six sections. A simple calculus shows that the position of a is $\frac{1}{2}(\rho \cos (\theta )+\sqrt{4-\rho ^2}\sin (\theta ),\rho \sin (\theta )-\sqrt{4-\rho ^2}\cos (\theta )$. The fact that $\rho$ is at most $2\cos (\theta )$ implies that the point a is not above the abscissa line. We denote by r the point $(-1,0)$. The conditions $\pi /6< \theta$ and $\rho \le 2\cos (\theta )$ do not imply anything on whether $(\mathcal {D}_{p(u)_2}\,\cap \,\mathcal {D}_{r})\setminus \mathcal {D}_{p(u)_1}$ is empty or not. Let $s_1$ be the highest point in $(\mathcal {D}_{p(u)_1}\,\cap \,\mathcal {D}_{r})\setminus \mathcal {D}_{p(u)_2}$. Note that if $(\mathcal {D}_{p(u)_2}\,\cap \,\mathcal {D}_{r})\setminus \mathcal {D}_{p(u)_1}$ is empty then the position of $s_1$ is $(-1/2,\sqrt{3}/2)$. Let $s_2$ be at the left intersection of $\mathcal {C}_{s_1}$ and the abscissa line. Let $s'_2$ be the translated of $s_2$ by the vector (1, 0). Let $s_3$ be the intersection of $\mathcal {C}_{p(u)_1}$ and $\mathcal {C}_{s'_2}$ that is below the abscissa line (if $p(u)_1$ and $s'_2$ have the same position, the position of $s_3$ is set to $(0,-1)$). Let $s_4$ (respectively $s_5$) be the point at the intersection of $\mathcal {C}_{p(u)_1}$ and $\mathcal {C}_{s_3}$ that is on left side (respectively right side) of the line $(p(u)_1,s_3)$. Observe that if $(\mathcal {D}_{p(u)_2}\,\cap \,\mathcal {D}_{r})\setminus \mathcal {D}_{p(u)_1}$ is empty then the positions of $s_2$, $s'_2$, $s_3$, $s_4$ and $s_5$ are respectively $(-1,0)$, (0, 0), $(0,-1)$, $(-1/2,-\sqrt{3}/2)$ and $(1/2,-\sqrt{3}/2)$. Let $S_1$ (in yellow) be the section defined as the union of $\mathcal {D}_{p(u)_1} \cap \mathcal {D}_{r} \cap h^+$ and the intersection between $\mathcal {D}_{p(u)_1}$, $h^-$ and the half-plane above the line $(p(u)_1,s_4)$. If $(\mathcal {D}_{p(u)_2}\,\cap \,\mathcal {D}_{r})\setminus \mathcal {D}_{p(u)_1}$ is empty, then $S_1$ is exactly as in the precedent case. Let $S_2$ (in blue) be the thickened triangle with vertices $p(u)_1$, $s_3$ and $s_4$. Let $S_3$ (in purple) be the thickened triangle with vertices $p(u)_1$, $s_3$ and $s_5$. Let p be the rightmost point of $\mathcal {C}_{p(u)_2}$ with height 1. Let q be the point of $\mathcal {C}_{p(u)_2}$ such that $pqp(u)_2$ is a clockwise equilateral triangle (therefore with sides of length 1). Let $S_4$ (in red) be the thickened triangle with these three vertices. Let $S_5$ (in green) be the thickened triangle with vertices $p(u)_2$, q, and a third vertex inside the purple section $S_3$. Let $S_6=\mathbf {X}(u)\setminus (\bigcup _{i=1}^5S_i)$ (in grey) be the remaining section.

It is clear from the definition of $S_6$ that $\bigcup _{i=1}^6S_i$ covers $\mathbf {X}(u)$. Sections $S_2$, $S_3$, $S_4$ and $S_5$ have diameter 1 as thickened triangles. To prove the proposition in this case, it suffices to check the following.

Claim 3

Section $S_1$ induces a clique and $S_6$ is small.

When $\theta <\pi /6$, for some values of $\rho$, the section $S_6$ is too big, and does not induce a clique. Likewise, for some values of $\rho$ and $\theta$ with $2\cos \theta <\rho$, $S_6$ is too big. This is why we use different constructions for the two other cases.

Fig. 4.

The six sections when $2\cos \theta < \rho$. (Color figure online)

Third Case: ${\varvec{2\cos (\theta )<\rho }}$. The construction for this last case is illustrated in Fig. 4. Note that $2 \cos (\theta )< \rho$ implies that $\theta$ is larger than $\pi /3$. It also implies that the point a is above the abscissa line. The construction of the six sections is more complicated in this last case. We denote by $r_0$, $r_1$, $r_2$ and $r_3$ the points $(-1,0)$, $(-1/2,-\sqrt{3}/2)$, $(1/2,-\sqrt{3}/2)$ and (1, 0). Let $S_1$ (in blue) be the thickened triangle with vertices $p(u)_1$, $r_0$ and $r_1$. Let $S_2$ (in green) be the thickened triangle with vertices $p(u)_1$, $r_1$ and $r_2$ and let $S_3$ (in red) be the thickened triangle with vertices $p(u)_1$, $r_2$ and $r_3$. Let b be the upper intersection between the circles $\mathcal {C}_{p(u)_2}$ and $\mathcal {C}_{r_0}$. Note that the circles $\mathcal {C}_b$ and $\mathcal {C}_{r_1}$ intersect in $r_0$, and let c be their second intersection. Let $c'$ be the translated of c by the vector (1, 0). Section $S_4$ (in purple) is defined as the thickened triangle with vertices c, $c'$ and a third point uniquely defined with positive y-coordinate. Let $S_5$ (in yellow) be the thickened triangle with vertices $r_0$, b and a point inside the section $S_4$ (in purple). Set $S_6=\mathbf {X}(u)\setminus (\bigcup _{i=1}^5S_i)$.

Sections $S_1$, $S_2$, $S_3$, $S_4$ and $S_5$ have diameter 1 because they are thickened triangles. To conclude this case and finish the proof, it suffices to show the following property.

Claim 4

Section $S_6$ is small.

For this construction, b must not be inside $\mathcal {D}_{p(u)_1}$, otherwise the distance between $r_0$ and c would be greater than 1. This is always true when $2\cos \theta < \rho$, but not guaranteed for other values. For instance if $\rho =1$, then b is not inside $\mathcal {D}_{p(u)_1}$ if and only if $2\cos (\theta ) \le \rho$, i.e. $\theta \ge \pi /3$, which is why we use this construction only for this case.

The proofs of Claims 2, 3 and 4 can be found in Appendix.

3 An Online 8-competitive algorithm

Our focus in this section is to prove Theorem 5, which directly implies Theorem 2. As alluded to earlier, we make use of the following kissing number-type result, which may be of independent interest. The corresponding problem in ${\mathbb R}^3$ is interesting and may be difficult.

Theorem 6

Let $x_1$ and $x_2$ be two points in ${\mathbb R}^2$ within Euclidean distance 1. Let Y be a collection of points in ${\mathbb R}^2$ pairwise of Euclidean distance greater than 1 such that either y and $x_1$ or y and $x_2$ are within Euclidean distance 1 for any $y\in Y$. Then $|Y|\le 8$.

Fig. 5.

Theorem 6 is tight.

Note that this result is sharp as illustrated in Fig. 5. Take $x_1$ and $x_2$ to be at Euclidean distance 1, and choose the 8 points in Y as in a partial optimal circle packing configuration. Now it is possible to shift one of the vertices that are at Euclidean distance 1 from both $x_1$ and $x_2$, and to perturb slightly the position of the others, so that all points in Y are pairwise of Euclidean distance greater than 1. Before giving the proof of Theorem 6, we first show how it readily implies Theorem 5.

Proof

(Proof of Theorem 5). Let $G=(V,E)$ be a twin unit disk graph and fix an embedding $p: V\rightarrow {\mathbb R}^2\times {\mathbb R}^2$. Let $u\in V$ be a vertex of degree $\varDelta (G)$ and consider the set N(u) of neighbours of u in G. Without loss of generality, we may assume that for any $v\in N(u)$ either $p(v)_1$ and $p(u)_1$ or $p(v)_1$ and $p(u)_2$ are within distance 1. It follows from Theorem 6 that the subgraph of G induced by N(u) has no independent set with more than 8 vertices. We know that this induced subgraph can be properly coloured with at most $\chi (G)-1$ colours. We therefore conclude that $\varDelta (G)/8 = |N(u)|/8 \le \chi (G)-1$, which completes the proof.   $\square$

We prove Theorem 6 through a succession of geometric lemmas. In these lemmas, we treat points in ${\mathbb R}^2$ as hypothetical vertices of an embedded unit disk graph, so we speak of pairs of them as adjacent, i.e. within Euclidean distance 1, or not.

Lemma 1

Let u, v, $v'$ be points in ${\mathbb R}^2$ such that u and v are adjacent, u and $v'$ are adjacent, and v and $v'$ are non-adjacent. If we shift v further from u in the direction of the line segment [u, v] until u and v are non-adjacent, then v and $v'$ remain non-adjacent.

Proof

Assume without loss of generality that the position of u is (0, 0) and that the first position of v is (z, 0) with $0< z \le 1$ before going to (1, 0). We denote the position of $v'$ as (x, y). As can be deduced from the proof of the Lemma 3.1 in [16], the angle between the line segments [u, v] and $[u,v']$ is at least $\pi /3$. Thus $x\le 1/2$, and so $2x \le 1+z$. Then we obtain $2x(1-z)\le 1-z^2$ and so $z^2-2xz\le 1-2x$. We also know $(x-z)^2+y^2>1$ since v and $v'$ are non-adjacent. Now $(x-1)^2+y^2= x^2+1-2x+y^2\ge x^2+z^2-2zx+y^2=(x-z)^2+y^2>1$. Thus the distance between v and $v'$ is still larger than 1.    $\square$

Lemma 2

Let u, v, $u'$, $v'$ be points in ${\mathbb R}^2$ such that u and v are adjacent, u and $u'$ are adjacent, v and $v'$ are adjacent, u and $v'$ are non-adjacent, v and $u'$ are non-adjacent, and $u'$ and $v'$ are non-adjacent. Then one of the following is true.

• If we shift $u'$ further from u in the direction of the line segment $[u,u']$ until u and $u'$ are non-adjacent, then $u'$ remains non-adjacent with v and $v'$.

• If we shift $v'$ further from v in the direction of the line segment $[v,v']$ until v and $v'$ are non-adjacent, then $v'$ remains non-adjacent with u and $u'$.

Proof

Figure 6 depicts one potential situation covered by Lemma 2. Assume without loss of generality that the position of u is (0, 0) and the position of v is (1, 0). If the abscissa coordinate of $u'$ or $v'$ is not between 0 and 1, then it is possible to shift this point as claimed. Assume that the abscissa coordinate of both points is between 0 and 1. Then one must be above the other. Assume that $u'$ is above $v'$, for consistency with Fig. 6. We may also assume that they are both above the abscissa line, otherwise the claim is immediately true. By Lemma 1, we know that shifting $u'$ until its distance to u is 1 will not make it adjacent to v. Moreover, since the abscissa of $u'$ and $v'$ is between 0 and 1, the line segment $[u,u']$ goes through the disk with radius 1 centred at $v'$. As $u'$ is not in this disk, and because a disk is convex, shifting $u'$ as claimed will not return it to the disk. If instead $v'$ is above $u'$, then shifting will instead be possible for $v'$ because of the same arguments.    $\square$

Fig. 6.

By shifting $u'$ to the position of w, it remains non-adjacent to v and to $v'$.

Lemma 3

Let u and $u'$ be points in ${\mathbb R}^2$ such that u and $u'$ are adjacent. Let $v_1,\dots ,v_8$ be eight pairwise non-adjacent points in ${\mathbb R}^2$ each of which is adjacent to u or to $u'$. Then some $v_i$ is adjacent to both u and $u'$.

Proof

We assume that no $v_i$ is adjacent to both u and $u'$, and show that this leads to a contradiction. Without loss of generality, assume that the position of u is (0, 0) and the position of $u'$ is (d, 0) with $0<d\le 1$. Denote by $V_u$ (respectively $V_{u'}$) the set of those $v_i$ adjacent to u (respectively $u'$). We add to the abscissa of $u'$ and all the points in $V_{u'}$ the value $1-d$. Thus u and $u'$ are still adjacent and the points in $V_{u'}$ are still adjacent to $u'$. Note that the bisector of the line segment $[u,u']$ separates the points in $V_u$ from the points in $V_{u'}$. Indeed if a point is in $V_u$, it is closer to u than $u'$, and vice versa. Thus the points $\{v_i\}_i$ are still pairwise non-adjacent. Now the position of $u'$ is (1, 0).

The star graph $K_{1,6}$ is not a unit disk graph. Thus since the points in $V_u\,\cup \,\{u'\}$ are pairwise non-adjacent and adjacent to u, we have $|V_u|<5$. By the same reasoning we obtain $|V_{u'}|<5$. Thus we have $|V_u|=|V_{u'}|=4$. Without loss of generality, assume that we have $V_u=\{v_1,v_2,v_3,v_4\}$ and $V_{u'}=\{v_5,v_6,v_7,v_8\}$. We order the points in $V_u$. For a point v we will consider the oriented angle between the line segments [u, v] and $[u,u']$ taken in $[0,2 \pi )$. Note that two points cannot have the same angle value. Thus we can order the points from the smallest angle value to the largest. We apply the same process to the points in $V_{u'}$. For a point $v'$, we consider the angle between $[u',v']$ and $[u',u]$. Without loss of generality we can assume that the points in $V_u$ appear in the right order. Figure 7a depicts the ordering. (Of course, since we are going to show a contradiction, the graph in the figure cannot satisfy the assumptions we have taken.)

Now we move the point $v_2$ further from u in the direction of the line segment $[u,v_2]$ until the distance between $v_2$ and u is 1. By Lemma 1, we know that when $v_2$ is shifted in this way, it will not become adjacent to any other point in $\{v_i\}_i$. We apply the same process to $v_3$, $v_6$ and $v_7$. By Lemma 2, it is possible to shift either $v_1$ or $v_8$, and either $v_4$ or $v_5$. Without loss of generality, assume that it is possible to shift $v_1$. Denote by $\theta \in [0,2\pi )$ the angle between the line segments $[u,v_1]$ and $[u,u']$. By the same arguments as above, we have $\theta >\pi /3$. Thus the angle between $[u,v_4]$ and $[u,u']$ taken in $[0,2\pi )$ is larger than $\theta +\pi$. Let us consider the angle between $[u',v_7]$ and the abscissa line. It is less than $\theta -\pi /3$, because otherwise $v_8$ must be adjacent to u or $v_1$, as we prove in the next paragraph. Thus the worst case is when the angle is exactly equal to $\theta -\pi /3$. We have u at position (0, 0), $u'$ at (1, 0), $v_1$ at $(\cos (\theta ),\sin (\theta ))$ and $v_7$ at $(1+\cos (\theta -\pi /3),\sin (\theta -\pi /3))$.

We move $v_8$ so that it is at distance 1 from both u and $v_7$. This is theoretically not possible because $v_8$ is not adjacent to those points, but we are going to show that even in this case we have $v_8$ at distance 1 from $v_1$. Since this position is the furthest $v_8$ could be from $v_1$, this shows a contradiction, and thus that the angle between $[u',v_7]$ and the abscissa line must be less than $\theta -\pi /3$. Let us compute the position (x, y) of $v_8$. We have $x^2+y^2=1$ and $(x-1-\cos (\theta -\pi /3))^2+(y-\sin (\theta -\pi /3))^2=1$. There are two possible solutions. One is (1, 0), which is the position of $u'$, and the other is the position of $v_8$: $(\cos (\theta -\pi /3),\sin (\theta -\pi /3))$. Figure 7b depicts the position of the points. But then the distance between $v_1$ and $v_8$ is equal to 1. Thus, even if we take $v_8$ to be the furthest possible from $v_1$, they are still too close. Thus we know that the angle between $[u',v_7]$ and the abscissa line taken in $[0,2\pi )$ must be larger than $\theta -\pi /3$. Hence the angle between $[u',v_6]$ and the same line taken into $[0,2\pi )$ must be less than $\theta +4\pi /3$, and the angle between $[u',v_5]$ and the same line must be less than $\theta +\pi$. We have seen that either $v_4$ or $v_5$ can be pushed until their distance to u or $u'$ is 1. If it is possible for $v_4$ we can apply what we did before to $v_4$ and $v_6$ to obtain a contradiction. If it is possible for $v_5$, we then apply the reasoning to $v_3$ and $v_5$. In any case we have a contradiction, which concludes the proof of the lemma.   $\square$

Fig. 7.

Illustration of Lemma 3

Proof

(Proof of Theorem 6). Let Y in the statement of the theorem be $\{y_1,\dots ,y_9\}$ for a contradiction. For any eight points in Y, Lemma 3 guarantees that at least one of them is within Euclidean distance 1 of both $x_1$ and $x_2$. Without loss of generality, we may thus assume that both $y_1$ and $y_2$ are within Euclidean distance 1 to both $x_1$ and $x_2$. Of the seven remaining points of Y, at least four of them must be within Euclidean distance 1 of, say, $x_1$, by the pigeonhole principle. But then $x_1$ is within Euclidean distance 1 of six points that are pairwise of Euclidean distance greater than 1, which is impossible.    $\square$