Recognizing Weighted Disk Contact Graphs

Abstract

Disk contact representations realize graphs by mapping vertices bijectively to interior-disjoint disks in the plane such that two disks touch each other if and only if the corresponding vertices are adjacent in the graph. Deciding whether a vertex-weighted planar graph can be realized such that the disks’ radii coincide with the vertex weights is known to be $\textsf {NP}$-hard. In this work, we reduce the gap between hardness and tractability by analyzing the problem for special graph classes. We show that it remains $\textsf {NP}$-hard for outerplanar graphs with unit weights and for stars with arbitrary weights, strengthening the previous hardness results. On the positive side, we present constructive linear-time recognition algorithms for caterpillars with unit weights and for embedded stars with arbitrary weights.

1 Introduction

A set of disks in the plane is a disk intersection representation of a graph $G=(V,E)$ if there is a bijection between V and the set of disks such that two disks intersect if and only if they are adjacent in G. Disk intersection graphs are graphs that have a disk intersection representation; a subclass are disk contact graphs (also known as coin graphs), that is, graphs that have a disk intersection representation with interior-disjoint disks. This is also called a disk contact representation (DCR) or, if connected, a circle packing. It is easy to see that every disk contact graph is planar and the famous Koebe-Andreev-Thurston circle packing theorem [13] dating back to 1936 (see Stephenson [17] for its history) states that the converse is also true, that is, every planar graph is a disk contact graph.

Application areas for disk intersection/contact graphs include modeling physical problems like wireless communication networks [9], covering problems like geometric facility location [16, 18], visual representation problems like area cartograms [7] and many more (various examples are given by Clark et al. [4]). Efficient numerical construction of DCRs has been studied in the past [5, 15]. Often, however, one is interested in recognizing disk graphs or generating representations that do not only realize the input graph, but also satisfy additional requirements. For example, Alam et al. [1] recently obtained several positive and negative results on the existence of balanced DCRs, in which the ratio of the largest disk radius to the smallest is polynomial in the number of disks. Furthermore, it might be desirable to generate a disk representation that realizes a vertex-weighted graph such that the disks’ radii or areas are proportional to the corresponding vertex weights, for example, for value-by-area circle cartograms [10]. Clearly, there exist vertex-weighted planar graphs that cannot be realized as disk contact representations, and the corresponding recognition problem for planar graphs is $\textsf {NP}$-hard, even if all vertices are weighted uniformly [3]. The complexity of recognizing weighted disk contact graphs for many interesting subclasses of planar graphs remained open. Note that graphs realizable as DCRs with unit disks correspond to 1-ply graphs. This was stated by Di Giacomo et al. [6] who recently introduced and studied the ply number concept for graphs. They showed that internally triangulated biconnected planar graphs admitting a DCR with unit disks can be recognized in $O(n \log n)$ time.

In this paper we extend the results of Breu and Kirkpatrick [3] and show that it remains $\textsf {NP}$-hard to decide whether a DCR with unit disks exists even if the input graph is outerplanar. Our result holds both for the case that arbitrary embeddings are allowed and the case that a fixed combinatorial embedding is specified. The result for the latter case is also implied by a very recent result by Bowen et al. [2] stating that for fixed embeddings the problem is $\textsf {NP}$-hard even for trees. However, the recognition of trees with a unit disk contact representation remains an interesting open problem if arbitrary embeddings are allowed. For caterpillar-trees we solve this problem in linear time. For vertex weights that are not necessarily uniform we show that the recognition problem is strongly $\textsf {NP}$-hard even for stars if no embedding is specified. However, for embedded stars we solve the problem in linear time. Some of our algorithms use the Real RAM model, which assumes that a set of basic arithmetic operations (including trigonometric functions and square roots) can be performed in constant time.

2 Unit Disk Contact Graphs

In this section we are concerned with the problem of deciding whether a given graph is a unit disk contact graph (UDC graph), that is, whether it has a DCR with unit disks. For a UDC graph we also say that it is UDC-realizable or simply realizable. It is known since 1998 that recognizing UDC graphs is generally $\textsf {NP}$-hard for planar graphs [3], but it remained open for which subclasses of planar graphs it can be solved efficiently and for which subclasses $\textsf {NP}$-hardness still holds. We show that we can recognize caterpillars that are UDC graphs in linear time and construct a representation if it exists (Sect. 2.1), whereas the problem remains $\textsf {NP}$-hard for outerplanar graphs (Sect. 2.2).

