Star-Based Separators for Intersection Graphs of $𝒄$-Colored Pseudo-Segments

The celebrated Planar Separator Theorem by Lipton and Tarjan [24] states that any planar graph admits a balanced separator of size $O(\sqrt{n})$. More precisely, for any planar graph $G=(V,E)$ with $n$ nodes there exists a set $S\subseteq V$ of size $O(\sqrt{n})$ whose removal partitions $G$ into components of at most $\frac{2n}{3}$ nodes each. This fundamental tool has been used to develop efficient algorithms for many classic problems on planar graphs.

Geometric intersection graphs – graphs whose nodes correspond to objects in the plane and that have an edge between two nodes iff the corresponding objects intersect – are a generalization of planar graphs that have received widespread attention in computational geometry, graph theory, and parametrized complexity. (For an overview of work in the latter area, we refer the reader to the survey by Xue and Zehavi [28].) Unfortunately, geometric intersection graphs do not admit balanced separators of sublinear size, because they can contain arbitrarily large cliques. This led De Berg et al. [11] to introduce so-called clique-based separators: balanced separators that consist of a small number of disjoint (but potentially large) cliques instead of a small number of nodes. They proved that any disk graph – and more generally, any intersection graph of convex fat objects in the plane – admits a clique-based separator of size $O(\sqrt{n})$. Here the size of a clique-based separator is the number of cliques it consists of. They also showed how to use such clique-based separators to obtain sub-exponential algorithms for various classic graph problems, including Independent Set, Dominating Set, and Feedback Vertex Set. Recently, De Berg et al. [12] showed that intersection graphs of pseudo-disks, and intersection graphs of geodesic disks inside a simple polygon, admit balanced separators consisting of $O(n^{2/3})$ cliques, and Aronov et al. [3] proved that intersection graphs of geodesic disks in any well-behaved metric in the plane admit balanced separators consisting of $O(n^{3/4+\epsilon })$ cliques.

One may wonder if all geometric intersection graphs have sublinear clique-based separators. Unfortunately the answer is no, even for intersection graphs of horizontal and vertical line segments. The problem is that such graphs can contain arbitrarily large bicliques, and $K_{n,n}$ does not admit a sublinear clique-based separator. We therefore introduce biclique-based separators, which are separators consisting of bicliques, and we show that any set of horizontal and vertical segments admits a balanced separator consisting of a small number of bicliques. In fact, our result is stronger (as it uses star graphs in the separator, and not just any biclique) and it applies to a much wider class of intersection graphs, as discussed next.

Let $𝒢=(V,E)$ be an undirected graph with $n$ nodes. A collection $S=\{S_1,\mathrm{\dots }{S}_t\}$ of (not necessarily induced) disjoint subgraphs from $G$ is called a balanced¹¹1In the sequel we will often omit the adjective balanced and simply speak of separators. biclique-based separator for $G$ if it has the following properties:

• $\mathrm{■}$

  Each subgraph $S_i$ is a biclique.

• $\mathrm{■}$

  The removal from $𝒢$ of all subgraphs $S_i$ and their incident edges partitions $𝒢$ into connected components with at most $\frac{2n}{3}$ nodes each.

The size of a biclique-based separator is the number of bicliques it is comprised of. If each biclique $S_i\in S$ is a star, then we call $S$ a star-based separator. Note that the subgraphs $S_i$ in a biclique-based separator (or: in a star-based separator) need not be induced subgraphs of $𝒢$. This is necessary to be able to handle large cliques. To avoid confusion between our new separators that are comprised of bicliques and the traditional separators that are comprised of individual nodes, we will refer to the latter as node-based separators.

We denote the intersection graph induced by a set $V$ of $n$ objects in the plane by ${𝒢}^{\times }[V]$. Thus, the nodes in ${𝒢}^{\times }[V]$ are in one-to-one correspondence with the objects in $V$ and there is an edge between two objects $u,v\in V$ iff $u$ intersects $v$. In Section 2 we prove that a star-based separator of size $O(\sqrt{n})$ exists for the intersection graph of any set $V$ of axis-parallel segments. (The bound on the size of the separator is tight in the worst case.) In fact, we will prove that a star-based separator of size $O(\sqrt{n})$ exists for any set $V$ of pseudo-segments²²2A set $V$ of curves in the plane is a set of pseudo-segments if any two curves in $V$ are either disjoint or intersect in a single point that is a proper crossing (and not a tangency). that is partitioned into subsets $V_1,\mathrm{\dots },V_c$ such that the pseudo-segments from each $V_i$ are disjoint from each other. In other words, each $V_i$ is an independent set in ${𝒢}^{\times }[V]$. We call such a set $V$ a $c$-colored set of pseudo-segments, and we call $V_1,\mathrm{\dots },V_c$ its color classes; see Figure 1(left). Note that a set of axis-parallel segments such that no two segments of the same orientation overlap, is a $2$-colored set of pseudo-segments. More generally, a $c$-oriented set of line segments such that no two segments from the same orientation intersect, is a $c$-colored set of pseudo-segments. Intersection graphs of $c$-oriented segments are often referred to as $c$-dir graphs, and when segments of the same orientation are not allowed to intersect, they are referred to as pure $c$-dir graphs [20, 21]. We show that a star-based separator of size $O(\sqrt{n})$ for a $c$-dir graph can be computed in $O(n\log n)$ time, if the segments which induce this graph are given.

In Section 3 we extend our result to the case where $V$ is a set of $n$ constant-complexity $c$-oriented simple polygons, that is, a set of polygons without holes such that the set of edges of all polygons is a $c$-oriented set. Note that two polygons can intersect without having their boundaries intersect, namely when one polygon is completely contained in the other polygon – this is the main difficulty we need to handle when extending our results to polygons. Finally, in Section 3 we also present a straightforward greedy algorithm that computes a star-based separator of size $O(n^{2/3}{\log }^{2/3}n)$ for any string graph.

A distance oracle for a (potentially weighted) graph $𝒢=(V,E)$ is a data structure that can quickly report the distance between two query nodes $s,t\in V$. Such queries can trivially be answered in $O(1)$ time if we store the distance between any two nodes in a distance table, but this requires $\mathrm{\Omega }(n^2)$ storage. The challenge is to design distance oracles that use subquadratic storage. Unfortunately, this is not possible in general: any distance oracle must use $\mathrm{\Omega }(n^2)$ bits of storage in the worst case, irrespective of the query time [27]. This is even true for distance oracles that approximate distances to within a factor strictly less than $3$. Thus, work on distance oracles concentrated on special graph classes and, in particular, on planar graphs. More than two decades of research culminated in an exact distance oracle for weighted planar graphs that uses $O(n^{1+o(1)})$ storage and has $O({\log }^{2}n)$ query time [9]. For the unweighted case – in other words, if we are interested in the hop-distance – there is a $(1+\epsilon )$-approximate distance oracle with $O(1/{\epsilon }^2)$ query time and $O(n/{\epsilon }^2)$ storage [22]. See the survey by Sommer [26] and the paper by Charalampopoulos et al. [9] for overviews of the existing distance oracles for various graph classes.

For geometric intersection graphs, only few results are known. Gao and Zhang [15], and Chan and Skrepetos [6], provide $(1+\epsilon )$-approximate distance oracles with $O(n\log n)$ storage and $O(1)$ query time for weighted unit-disk graphs. No exact distance oracles that use subquadratic storage and have sublinear query time are known, even for unweighted unit-disk graphs. Very recently, Chang, Gao, and Le [8] presented an almost exact distance-oracle for unit-disk graphs (and, more generally, for intersection graphs of similarly sized, convex, fat pseudodisks) that uses $O(n^{2-1/18})$ storage and that can report the distance between two query nodes, up to an additive error³³3In the most recent arxiv version [7] the error has been reduced to 1. of 2, in $O(1)$ time. Another recent result is by Aronov, De Berg, and Theocharous [3], who presented an almost exact distance oracle that uses clique-based separators. For intersection graphs of geodesic disks in the plane, their oracle uses $O(n^{7/4+\epsilon })$ storage, has $O(n^{3/4+\epsilon })$ query time, and can report the hop-distance between two query points up to an additive error of $1$. For Euclidean disks, the storage and preprocessing would be $O(n\sqrt{n})$ and $O(\sqrt{n})$, respectively. As we explain later, their approach also works with biclique-based separators; the only difference is that the additive error increases from $1$ to $2$. Thus, we obtain an almost exact distance oracle for intersection graphs of $c$-colored pseudo-segments with $O(n\sqrt{n})$ storage and $O(\sqrt{n})$ query time. This is, to the best of our knowledge, the first almost exact distance oracle for intersection graphs of non-disk-like objects.

Recall that a contact graph is the intersection graph of a set of interior-disjoint objects. Contact graphs of curves are known to be planar if no four objects meet in a common point [19, Lemma 2.1]. Our strategy to construct a star-based separator $S$ for ${𝒢}^{\times }[V]$ consists of the following steps, illustrated in Figure 1 and explained in more detail later.

Step 1.

We partition each segment in $V$ into fragments. Some fragments will be active, while others will be inactive. This partition will be such that active segments do not cross each other, although they may touch.

Step 2.

Let $\mathscr{H}$ be the contact graph on the active segments. We construct a separator $S_{\mathscr{H}}$ on $\mathscr{H}$, using a suitable weighting scheme on the nodes of $\mathscr{H}$. Because $\mathscr{H}$ is planar, constructing the separator can be done using the Planar Separator Theorem.

Step 3.

We use $S_{\mathscr{H}}$ to construct our star-based separator $S$ for ${𝒢}^{\times }[V]$. For a fragment $f$, let $\mathrm{seg}(f)\in V$ denote the segment containing $f$. Intuitively, we want to put a star into $S$ for each fragment $f$ in the separator $S_{\mathscr{H}}$, namely, the star consisting of the segment $\mathrm{seg}(f)$ as well as all other segments intersecting $\mathrm{seg}(f)$. For technical reasons, however, we actually have to put a slightly larger collection of stars into $S$.

To make this strategy work, we need to control the size of the contact graph $\mathscr{H}$. More precisely, to obtain a star-based separator of size $O(\sqrt{n})$, the size of $\mathscr{H}$ needs to be $O(n)$. Thus we cannot, for example, cut each segment into fragments at its intersection points with all other segments and make all the resulting fragments active. On the other hand, if we ignore certain parts of the segments by making them inactive, we miss certain intersections and we run the risk that our final set of stars is no longer a valid separator. Next, we describe how to overcome these problems by carefully creating the active fragments.

To construct the active fragments that form the nodes in our contact graph $\mathscr{H}$, we will go over the subsets $V_1,\mathrm{\dots },V_c$ one by one. We denote the active and inactive fragments created for a subset $V_i$ by $F_i$ and ${\overline{F}}_i$, respectively. For $1⩽i⩽c$, we define $F_{⩽i}:=F_1\cup \mathrm{\cdots }\cup F_i$, and we define similarly.

Handling the first subset $V_1$ is easy: we simply define $F_1:=V_1$. In other words, each segment in $V_1$ becomes a single fragment, and all these fragments are active.