2.1 Recognizing Caterpillars with a Unit Disk Contact Representation

Let $G=(V,E)$ be a caterpillar graph, that is, a tree for which a path remains after removing all leaves. Let $P = (v_1, \dots , v_k)$ be this so-called inner path of G. On the one hand, it is well known that six unit disks can be tightly packed around one central unit disk, but then any two consecutive outer disks necessarily touch and form a triangle with the central disk. This is not permitted in a caterpillar and thus we obtain that in any realizable caterpillar the maximum degree $\varDelta \le 5$. On the other hand, it is easy to see that all caterpillars with $\varDelta \le 4$ are UDC graphs as shown by the construction in Fig. 1a.

Fig. 1.

(a) For $\varDelta \le 4$ any caterpillar can be realized. (b) Incremental construction of a DCR. Narrow disks are dark gray and indicated by an outgoing arrow, wide disks are light gray.

However, not all caterpillars with $\varDelta = 5$ can be realized. For example, two degree-5 vertices on P separated by zero or more degree-4 vertices cannot be realized, as they would again require tightly packed disks inducing cycles in the contact graph. In fact, we get the following characterization.

Lemma 1

A caterpillar G with $\varDelta = 5$ is a UDC graph if and only if there is at least one vertex of degree at most 3 between any two degree-5 vertices on the inner path P.

Proof

Consider an arbitrary UDC representation of G and let $D_i$ be the disk representing vertex $v_i$ of the inner path P. Let $\ell _i$ be the tangent line between two adjacent disks $D_{i-1}$ and $D_i$ on P. We say that P is narrow at $v_i$ if some leaf disk attached to $D_{i-1}$ intersects $\ell _i$; otherwise P is wide at $v_i$. Let $v_i$ and $v_j$ ($i<j$) be two degree-5 vertices on P with no other degree 5 vertices between them. The path P must be narrow at the next vertex $v_{i+1}$, since one of the four mutually disjoint neighbor disks of $D_{i-1}$ except $D_i$ necessarily intersects $\ell _i$. If there is no vertex $v_k$ $(i<k<j)$ with $\deg (v_k) \le 3$ between $v_i$ and $v_j$ we claim that P is still narrow at $v_j$. If $j=i+1$ this is obviously true. Otherwise all vertices between $v_i$ and $v_j$ have degree 4. But since the line $\ell _{i+1}$ was intersected by a neighbor of $v_i$, this property is inherited for the line $\ell _{i+2}$ and a neighbor of $v_{i+1}$ if $\deg (v_{i+1})=4$. An inductive argument applies. Since P is still narrow at the degree-5 vertex $v_j$, it is impossible to place four mutually disjoint disks touching $D_{j}$ for the neighbors of $v_j$ except $v_{j-1}$.

We now construct a UDC representation for a caterpillar in which any two degree-5 vertices of P are separated by a vertex of degree $\le 3$. We place a disk $D_1$ for $v_1$ at the origin and attach its leaf disks leftmost, that is, symmetrically pushed to the left with a sufficiently small distance between them. In each subsequent step, we place the next disk $D_i$ for $v_i$ on the bisector of the free space, which we define as the maximum cone with origin in $D_{i-1}$’s center containing no previously inserted neighbors of $D_{i-1}$ or $D_{i-2}$. Again, we attach the leaves of $D_{i}$ in a leftmost and balanced way, see Fig. 1b. For odd-degree vertices this leads to a change in direction of P, but by alternating upward and downward bends for subsequent odd-degree vertices we can maintain a horizontal monotonicity, which ensures that leaves of $D_i$ can only collide with leaves of $D_{i-1}$ or $D_{i-2}$. In this construction P is wide until the first degree-5 vertex is placed, after which it gets and stays narrow as long as degree-4 vertices are encountered. But as soon as a vertex of degree $\le 3$ is placed, P gets (and remains) wide again until the next degree-5 vertex is placed. Placing a degree-5 vertex at which P is wide can always be done. $\square$