Now consider a subset $V_i$ with $i>1$. Each segment $v\in V_i$ is partitioned into one or more fragments by cutting it at every intersection point of $v$ with an active fragment . Let $X_i$ be the set of fragments thus created. There are two types of fragments in $X_i$: fragments $f$ that contain an endpoint of the segment $v\in V_i$ contributing $f$ – there are at least one and at most two of these fragments per segment $v\in V_i$ – and fragments that do not contain such an endpoint. We call fragments of the former type end fragments and fragments of the latter type internal fragments. Note that an internal fragment has its endpoints on two distinct active fragments . We then say that $f$ connects $g$ and $g^{\prime }$.

Now that we have defined $X_i$, we need to decide which fragments in $X_i$ become active. To avoid making too many fragments active, we will partition $X_i$ into equivalence classes, and we will activate only one fragment from each equivalence class. To define the equivalence classes we first define, for two internal fragments $f,f^{\prime }\in X_i$ that connect the same pair of fragments , a region $Q(f,f^{\prime },g,g^{\prime })$, as follows; see Figure 2(i) for an illustration.

First, suppose that the segments $g$ and $g^{\prime }$ do not touch each other, as in the left part of Figure 2(i). Thus, ${ℝ}^2\setminus (g\cup g^{\prime })$ is a single, unbounded region with two holes, namely $g$ and $g^{\prime }$. The fragment $f$ connects these two holes, and so ${ℝ}^2\setminus (g\cup g^{\prime }\cup f)$ is still a single unbounded region, but now with one hole. Removing $f^{\prime }$ from this region splits it into two regions, one bounded and one unbounded. We define $Q(f,f^{\prime },g,g^{\prime })$ to be the bounded region. Now suppose that $g$ and $g^{\prime }$ touch each other, say at an endpoint of $g$. We slightly shrink $g$ at the point where it touches $g^{\prime }$, and then define $Q(f,f^{\prime },g,g^{\prime })$ as above. Note that in this case $Q(f,f^{\prime },g,g^{\prime })$ may consist of one or two bounded regions, if we undo the shrinking process; see the middle and right part in Figure 2(i). We can now define the equivalence classes.

The following lemma shows that $\equiv$ is indeed an equivalence relation.

It is clear that $\equiv$ is reflexive and symmetric. It remains to show that if $f_1\equiv f_2$ and $f_2\equiv f_3$, then $f_1\equiv f_3$. Let $g,g^{\prime }$ be the fragments connected by $f_1,f_2,f_3$. We can assume that $g$ and $g^{\prime }$ do not touch; otherwise, as before, we can shrink one of the fragments so that the arguments below still apply. It is instructive to view $g$ and $g^{\prime }$ as being slightly inflated so that they become closed curves and no longer have two “sides”. We then see that, from a topological point of view, the situation is always as in Figure 2(ii): two of the fragments, $f_j$ and $f_{\mathrm{\ell }}$, are incident to the unbounded face, while the third fragment $f_k$ is not. Thus, if we define $Q_{jk}:=Q(f_j,f_k,g,g^{\prime })$ and we define $Q_{k\mathrm{\ell }}$ and $Q_{j\mathrm{\ell }}$ similarly, then $Q_{j\mathrm{\ell }}=Q_{jk}\cup Q_{k\mathrm{\ell }}$. This implies that, no matter which of the three fragments $f_j,f_k,f_{\mathrm{\ell }}$ is $f_2$, we always have $Q_{13}\subseteq Q_{12}\cup Q_{23}$. Since $Q_{12}$ and $Q_{23}$ do not contain endpoints of segments in $V$ if $f_1\equiv f_2$ and $f_2\equiv f_3$, neither does $Q_{13}$. Thus, $f_1\equiv f_3$. $◀$

We now partition $X_i$ into equivalence classes according to the relation $\equiv$ defined above. For each equivalence class, we make an arbitrary fragment $f\in X_i$ from that class active and put it into $F_i$; the other fragments from that equivalence class are made inactive and put into ${\overline{F}}_i$. Note that end fragments are always active, since they do not connect a pair of fragments from and thus cannot be equivalent to any other fragment.

Let $F:=F_1\cup \mathrm{\cdots }\cup F_c$ be the set of active fragments created in Step 1, and let $\overline{F}:={\overline{F}}_1\cup \mathrm{\cdots }\cup {\overline{F}}_c$ be the inactive fragments. We define $\mathscr{H}=(F,E_{\mathscr{H}})$ to be the contact graph of $F$. More precisely, for two fragments $f,f\in F$ we put the edge $(f,f^{\prime })$ in $E_{\mathscr{H}}$ iff $f$ and $f^{\prime }$ are in contact – that is, $f\cap f^{\prime }\ne \mathrm{\varnothing }$ – and they do not belong⁴⁴4Since we do not put an edge between fragments belonging to the same segment, even if these fragments touch, $\mathscr{H}$ is formally speaking not a contact graph, but we permit ourselves this abuse of terminology. to the same segment in $V$; see Figure 1. Because of our general position assumption, no three fragments from different segments meet in a point, and therefore $\mathscr{H}$ is planar [19, Lemma 2.1]. From now on, with a slight abuse of notation, we will not make a distinction between the nodes in $\mathscr{H}$ and the corresponding fragments in $F$.

We now wish to create a separator $S_{\mathscr{H}}$ for $\mathscr{H}$. In Step 3 we will use $S_{\mathscr{H}}$ to create a separator $S$ for ${𝒢}^{\times }[V]$. To ensure that $S$ will be balanced, we will put weights on the nodes in $\mathscr{H}$ and use a weighted version of the Planar Separator Theorem, as described next.

For each segment $s\in V$, we designate one of its end fragments – recall that end fragments are always active – as its representative fragment. We give all representative fragments a weight of $\frac{1}{n}$, and all other fragments a weight of $0$. Note that the total weight of the fragments in $F$ is $1$. We apply the weighted separator theorem given below to $\mathscr{H}$. This gives us a separator $S_{\mathscr{H}}$, and parts $A_{\mathscr{H}},B_{\mathscr{H}}\subseteq F\setminus S{}_{\mathscr{H}}$ such that there are no edges between $A_{\mathscr{H}}$ and $B_{\mathscr{H}}$.

Using the separator $S_{\mathscr{H}}$ created in Step 2, we now create our star-based separator $S$ for the intersection graph ${𝒢}^{\times }[V]$. We do this by putting one or three stars into $S$ for each fragment $f\in S_{\mathscr{H}}$, as follows. For a segment $s\in V$, define $\mathrm{star}(s)$ to be the subgraph of ${𝒢}^{\times }[V]$ consisting of $s$ and all its incident edges. Thus, the nodes in $\mathrm{star}(s)$ are the segment $s$ itself plus the segments $s^{\prime }\in V$ that intersect $s$.

• $\mathrm{■}$

  If $f\in S_{\mathscr{H}}$ is an end fragment then we put $\mathrm{star}(\mathrm{seg}(f))$ into $S$.

• $\mathrm{■}$

  If $f\in S_{\mathscr{H}}$ is an internal fragment then let $g,g^{\prime }\in F$ be the pair of active fragments connected by $f$. We put $\mathrm{star}(\mathrm{seg}(f))$, $\mathrm{star}(\mathrm{seg}(g))$, and $\mathrm{star}(\mathrm{seg}(g^{\prime }))$ into $S$.

Note that multiple copies of the same star can be added to $S$. We remove these duplicates to ensure that all star graphs in $S$ have unique centers. It can still be the case that several stars in $S$ contain the same node. To make the stars pairwise disjoint, we therefore remove non-center nodes until every node appears in at most one star in $S$.

We now show that the construction described above yields a balanced separator of the required size. This requires proving two things: the separation property, namely that the removal of $S$ partitions ${𝒢}^{\times }[V]$ into components of size at most $\frac{2n}{3}$, and the size property, namely that $S$ consists of $O(\sqrt{n})$ stars.

To prove the separation property, it suffices to show that $V\setminus S$ can be partitioned⁵⁵5Formally, we should have written $V\setminus \bigcup S$ instead of $V\setminus S$, since $S_{\mathscr{H}}$ is a set of stars and not a set of nodes, but we prefer the simpler (though technically incorrect) notation. into subsets $A$ and $B$ such that $|A|⩽\frac{2n}{3}$ and $|B|⩽\frac{2n}{3}$, and such that no segment in $A$ intersects any segment in $B$.

We define the sets $A$ and $B$ as follows. For each segment $v\in V$ not contained in a star in $S$ we look at its representative fragment $f_v$. Note that $f_v$ must be contained in either $A_{\mathscr{H}}$ or $B_{\mathscr{H}}$, since $f_v\in S_{\mathscr{H}}$ would imply that $v$ is contained in a star in $S$. If $f_v\in A_{\mathscr{H}}$ then we add $v$ to $A$, else we add $v$ to $B$. The value $\frac{|A|}{n}$ can be at most the total weight of fragments in $A_{\mathscr{H}}$, and a similar statement holds for $B$. Hence, the next observation follows from the fact that $S_{\mathscr{H}}$ is a balanced separator.

The more challenging part is to show that no segment in $A$ intersects any segment in $B$. We will need the following lemma. Recall that the segment set $V$ is partitioned into color classes $V_1,\mathrm{\dots },V_c$, which we handled one by one to create the set $F$ of active fragments.

We prove the lemma under the assumption that $v\in A$; the proof for $v\in B$ is analogous. Let $f_v$ be the representative fragment of $v$. Because $v\in A$, we have $f_v\in A_{\mathscr{H}}$. We will define sets $Z_1,Z_2,Z_3$ that contain the active fragments for which conditions (i), (ii), and (iii) hold, respectively, and then argue that the lemma holds for each of the three sets.

Let $f_v^{\prime }$ be the other end fragment of $v$, and let $Z_1=\{g_1,\mathrm{\dots },g_k\}$ be the ordered set of fragments from that we cross as we trace $v$ from $f_v$ to $f_v^{\prime }$; see Figure 3. It is possible that $f_v^{\prime }$ does not exist, in this case $Z_1$ is empty.

Note that every pair $g_j,g_{j+1}\in Z_1$ is connected by an active or inactive fragment of $v$, which we denote by $f_j$. We now define $Z_2,Z_3$ as follows.

• $\mathrm{■}$

  $Z_2$ contains the fragments $f_j$ that are active plus the end fragments $f_v$ and (if it exists) $f_v^{\prime }$. Thus, $Z_2$ simply contains all active fragments of $v$.

• $\mathrm{■}$

  $Z_3$ contains, for each inactive fragment $f_j$, the unique equivalent active fragment $f_j^{\prime }\in F_i$.