Lemma 1 and the immediate observations for caterpillars with $\varDelta \ne 5$ yield the following theorem. We note that the decision is only based on the vertex degrees in G, whereas the construction uses a Real RAM model.

Theorem 1

For a caterpillar G it can be decided in linear time whether G is a UDC graph if arbitrary embeddings are allowed. A UDC representation (if one exists) can be constructed in linear time.

Fig. 2.

Sketch of the grid layout $\mathcal {G}_\varphi$ (a) and high-level structure of the construction of $G'_\varphi$ (b) for the PM3SAT formula $\varphi = (x_1\vee x_2)\wedge (x_1\vee x_2\vee x_3)\wedge (\bar{x}_1\vee \bar{x}_2\vee \bar{x}_3)$.

2.2 Hardness for Outerplanar Graphs

A planar 3SAT formula $\varphi$ is a Boolean 3SAT formula with a set $\mathcal U$ of variables and a set $\mathcal C$ of clauses such that its variable-clause-graph $G_\varphi = (\mathcal U\cup \mathcal C, E)$ is planar. The set E contains for each clause $c \in \mathcal C$ the edge (c, x) if a literal of variable x occurs in c. Deciding the satisfiability of a planar 3SAT formula is $\textsf {NP}$-complete [14] and there exists a planar drawing $\mathcal {G}_\varphi$ of $G_\varphi$ on a grid of polynomial size such that the variable vertices are placed on a horizontal line and the clauses are connected in a comb-shaped rectangular fashion from above or below that line [12], see Fig. 2a. A planar 3SAT formula $\varphi$ is monotone if each clause contains either only positive or only negative literals and if $G_\varphi$ has a planar drawing as described before with all clauses of positive literals on one side and all clauses of negative variables on the other side. The 3SAT problem remains $\textsf {NP}$-complete for planar monotone formulae [14] and is called Planar Monotone 3-Satisfiability (PM3SAT).

We perform a polynomial reduction from PM3SAT to show $\textsf {NP}$-hardness of recognizing outerplanar UDC graphs. A graph is outerplanar if it has a planar drawing in which all vertices lie on the unbounded outer face. We say that a planar graph G is (combinatorially) embedded if we are given for each vertex the circular order of all incident edges as well as the outer face such that a planar drawing respecting this embedding exists. For the reduction we create, based on the planar drawing $\mathcal {G}_\varphi$, an outerplanar graph $G'_\varphi$ that has a UDC representation if and only if the formula $\varphi$ is satisfiable.

Arguing about UDC representations of certain subgraphs of $G'_\varphi$ becomes a lot easier, if there is a single unique geometric representation (up to rotation, translation and mirroring). We call graphs with such a representation rigid. Using an inductive argument (see full version [11]), we state the following sufficient condition for rigid UDC structures. All subgraphs of $G'_\varphi$ that we refer to as rigid satisfy this condition.

Lemma 2

Let $G=(V,E)$ be a biconnected graph realizable as a UDC representation that induces an internally triangulated outerplane embedding of $G$. Then, $G$ is rigid.

Fig. 3.

Variable gadget in state false with a positive (left) and a negative literal (right).

The main building block of the reduction is a wire gadget in $G'_\varphi$ that comes in different variations but always consists of a rigid tunnel structure containing a rigid bar that can be flipped into different tunnels around its centrally located articulation vertex. Each wire gadget occupies a square tile of fixed dimensions so that different tiles can be flexibly put together in a grid-like fashion. The bars stick out of the tiles in order to transfer information to the neighboring tiles. Variable gadgets consist of special tiles containing tunnels without bars or with very long bars. Adjacent variable gadgets are connected by narrow tunnels without bars. Face merging wires work essentially like normal horizontal wires but their low-level construction differs in order to assert that $G'_\varphi$ is outerplanar and connected. Figure 2b shows a schematic view of how the gadget tiles are arranged to mimic the layout $\mathcal G_\varphi$ of Fig. 2a. The wires connect the positive (negative) clauses to the left (right) halves of the respective variable gadgets. Furthermore, we place a face merging wire (marked by ‘M’) in the top/bottom left corner of each inner face followed by an upper (lower) spiral, which is a fixed $3\times 4$ pattern of wire gadgets. These structures ensure that $G'_\varphi$ is outerplanar and they limit relative displacements.