It is easily checked that the sets $Z_1,Z_2,Z_3$ indeed contain exactly those fragments for which conditions (i), (ii), and (iii) hold, respectively. We will now prove that all fragments in $Z_1\cup Z_2\cup Z_3$ are in $A_{\mathscr{H}}$. To this end, observe that the fragments in $Z_1\cup Z_2\cup Z_3$ correspond to nodes in $\mathscr{H}$ that form a path $\pi$ starting at $f_v$ and ending at $f_v^{\prime }$, as illustrated in Figure 3. Recall that $f_v\in A_{\mathscr{H}}$. Now assume for a contradiction that there is a fragment $f\in Z_1\cup Z_2\cup Z_3$ that is in $B_{\mathscr{H}}\cup S_{\mathscr{H}}$. Because there are no edges between $A_{\mathscr{H}}$ and $B_{\mathscr{H}}$, this means there must be a fragment $f^{\ast }$ on the subpath of $\pi$ from $f_v$ to $f$ that is an element of the separator $S_{\mathscr{H}}$. If $f^{\ast }\in Z_1\cup Z_2$ then $v\in \mathrm{star}(\mathrm{seg}(f^{\ast }))$, which contradicts that $v\in A$. Otherwise $f^{\ast }\in Z_3$ and $f^{\ast }$ connects two fragments $g_j,g_{j+1}\in Z_1$. Since $f^{\ast }\in S_{\mathscr{H}}$, this implies that $\mathrm{star}(\mathrm{seg}(g_j))$ is a star in $S$. Because $v\in \mathrm{star}(\mathrm{seg}(g_j))$, this again contradicts that $v\in A$. $◀$

We can now prove that ${𝒢}^{\times }[V]$ does not contain edges between nodes in $A$ and nodes in $B$.

Assume for a contradiction that $a\in A$ and $b\in B$ intersect. Let $f_a\subseteq a$ and $f_b\subseteq b$ be the fragments containing the intersection point. We distinguish three cases.

• $\mathrm{■}$

  Both $f_a$ and $f_b$ are active. Then $f_a$ and $f_b$ satisfy condition (ii) of Lemma 2, and so $f_a\in A_{\mathscr{H}}$ and $f_b\in B_{\mathscr{H}}$. Because $f_a$ and $f_b$ are active and intersect, $(f_a,f_b)$ is an edge in $\mathscr{H}$. But then $S_{\mathscr{H}}$ would not be a proper separator, and we reach a contradiction.

• $\mathrm{■}$

  Both $f_a$ and $f_b$ are inactive. Let $f_a\in {\overline{F}}_i$ and $f_b\in {\overline{F}}_j$, and assume without loss of generality that $i⩽j$. Because $a$ and $b$ intersect and segments from the same color class are disjoint, we cannot have $i=j$. Hence, . Because $f_a$ is inactive, it must be an internal fragment that connects some fragments . Thus, $g,g^{\prime }$ satisfy condition (i) of Lemma 2, with $a$ playing the role of $v$, which implies that $g,g^{\prime }\in A_{\mathscr{H}}$. Let $f_a^{\prime }\in F_i$ be the active fragment that is equivalent to $f_a$. Then $f_a^{\prime }$ satisfies condition (iii) from Lemma 2 and so $f_a^{\prime }\in A_{\mathscr{H}}$. The fragments $f_a,f_a^{\prime },g,g^{\prime }$ enclose some region $Q$. The segment $b$ intersects $f_a$ so it is partly contained in $Q$; see Figure 4 for an illustration of the possibilities for $f_b$ entering $Q$.

  It cannot have an endpoint in $Q$, because $f_a$ and $f_a^{\prime }$ are equivalent. Segment $b$ cannot intersect $f_a$ twice, because $V$ is a collection of pseudo-segments. It follows that $b$ must intersect $f_a$, $g$ or $g^{\prime }$. Now observe that $f_a$, $g$ and $g^{\prime }$ are all fragments in . This implies that the fragment that intersects $b$ satisfies condition (i) from Lemma 2, with $b$ playing the role of $v$. But then the intersected fragment would be in $B_{\mathscr{H}}$, contradicting that $A_{\mathscr{H}}$ and $B_{\mathscr{H}}$ are disjoint.

• $\mathrm{■}$

  One of the fragments $f_a,f_b$ is active and one is inactive. Assume wlog that $f_a$ is inactive and $f_b$ is active. Let $f_a\in {\overline{F}}_i$ and $f_b\in F_j$. Because $a$ and $b$ intersect, we have $i\ne j$. If then the arguments from the previous case can be used to obtain a contradiction – indeed, these arguments did not use that $f_b$ is inactive. If $i>j$ then . Also note that $a$ intersects $f_b$. But then $f_b$ satisfies condition (i) from Lemma 2, with $a$ playing the role of $v$. It follows that $f_b\in A_{\mathscr{H}}$, which contradicts that $A_{\mathscr{H}}$ and $B_{\mathscr{H}}$ are disjoint.

We have reached a contradiction in each case, thus proving the lemma. $◀$

Because we add at most three stars to $S$ per fragment in $S_{\mathscr{H}}$, it suffices to bound the size of $S_{\mathscr{H}}$ to prove the size property. From Lemma 2 it follows that $|S_{\mathscr{H}}|=O(\sqrt{|F|})$. The next lemma bounds $|F|$.

We first bound $|F_i|$, the number of active fragments created for the segments in $V_i$, in terms of the number of active fragments created for .

The set $F_i$ contains at most $2\cdot |V_i|$ end fragments. The internal fragments in $F_i$ connect two fragments from . We denote the set of these internal fragments by $F_i^{\mathrm{int}}$. Now consider the multi-graph $𝒢$ defined as follows.

• $\mathrm{■}$

  For each fragment in , we add a node to $𝒢$.

• $\mathrm{■}$

  For each fragment in $F_i^{\mathrm{int}}$, we add an edge to $𝒢$ between the fragments from that it connects.