The main idea behind the reduction is as follows. Each variable gadget contains one thin, long horizontal bar that is either flipped to the left (false) or to the right (true), see Fig. 3. If the bar is in its left (right) position, this blocks the lower (upper) bar position of the first wire gadget of each positive (negative) literal. Consequently, each wire gadget that is part of the connection between a variable gadget and a clause gadget must flip its entire chain of bars towards the clause if the literal is false. The design of the clause gadget depends on its number of literals. Figure 4a illustrates the most important case of a clause with three literals containing a T-shaped wire gadget. The bar of the T-shaped wire needs to be placed in one of the three incident tunnels. This is possible if and only if at least one of the literals evaluates to true. A similar statement holds true for clauses with two or one literals; their construction is much simpler: just a horizontal wire gadget or a dead end suffice as clause tile.

Fig. 4.

(a) Clause gadget with two false inputs (left and right) and one true input. (b) Detailed view of a horizontal wire gadget with a rigid bar (black disks) inside a tunnel (dark gray disks).

All gadgets are realized by combining several rigid UDC subgraphs. As an example, Fig. 4b shows a close-up of the left side of a horizontal wire gadget. Both the black and the dark gray disks form rigid components whose UDC graphs satisfy the precondition of Lemma 2. The black disks implement the bar, the dark gray disks constitute the tunnel. Note how the bar can be flipped or mirrored to the left or the right around the articulation disk (marked ‘x’) due to the two light gray disks (called chain disks) that do not belong to a rigid structure. The width of each bar is chosen such that it differs from the supposed inner width of a tunnel by at most twice the disk diameter, thus admitting some slack. However, we can choose the width of the tunnels/bars (and the gadget tile dimensions) as a large polynomial in the input such that this “wiggle room” does not affect the combinatorial properties of our construction. The description of the face merging wire below discusses this aspect in more detail. Further, we choose the lengths of the bars such that the bars of two adjacent wire gadgets collide if their bars are oriented towards each other. Unlike the bars of wire gadgets, the bars of variable gadgets are not designed to transmit information from tile to tile. Instead they are simply designed to prevent the adjacent vertical wires on either the left or the right side of the variable gadget to be oriented towards it. For this reason, we can choose the width of the variable bars to be very small (e.g., just 2 disks), in order to obtain an overall tighter construction.

Fig. 5.

Schematic of $G'_\varphi$ if face merging wires (marked ‘M’) replace some regular wires. Inner faces of $\mathcal G_\varphi$ in dark gray, the face ‘inside the tunnels’ in light gray, the outer face in white and the face boundaries in black

Now that we have established how the gadgets work and how they are constructed, consider the properties of the corresponding graph $G'_\varphi$ that encodes the entire structure. If we would use only the regular wire gadgets as in Fig. 4b for the entire construction, $G'_\varphi$ would neither be outerplanar nor connected. As illustrated in Fig. 5, for each of the inner faces of $\mathcal G_\varphi$ we would obtain a single rigid structure, which we call face boundary, with several bars attached to it. These face boundaries, however, would not be connected to each other. Furthermore, the subgraphs that realize the face boundaries would not be outerplanar. This is why we replace some horizontal wire gadgets in the upper (positive) and lower (negative) part of our construction by upper and lower face merging wires respectively, which have two purposes. Horizontal wires contain a tunnel that is formed by two face boundaries, called the upper and lower face boundary of the corresponding gadget tile. These face boundaries are not connected, see Fig. 4b. In a face merging wire, however, the respective face boundaries are connected. Furthermore, a gap is introduced (by removing two disks) to the lower (upper) face boundary in an upper (lower) face merging wire so that the lower (upper) face boundary now becomes outerplanar. Since the face merging wire is supposed to transfer information just like a horizontal wire we cannot connect the two face boundaries rigidly. Instead we create three bars connected to each other with chain disks, see Fig. 6a. The width of the top and the bottom bars are chosen such that they fit tightly inside the narrow cavity in the middle of the tile if placed perpendicularly to the left or right of the respective articulation disk. The third bar ensures that all three bars together are placed either to the left (Fig. 6b) or to the right (Fig. 6a), which allows the desired information transfer.

Together with the incident spiral, a face merging wire ensures that the disks of the lower face boundary deviate from their intended locations relative to the upper face boundary only by up to a small constant distance since (1) the design and the asymmetrical placement of the spirals and the face merging wires preserve the orientations of the respective upper and lower face boundaries, i.e., the left/right/top/bottom sides of these structures are facing as intended in any realization and (2) the width of the tunnels is at most twice the disk diameter larger than the width of the bars and there is at least one bar located in any of the cardinal directions of each spiral. This effect can cascade since the face boundaries might be connected to further face boundaries. However, according to Euler’s formula the number of faces in $\mathcal G_\varphi$ is linear in the number of clauses and variables and, therefore, the total distance by which a disk can deviate from its intended ideal position is also linear in this number. By accordingly adjusting the tile dimensions and bar widths, we can therefore ensure that the wiggle room in our construction does not affect the intended combinatorial properties while keeping the size of $G'_\varphi$ polynomial. The introduction of face merging wires causes $G'_\varphi$ to be connected and it causes all inner faces and the face ’inside the tunnels’ to collapse. Finally, by introducing a single gap in the outermost rigid structure, $G'_\varphi$ becomes outerplanar, which concludes our reduction.

This concludes our construction for the case with arbitrary embeddings. Note, however, that the gadgets are designed such that flipping the bars does not require altering the combinatorial embedding of the graph. This holds true even for the face merging wire. Therefore, we can furthermore provide a combinatorial embedding such that $G'_\varphi$ can be realized with respect to said embedding if and only if $\varphi$ is satisfiable. Thus, we obtain the following theorem with the remaining arguments of its proof found in [11].

Fig. 6.

Upper face merging wire gadget oriented to the right (a) / left (b). It connects the lower and upper face boundaries. The gap causes the faces inside the tunnel and the lower face to collapse.

Theorem 2

For outerplanar graphs the UDC recognition problem is $\textsf {NP}$-hard. This remains true for outerplanar graphs with a specified combinatorial embedding.

3 Weighted Disk Contact Graphs

In this section, we assume that a positive weight w(v) is assigned to each vertex v of the graph $G=(V,E)$. The task is to decide whether G has a DCR, in which each disk $D_v$ representing a vertex $v \in V$ has radius proportional to w(v). A DCR with this property is called a weighted disk contact representation (WDC representation) and a graph that has a WDC representation is called a weighted disk contact graph (WDC graph). Obviously, recognizing WDC graphs is at least as hard as the UDC graph recognition problem from Sect. 2 by setting $w(v) = 1$ for every vertex $v \in V$. Accordingly, we first show that recognizing WDC graphs is $\textsf {NP}$-hard even for stars (Sect. 3.1), however, embedded stars with a WDC representation can still be recognized (and one can be constructed if it exists) in linear time (Sect. 3.2).

3.1 Hardness for Stars

We perform a polynomial reduction from the well-known 3-Partition problem. Given a bound $B \in \mathbb N$ and a multiset of positive integers $\mathcal A= \{ a_1, \dots , a _{3n}\}$ such that $\frac{B}{4} < a_i < \frac{B}{2}$ for all $i = 1, \dots , 3n$, deciding whether $\mathcal A$ can be partitioned into n triples of sum B each is known to be strongly $\textsf {NP}$-complete [8]. Let $(\mathcal A,B)$ be a 3-Partition instance. We construct a star $S = (V,E)$ and a radius assignment $\mathbf {r}: V \rightarrow \mathbb {R}^+$ such that S has a WDC representation respecting $\mathbf {r}$ if and only if $(\mathcal A,B)$ is a yes-instance.

Fig. 7.

Reducing from 3-Partition to prove Theorem 3. Input disks (dark) are distributed between gaps. Hatched disks are separators.