• $\mathrm{■}$

  For each endpoint of a segment in $V_{⩾i}$ we add a singleton node to $𝒢$. (Observe that the endpoints of segments in lie on an end fragment in , which is already a node in $𝒢$.)

Now consider the obvious drawing of $𝒢$, where the nodes are drawn as fragments of or as points, and the edges are drawn as fragment in $F_i^{\mathrm{int}}$. Recall that two active fragments can touch, but they never cross. By continuously shrinking the fragments in $F_{⩽i}$ and deforming the fragments of $F_i^{\mathrm{int}}$ appropriately, we can therefore create a plane drawing of $𝒢$. That is, we can create a drawing of $𝒢$ in which the nodes are points and the edges are pairwise disjoint curves connecting their endpoints. See Figure 5 for an example of this deformation. For reasons that will become clear shortly, we augment $𝒢$ with one additional singleton node $u_{\mathrm{\infty }}$, which we place in the unbounded face of $𝒢$.

The graph $𝒢$ is a multi-graph because $F_i^{\mathrm{int}}$ can contain multiple fragments connecting the same pair of fragments . Let $g,g^{\prime }\in F_i^{\mathrm{int}}$ be two such fragments. The reason that we added both $g$ and $g^{\prime }$ to $F_i^{\mathrm{int}}$ is that $g$ and $g^{\prime }$ were not equivalent. Hence, the region $Q(f,f^{\prime },g,g^{\prime })$ contains an endpoint belonging to some segment $v\in V$. The deformation process that turns each node the drawing of $𝒢$ into a point can be done in such a way that this property is maintained. Thus, after the deformation we have a plane drawing of $𝒢$ in which for any two edges $g,g^{\prime }$ that connect the same pair of nodes, there is a node inside the deformed region $Q(f,f^{\prime },g,g^{\prime })$. Because of the additional node $u_{\mathrm{\infty }}$, we are also guaranteed to have at least one node outside this region. A plane multi-graph with this property is called a thin graph. It is known [1, Lemma 5] that the standard inequality $(\text{\#\hspace{0.17em}edges})⩽3\cdot (\text{\#\hspace{0.17em}nodes})-6$ that holds for planar graphs (with at least three vertices) also holds for thin graphs. Hence, . $\mathrm{⊲}$

Note that $|F_1|=|V_1|$ and $|V_i|⩽n$ for all $i$. Hence, the claim above gives us the recurrence with $|F_{⩽1}|⩽n$. This gives $|F_{⩽i}|⩽\left(\frac{n}{4}+\frac{8n-3}{12}\right)\cdot 4^i-\frac{8n-3}{3}$. Plugging in $i=c$ gives $|F|=|F_{⩽c}|=O(n\cdot 4^c)$, which proves the lemma. $◀$

Since $c$, the number of color classes, is a constant, we obtain the following corollary.

So far we have considered input sets $V$ where the segments are unweighted. To create a separator for $c$-oriented polygons, which we will do in the next section, we need a separator for weighted segments. Fortunately it is straightforward to adapt the construction described above to the weighted setting – we only need to change the weighting scheme we used in Step 2 of the construction. More precisely, instead of assigning a weight $\frac{1}{n}$ to the representative fragment of a segment $v$, we assign $\mathrm{weight}(v)/{\sum }_{u\in V}\mathrm{weight}(u)$ to the representative.

If we assume that the appropriate elementary operations on the pseudo-segments – computing the intersection point of two pseudo-segments, for instance, or determining if a point lies inside some region $Q(f,f^{\prime },g,g^{\prime })$ – can be performed in $O(1)$ time, that then a brute-force implementation of the algorithm presented above runs in polynomial time. More interestingly, for $c$-oriented line segments, the algorithm can be implemented to run in $O(n\log n)$ time, as shown in the full version of this paper. We obtain the following theorem.

Arikati et al. [2] presented a simple distance oracle for planar graphs, using node-based separators. Aronov, De Berg, and Theocharous [3] observed that the approach can be adapted to work with clique-based separators, as follows. Let $𝒢=(V,E)$ be the graph for which we want to construct a distance oracle.

• $\mathrm{■}$

  Construct a clique-based separator $S$ for $𝒢$, and let $A,B\subseteq V\setminus S$ be the two parts of the partition given by $S$. For each node $v\in V$ and each clique $C\in S$, store the distance $d(v,C):=\min \{d(v,u):u\in C\}$, where $d(u,v)$ denotes the hop-distance from $s$ to $t$ in $𝒢$.

• $\mathrm{■}$

  Recursively construct distance oracles for the subgraphs induced by the parts $A$ and $B$.

Now suppose we want to answer a distance query with nodes $s,t\in V$. Let $d^{\ast }:=\min \{d(s,C)+d(t,C):C\in S\}$. If $s$ and $t$ do not lie in the same part – that is, we do not have $s,t\in A$ or $s,t\in B$ – then we report $d^{\ast }$. Otherwise, $s$ and $t$ lie in the same part of the partition, say $A$. Then we report the minimum of $d^{\ast }$ and the distance we obtain by querying the recursively constructed oracle for $A$.

This distance oracle uses $O(n\cdot s(n))$ storage, where $s(n)$ is the size of the separator, and it has $O(s(n))$ query time, assuming $s(n)=\mathrm{\Omega }(n^{\beta })$ for some constant $\beta >0$. The reported distance is either the exact distance $d(s,t)$, or it is $d(s,t)-1$. The additive error of $1$ is because we do not know if $s$ and $t$ can reach the same node of some clique $C$ with paths of length $d(s,C)$ and $d(t,C)$, respectively – we may have to use an edge inside $C$ to connect these paths. We observe that the same approach can be used in combination with star-based (or biclique-based) separators. The only difference is that we now get an additive error of at most $2$, because we may need two additional edges inside a star (or biclique) in the separator. We obtain the following result.

Let $𝒫=\{P_1,\mathrm{\dots },P_n\}$ be a collection of $c$-oriented simple polygons, each with a constant number of edges, where $c$ is a fixed constant. The idea is to create a weighted collection $V$ of segments to which we can apply Theorem 9, and then use the resulting separator $S_V$ to construct a separator $S$ for ${𝒢}^{\times }[𝒫]$. The set $V$ is created as follows.

• $\mathrm{■}$

  First, we add each side of every polygon $P_i\in 𝒫$ to $V$. For each polygon $P_i$, we pick an arbitrary side as its representative side, which we give weight $\frac{1}{n}$; other sides of $P_i$ are given weight $0$.

• $\mathrm{■}$

  Second, to handle the containment of polygons within other polygons, we add so-called containment segments to $V$. These segments will always have weight $0$. Let $\varphi$ be an orientation that is not used by any segment in $V$. For each polygon $P_i$ let ${𝒞}_i\subseteq 𝒫$ be the set of polygons that fully contain $P_i$. Take a point $x_i\in P_i$, and let ${\rho }_i$ be a ray emanating from $x_i$ and with orientation $\varphi$. For each $P_j\in {𝒞}_i$, let $y_j$ be the point where ${\rho }_i$ leaves $P_j$ for the first time. Define $x_i^{\prime }$ to be the last such point $y_{j^{\ast }}$. We now add $x_i{x}_i^{\prime }$ as a containment segment to $V$. Note that the containment segment $x_i{x}_i^{\prime }$ intersects the boundaries of all polygons in ${𝒞}_i$. Moreover, $x_i{x}_i^{\prime }$ is completely contained in $P_{j^{\ast }}$. Figure 6 shows examples of containment segments.

Clearly, we can partition $V$ into color classes $V_1,\mathrm{\dots },V_{c+1}$ based on the orientation of the segments. We let $V_1$ contain the segments of orientation $\varphi$, which will be important later. The total weight of the segments is $1$, so we can apply Theorem 9. Let $S_V$ be the resulting separator for ${𝒢}^{\times }[V]$, and let $A_V$ and $B_V$ be the two parts of weight at most $\frac{2}{3}$ into which $S_V$ splits $V\setminus S_V$. We construct a separator $S$ and parts $A,B$ for ${𝒢}^{\times }[𝒫]$ as follows.

For each star in $S_V$ we consider its center $v$. If $v$ is a side of a polygon $P_i\in 𝒫$ then we add $\mathrm{star}(P_i)$ to $S$, where $\mathrm{star}(P_i)$ is the subgraph of ${𝒢}^{\times }[𝒫]$ consisting of $P_i$ and its incident edges. If $v$ is a containment segment $x_i{x}_i^{\prime }$ that we generated for polygon $P_i\in 𝒫$, then let $P_j$ be the polygon enclosing $P_i$ such that $x_i^{\prime }\in \partial P_j$. We add $\mathrm{star}(P_j)$ to $S_P$. As before, we remove duplicate stars and we remove polygons from stars to ensure that each polygon is in at most one star. To create the parts $A,B$, we consider the representative sides of the polygons $P_i\in 𝒫$ that are not in a star in $S$. If the representative side is in $A_V$, then we put $P_i$ in part $A$; otherwise we put $P_i$ in part $B$.

Proving the size property, namely that $|S|=O(\sqrt{n})$, is easy. Indeed, we put $O(1)$ sides and one containment segment per polygon into $V$. Hence, $|V|=O(n)$ and thus $|S|=|S_V|=O\left(\sqrt{n}\right)$. It remains to prove the separation property.

Since the total weight of $A_V$ and of $B_V$ are both at most $\frac{2}{3}$ and each representative side has weight $\frac{1}{n}$, it follows that $|A|⩽\frac{2n}{3}$ and $|B|⩽\frac{2n}{3}$. Next, we prove that there are no edges from $A$ to $B$ in ${𝒢}^{\times }[𝒫]$. We need the following lemma.

First consider the case $P_i\in A$. Suppose for a contradiction that not all sides of $P_i$ are in $A_V$. Hence, $P_i$ has a side $s\in S_V$ or a side $s^{\prime }\in B_V$. We claim that in the latter case $P_i$ must also have a side $s\in S_V$. To see this, consider the representative side $s_i$ of $P_i$. Note that $s_i\in A_V$ since we put $P_i$ into $A$. Also note that there is a path in ${𝒢}^{\times }[V]$ connecting $s^{\prime }$ to $s_i$ – the nodes on this path correspond to the sides of $P_i$ that we encounter as we traverse $\partial P_i$ from $s^{\prime }$ to $s_i$ in, say, clockwise order. Since $s_i\in A_V$ and $s^{\prime }\in B_V$, one of the nodes on this path must be in $S_V$ and be a side of $P_i$. This establishes our claim.

It remains to prove that if $P_i$ has a side $s$ in $S_V$, then $P_i\in S$. If $s$ is the center of a star in $S_V$, then by construction $P_i$ is the center of a star in $S$. If $s$ is a non-center node in some $\mathrm{star}(s^{\prime })\in S_V$ we distinguish two cases. If $s^{\prime }$ is a side of some polygon $P_j$, then $P_j$ intersects $P_i$ and $S$ contains $\mathrm{star}(P_j)$. Consequently, $P_i$ is a non-center node in $\mathrm{star}(P_j)$, thus $P_i\in S$. If $s^{\prime }$ is a containment segment $x_j{x}_j^{\prime }$ where $x_j^{\prime }$ lies on some polygon $P_k$, then $P_k$ intersects $P_i$ because $x_j{x}_j^{\prime }$ is fully contained in $P_k$. Because $\mathrm{star}(s^{\prime })\in S_V$ it follows that $\mathrm{star}(P_k)\in S$, and thus $P_i\in S$. We have reached a contradiction in all cases. We conclude that all sides of $P_i$ are in $A_V$.

Now consider the case $P_i\in B$. We can follow the proof for the case $P_i\in A$ if the representative side $s_i$ of $P_i$ is in $B_V$. This must indeed be the case: we cannot have $s_i\in A_V$ because then we would have put $P_i$ into $A$, and $s_i$ cannot be a node in a star in $S_V$ because then $P_i$ would have been in a star in $S$, as has been shown above. Hence, the lemma is also true if $P_i\in B$. $◀$

We can now prove that there are no edges from $A$ to $B$ in ${𝒢}^{\times }[𝒫]$.

Suppose for a contradiction that $P_a$ and $P_b$ intersect. We distinguish two cases.

• $\mathrm{■}$

  The boundaries of $P_a$ and $P_b$ intersect. Let $s$ and $s^{\prime }$ be the sides of $P_a$ and $P_b$ that intersect. Because $P_a\in A$ we have $s\in A_V$ by Lemma 3. Similarly, we have $s^{\prime }\in B_V$. But this contradicts that $S_V$ is a separator for ${𝒢}^{\times }[V]$ with parts $A_V,B_V$.

• $\mathrm{■}$

  The boundaries of $P_a$ and $P_b$ do not intersect. Assume wlog that $P_a\subset P_b$. Consider the containment segment $s=x_a{x}_a^{\prime }$. By construction of the containment segments, polygon $P_b$ has a side $s^{\prime }$ that intersects $s$. Recall that the containment segments were put into the set $V_1$ that was handled first by the algorithm from the previous section. Hence, there will be a fragment $f\in F$ that is identical to $s$. Let $i>1$ be such that $s^{\prime }\in V_i$. Then $f$ satisfies condition (i) of Lemma 2, with $s^{\prime }$ playing the role of $v$. Since $s^{\prime }$ is a side of $P_b\in B$, we have $s^{\prime }\in B_V$ by Lemma 3. Thus, Lemma 2 implies that $s=f\in B_V$.

  Similarly there exists a side $s^{\prime \prime }$ that is part of $P_a$ that intersects $s$. From Lemma 3 it follows $s^{\prime \prime }\in A_V$. It must be that $s^{\prime \prime }\in V_j$ for some $j>1$. Then $f$ also satisfies condition (i) of Lemma 2 with $s^{\prime \prime }$ playing the role of $v$, so that $s=f\in A_V$. But then the sets $A_V$ and $B_V$ are not disjoint, which contradicts that $S_V$ is a separator.

$◀$

Putting everything together, we obtain the following theorem. The runtime guarantee for computing the separator is proven in the full version.

A string graph is the intersection graph of a set $V$ of curves in the plane [14] – no conditions are put on the curves and, in particular, any two curves in $V$ can intersect arbitrarily many times. (But note that there is still at most one edge between the corresponding nodes in ${𝒢}^{\times }[V]$.) It is known that for any set $U$ of connected regions in the plane, there is a set $V$ of strings such that ${𝒢}^{\times }[U]$ and ${𝒢}^{\times }[V]$ are isomorphic [23]. Thus, string graphs are the most general type of intersection graphs of connected regions in the plane.

Matoušek [25] proved that any string graph with $n$ nodes and $m$ edges has a (node-based) separator of size $O(\sqrt{m}\log m)$.⁶⁶6A paper by Lee [23] claims that a separator of size $O(\sqrt{m})$ exists for string graphs, but Bonnet et al. [29] note that there is an error in this paper. It is not yet known if the proof can be repaired. Using this result we can obtain a star-based separator of sublinear size for a string graph ${𝒢}^{\times }[V]$ using the following simple two-stage process.

• $\mathrm{■}$

  Stage 1: As long as there is a node $v\in V$ of degree at least $n^{1/3}/{\log }^{2/3}n$, remove $\mathrm{star}(v)$ from ${𝒢}^{\times }[V]$ and add it to the separator. This puts at most $O(n^{2/3}{\log }^{2/3}n)$ stars into the separator.

• $\mathrm{■}$

  Stage 2: Construct a node-based separator on the remaining string graph, using Matoušeks method [25] and put these nodes as singletons into the separator. Since the maximum degree after Stage 1 is $O(n^{1/3}/{\log }^{2/3}n)$, the remaining graph has $O(n^{4/3}/{\log }^{2/3}n)$ edges. Hence, in Stage 2 we put $O\left(\sqrt{\frac{n^{4/3}}{{\log }^{2/3}n}}\cdot \log \left(\frac{n^{4/3}}{{\log }^{2/3}n}\right)\right)=O\left(n^{\frac{2}{3}}{\log }^{\frac{2}{3}}n\right)$ stars into the separator.

By using the star-based separator exactly as in Section 2, this yields the following.

Recall that the distance oracle of Aronov, De Berg and Theocharous [12] for geodesic disks in the plane has $O(n^{7/4+\epsilon })$ storage and $O(n^{3/4+\epsilon })$ query time. Thus the distance oracle in Proposition 3 is more general (as it can handle any string graph), has better storage, and better query time. The only downside is that the additive error in our distance oracle is at most 2, while for their oracle it is at most 1.