We create a central disk $D_c$ of radius $r_c$ corresponding to the central vertex $v_c$ of S as well as a fixed number of outer disks with uniform radius $r_o$ chosen appropriately such that these disks have to be placed close together around $D_c$ without touching, creating funnel-shaped gaps of roughly equal size; see Fig. 7. Then, a WDC representation of S exists only if all remaining disks can be distributed among the gaps, and the choice of the gap will induce a partition of the integers $a_i \in \mathcal A$. We shall represent each $a_i$ by a single disk called an input disk and encode $a_i$ in its radius. Each of the gaps is supposed to be large enough for the input disks that represent a feasible triple, i.e., with sum B, to fit inside it, however, the gaps must be too small to contain an infeasible triple’s disk representation, i.e., a triple with sum $>B$.

While the principle idea of the reduction is simple, the main challenge is finding a radius assignment satisfying the above property and taking into account numerous additional, nontrivial geometric considerations that are required to make the construction work. For example, we require that the lower boundary of each gap is sufficiently flat. We achieve this by creating additional dummy gaps and ensure that they can not be used to realize a previously infeasible instance. Next, we make sure that additional separator disks must be placed in each gap’s corners to prevent left and right gap boundaries from interfering with the input disks. Finally, all our constructions are required to tolerate a certain amount of “wiggle room”, since, firstly, the outer disks do not touch and, secondly, some radii cannot be computed precisely in polynomial time.

Since S is supposed to be a star, the only adjacencies in our construction are the ones with $D_c$. However, several of the disks adjacent to $D_c$ are required to be placed very close together without actually touching. We shall, whenever we need to calculate distances, handle these barely not touching disks as if they were actually touching. We will describe how to compute these distances approximately; see Lemma 8. During this step the radius of the central disk increases by a suitably small amount such that no unanticipated embeddings can be created.

Let $B > 12$ and $n>6$, and let $m \ge n$ be the number of gaps in our construction. In the original scenario described above, a gap’s boundary belonging to the central disk $D_c$, which we call the gap’s bow, is curved as illustrated in Fig. 8a. We will, however, first consider a simplified scenario in which a gap is created by placing two disks of radius $r_o$ right next to each other on a straight line as depicted in Fig. 8a. We refer to this gap’s straight boundary as the base of the gap. We call a point’s vertical distance from the base its height. We also utilize the terms left and right in an obvious manner. Assume for now that we can place two separator disks in the gap’s left and right corner, touching the base and such that the distance between the rightmost point $p_l$ of the left separator and the leftmost point $p_r$ of the right separator is exactly 12 units. We can assume $B \equiv 0\mod 4$; see Lemma 3. Thus, we know that $a\in \lbrace B/4+1,\dots ,B/2-1\rbrace$ for any $a\in \mathcal A$. Due to space restrictions, the proofs of the following lemmas are only available in the full version [11].

Lemma 3

For each $m \ge n$, there exists a 3-Partition instance $(\mathcal A', B')$ equivalent to $(\mathcal A, B)$ with $|\mathcal A'|=3m$ and $B' = 180B$.

Our first goal is to find a function $r:\lbrace B/4,B/4+1,\dots ,B/2\rbrace \rightarrow \mathbb {R}^+$ that assigns a disk radius to each input integer as well as to the values B / 4 and B / 2 such that a disk triple t together with two separator disks can be placed on the base of a gap without intersecting each other or the outer disks if and only if t is feasible. In the following, we show that $r(x)=2-(4-12x/B)/B$ will satisfy our needs. We choose the radius of the separators to be $r_ min =r(B/4+1)=2-(1-12/B)/B$, the smallest possible input disk radius. The largest possible input disk has radius $r_ max =r(B/2-1)=2+(2-12/B)/B$. Note that r is linear and increasing.

Fig. 8.

A gap, bounded in (a) by two outer disks and a bow; in (b) the gap’s base replaces its bow. The distance between the separators is 12 in both scenarios.

Next, we show for both scenarios that separators placed in each gap’s corners prevent the left and right gap boundaries from interfering with the input disks.

Lemma 4

For any $a\in \mathcal A$ it is not possible that a disk with radius $r(a)$ intersects one of the outer disks that bound the gap when placed between the two separators.

For our further construction, we need to prove the following property.

Property 1

Each feasible triple fits inside a gap containing two separators and no infeasible triple does.

It can be easily verified that for $x_1$,$x_2$,$x_3$, $\sum _{i=1}^3 x_i \le B$, it is $2 \sum _{i=1}^3 r(x_i) \le 12$, implying the first part of Property 1. We define $s_i=2r_ min +2\sqrt{(r_ max +r_ min )^2-(r_ max -r_ min )^2}$. In the proof of Lemma 5, we will see that $s_i$ is the horizontal space required for the triple $(r_ min ,r_ max ,r_ min )$, which is the narrowest infeasible triple. Next, let $d(\varepsilon ,x)=\sqrt{(r(x)-\varepsilon /2)^2+(r(x)-r_ min )^2}$ for $\varepsilon > 0$ and $x \in \{ B/4+1,\dots ,B/2-1\}$. We will see that $d(\varepsilon ,x)$ is an upper bound for the distance between the center of a disk D(x) with radius r(x) and the rightmost (leftmost) point of the left (right) separator disk, if the overlap of their horizontal projections is at least $\varepsilon /2$ .

Lemma 5

There exist $\varepsilon >0$ and $\varepsilon _1, \varepsilon _2, \phi \ge 0$ with $\varepsilon =\varepsilon _1+\varepsilon _2$ which satisfy the two conditions: (I) $12+\varepsilon \le s_i$ and (II) $d(\varepsilon _1,x)\le r(x)-\phi \forall x\in \lbrace B/4+1,\dots ,B/2-1\rbrace$. These conditions imply the second part of Property 1 for the simplified scenario.

So far we assumed that the separators are always placed in the corners of the gap. But in fact, separators could be placed in a different location, moreover, there could even be gaps with multiple separators and gaps with zero or one separator. Since the radius of the separators is $r_ min$, which is the radius of the smallest possible input disk, it seems natural to place them in the gaps’ corners to efficiently utilize the horizontal space. However, all feasible disk triples (except (B / 3, B / 3, B / 3)) require less than 12 units of horizontal space. It might therefore be possible to place a feasible disk triple inside a gap together with two disks that are not necessarily separators but input disks with a radius greater than $r_ min$. To account for this problem, we prove the following property.

Property 2

A feasible disk triple can be placed in the gap together with two other disks only if those two disks are separators.

We define $s_f=2r(B/4)+2\sqrt{(r(B/2)+r(B/4))^2-(r(B/2)-r(B/4))^2}$. In the proof of Lemma 6, we will see that $s_f$ is a lower bound for the horizontal space consumption of any feasible triple.

Lemma 6

There exist $\xi >0$ and $\xi _1, \xi _2, \psi \ge 0$ with $\xi =\xi _1+\xi _2$ satisfying the following two conditions: (III) $12-24/B^2+\xi \le s_f$ and (IV) $d(\xi _1,x)\le r(x)-\psi \, \forall x\in \lbrace B/4+1,\dots ,B/2-1\rbrace$. These conditions imply Property 2 for the simplified scenario.

We verify in the proofs of Lemmas 5 and 6 in the full version [11] that choosing $\varepsilon _1,\xi _1=16/B^2$ and $\varepsilon _2,\phi ,\xi _2 ,\psi = 1/B^2$ satisfies our four conditions.

Intuitively, Conditions (I)–(IV) have the following meaning. By (I), the horizontal space consumption of any infeasible triple is greater than 12 by some fixed buffer. By (III), the horizontal space consumption of any feasible triple is very close to 12. Conditions (II) and (IV) imply that if the overlap of the horizontal projections of a separator and an input disk is large enough, the two disks intersect, implying that triples with sufficiently large space consumption can indeed not be placed between two separators.

In the original scenario, consider a straight line directly below the two separators. We call this straight line the gap’s chord, see Fig. 8a. The gap’s chord has a function similar to the base in the simplified scenario. We still want separators to be placed in the gap’s corners. The distance between the rightmost point $p_l$ of the left separator and the leftmost point $p_r$ of the right separator is now allowed to be slightly more than 12. The horizontal space consumption of a disk triple placed on the bow is lower compared to the disk triple being placed on the chord. Moreover, the overlap of the horizontal projections of a separator and an input disk can now be bigger without causing an intersection. However, we show that if the maximum distance d between a gap’s bow and its chord is small enough, the original scenario is sufficiently close to the simplified one, and the four conditions still hold, implying the desired properties.

Lemma 7

In the original scenario, let $d \le 1/4B^2$, and let the amount of free horizontal space in each gap after inserting the two separators in each corner be between 12 and $12 + 1 / 4B^2$. Then, Properties 1 and 2 still hold.

In order to conclude the hardness proof, it therefore remains to describe how to choose the radii for the central and outer disks and how to create the gaps such that $d\le 1/4B^2$.

Recall that we have a central disk $D_c$ with radius $r_c$ and m outer disks with radius $r_o$ which are tightly packed around $D_c$ such that m equal-sized gaps are created. With basic trigonometry we see that $r_c+r_o=r_o/\sin (\pi /m)$ and, therefore, $r_c=r_o/\sin (\pi /m)-r_o$. Clearly, there always exists a value $r_o$ such that the two separator disks can be placed in each gap’s corners and such that the distance between each pair of separators is exactly 12 units. Let $\bar{r_o}$ be this value. Moreover, the maximum distance d between a gap’s bow and its chord is of particular importance, see Fig. 8a. Using the Pythagorean Theorem, it can be calculated to be $d=r_c-(\sqrt{(r_c+r_ min )^2-(6+r_ min )^2}-r_ min )$. The crucial observation is that we do not necessarily need to choose $m=n$. Instead we may choose any $m\ge n$ and thereby decrease d, as long as we make sure that m is still a polynomial in the size of the input or numeric values and that the $m-n$ additional gaps cannot be used to solve an instance which should be infeasible.

Lemma 8

There exist constants $c_1$, $c_3$, $c_4$, such that for $m=B^{c_1}$, $\varepsilon _3=1/B^{c_3}$ and $\varepsilon _4=1/B^{c_4}$, there exist values $\widetilde{r_o}$ for $r_o$ and $\widetilde{r_c}$ for $r_c$, for which it holds $\bar{r_o}< \widetilde{r_o}\le \bar{r_o}+\varepsilon _3$ and $\bar{r_c}< \widetilde{r_c}\le \bar{r_c}+\varepsilon _4$ for $\bar{r_c}= \widetilde{r_o}/ \sin (\pi /m)-\widetilde{r_o}$. The constants can be chosen such that $d \le 1/4B^2$ and such that the amount of free horizontal space in each gap is between $12$ and $12 + 1/4B^2$. Finally, $\widetilde{r_o}$ and $\widetilde{r_c}$ can be computed in polynomial time.

Lemma 3 already showed how to construct an equivalent 3-Partition instance with $3m \ge 3n$ input integers. We can now prove the main result of this section, see [11] for details. Lemmas 3 and 8 show that the construction can be performed in polynomial time. Properties 1 and 2 let us show that a valid distribution of the input and separator disks among the gaps induces a solution of the 3-Partition instance and vice versa.

Theorem 3

The WDC graph recognition problem is (strongly) $\textsf {NP}$-hard even for stars if an arbitrary embedding is allowed.

3.2 Recognizing Embedded Stars with a Weighted Disk Contact Representation

If, however, the order of the leaves around the central vertex of the star is fixed, the existence of a WDC representation can be decided by iteratively placing the outer disks $D_1$, ..., $D_{n-1}$ tightly around the central disk $D_c$. A naive approach tests for collisions with all previously added disks and yields a total runtime of $O(n^2)$. However, this can be improved to O(n) by maintaining a list containing only disks that might be relevant in the future. For more details see the full version [11].

Theorem 4

On a Real RAM, for an embedded, vertex-weighted star $S$ it can be decided in linear time whether $S$ is a WDC graph. A WDC representation respecting the embedding (if one exists) can be constructed in linear time.