Circle Graphs Can Be Recognized in Linear Time

A word over an alphabet $\mathrm{\Sigma }$ is a finite sequence of letters of $\mathrm{\Sigma }$. If $A$ is a word over $\mathrm{\Sigma }$, then $A^r$ denotes its reversal (the ordering between the letters of $A$ has been reversed). The concatenation between two words $A$ and $B$ over $\mathrm{\Sigma }$ is a word over $\mathrm{\Sigma }$ denoted $AB$. A subsequence $F$ of consecutive letters in a word $A$ is called a factor of $A$.

A circular word $C$ over $\mathrm{\Sigma }$ is a circular sequence of letters of $\mathrm{\Sigma }$. It can be represented by a word by considering that the first letter follows the last letter. Observe that such a representation fixes an arbitrary first letter. So if a circular word $C$ is represented by the word $AB$, then $BA$ also represents $C$. To denote that equivalence, we write $C\sim AB\sim BA$. Observe that, if $C$ a circular word represented by the word $A$, that is $C\sim A$, then the reversal of $C$ is $C^r\sim A^r$. The notion of factor naturally extends to circular words: $F$ is a factor of $C$ if there exists a word $A$ such that $C\sim A$ and $F$ is a factor of $A$.

Unless specified, we will assume that every graph $G=(V,E)$, on vertex set $V$ and edge set $E$, is connected. The neighborhood of a vertex $x$ in $G$ will be denoted $N_G(x)$ or simply $N(x)$ if the graph is clear from the context. A clique is a graph where every vertex is adjacent to every other vertex. A star is a tree with one universal vertex. For a graph $G=(V,E)$ and a vertex $x$ not belonging to $V$, we let denote $G^{\prime }=G+x$ ²²2Though the neighborhood of $x$ is not specified in the notation $G+x$, it will always be clear from the context. the graph obtained by adding $x$ to $V$ and all the edges between $x$ and $N_{G^{\prime }}(x)$ to $E$. Given a subset $S$ of vertices of $V$, we let $G[S]$ denote the subgraph induced by $S$. A vertex ordering $\sigma$ is a total order on the vertices of a graph $G$. If $x$ is smaller than $y$ in $\sigma$, we write . For a subset $S$ of vertices, we let $\sigma [S]$ denote the subordering of $\sigma$ induced by the vertices of $S$, that is for every $x,y\in S$, if and only if .

A bipartition $(A,B)$ of a set $V$ is non-trivial if $|A|>1$, $|B|>1$.

Splitting a graph $G$ with respect to a split $(A,B)$ of $G$ returns two graphs $G_A$ and $G_B$ obtained from $G$ by contracting $B$ into a vertex $x_A$ and $A$ into a vertex $x_B$ (the neighborhood of $x_A$ in $G_A$ is $A^{\prime }$ and of $x_B$ in $G_B$ is $B^{\prime }$), respectively. Let $G=(V,E)$ and $G^{\prime }=(V^{\prime },E^{\prime })$ be two graphs and let $x\in V$ and $x^{\prime }\in V^{\prime }$ be two vertices. The join between $G$ and $G^{\prime }$ with respect to $x$ and $x^{\prime }$, denoted $(G,x)\otimes (G^{\prime },x^{\prime })$, is the graph on vertex set $(V\cup V^{\prime })\setminus \{x,x^{\prime }\}$ such that two vertices $y$ and $z$ are adjacent if and only if $yz\in E$, or $yz\in E^{\prime }$, or $y\in N_G(x)$ and $z\in N_{G^{\prime }}(x^{\prime })$. So the join and the splitting are reverse operations for large enough graphs. Observe that if $G$ is the single vertex graph, then $(G,x)\otimes (G^{\prime },x^{\prime })$ is isomorphic to $G[V\setminus \{x^{\prime }\}]$, and if $G$ is the clique of size $2$, then $(G,x)\otimes (G^{\prime },x^{\prime })$ is isomorphic to $G^{\prime }$ Otherwise, if $G$ and $G^{\prime }$ are connected, then $(V\setminus \{x\},V^{\prime }\setminus \{x^{\prime }\})$ is a split of $(G,x)\otimes (G^{\prime },x^{\prime })$. A graph $G$ is degenerate if every non-trivial bipartition of $V$ is a split of $G$. It is known that if $G$ is degenerate, then $G$ is either a clique or a star. A graph $G$ is prime if it does not contain any split.

Let $(T,ℱ)$ be a GLT and let $u$ be a node of $(T,ℱ)$. We say that the node $u$ is prime if $G(u)$ is a prime graph and that $u$ is degenerate if $G(u)$ is degenerate. We let $V(u)$ denote the vertices of $G(u)$, hereafter called marker vertices, and $E(u)$ denote the edges of $G(u)$, hereafter called label edges. Since a leaf has only one incident edge, we may abusively consider leaves as marker vertices (namely the leaf $u$ is identified with the marker ${\rho }_u(e)$, of the unique edge $e$ incident to $u$). If $e=uv$ is a tree-edge of $T$, then the marker vertices ${\rho }_u(e)$ and ${\rho }_v(e)$ are opposite marker vertices called the extremities of $e$. Observe that every marker vertex is the extremity of a tree-edge of $T$.

A graph labelled tree is designed to represent a graph in a compact manner. To explain how, we need to introduce the notion of accessibility, which can be seen as an extension of the adjacency. Two marker vertices $q$ and $q^{\prime }$ of distinct nodes are accessible from one another if there exists a sequence of marker vertices $⟨q=q_1,\mathrm{\dots },q_{2k}=q^{\prime }⟩$ of even length such that $q_i,q_{i+1}$ are the extremities of a tree-edge if $i$ is odd and are adjacent marker vertices in some label graph if $i$ is even.

Let $e=u{u}^{\prime }$ be a tree-edge of the GLT $(T,ℱ)$. Consider the marker vertex $q\in V(u)$ that is the extremity $e$. Then, we let $L(q)$ denote the set of leaves of the subtree of $T-e$ not containing $u$. Among $L(q)$, we distinguish the subset $A(q)$ of leaves accessible from $q$.

Let $q^{\prime }\in V(u^{\prime })$ be the extremity of $e$ distinct from $q$. We observe that if $e$ is not incident to a leaf of $T$, then the bipartition $(L(q),L(q^{\prime }))$ is a split of $\mathrm{𝖦𝗋}(T,ℱ)$ and the frontiers of that split are $A(q)$ and $A(q^{\prime })$. The node-join of two non-leaf nodes $u$ and $u^{\prime }$ in $(T,ℱ)$ returns the GLT $(T^{\prime },{ℱ}^{\prime })$ obtained by contracting the tree-edge $e=u{u}^{\prime }$, labelling the resulting node $v$ by the graph $G(v)=(G(u),q)\otimes (G(u^{\prime }),q^{\prime })$, and letting every marker vertex $q\in V(v)$ be the extremity of the same tree-edge as in $(T,ℱ)$. The node-split operation of a GLT is the reverse of the node-join operation. Suppose that $(A,B)$ is a split of the graph $G(u)$ for some node $u$ of $(T,ℱ)$. The node-split of $u$ with respect to $(A,B)$ returns the GLT $(T^{\prime },{ℱ}^{\prime })$ where node $u$ has been replaced by two adjacent nodes $u_A$ and $u_B$ labelled by $G(u_A)=G(u)[A\cup \{q_A\}]$ for some vertex $q_A$ of the frontier $B^{\prime }$ and $G(u_B)=G(u)[B\cup \{q_B\}]$ for some vertex $q_B$ of the frontier $A^{\prime }$, respectively. The marker vertices $q_A\in V(u_A)$ and $q_B\in V(u_B)$ are made the extremities of the tree-edge $u_A{u}_B$. Every other marker vertex is an extremity of the same tree-edge as in $(T,ℱ)$.

A chord on a circle is defined by a pair $c=\{c_1,c_2\}$ of distinct points of the circle, called endpoints. Let $\chi$ be a set of chords no pair of which share a common endpoint. An expanded chord diagram on $\chi$ is naturally represented by a circular word $\dot{D}$ over the alphabet $𝒱={\bigcup }_{c\in \chi }\{c_1,c_2\}$. A chord diagram $D$ is obtained from the expanded chord diagram $\dot{D}$ by replacing every endpoint $c_i\in 𝒱$ ($i\in \{1,2\}$) by the corresponding chord $c\in \chi$. Observe that a chord diagram $D$ is a double occurrence circular word over the alphabet $\chi$, that is every chord of $\chi$ appears exactly twice in $D$. We may abusively say that each occurrence of a chord $c$ in $D$ is an endpoint of $c$. A subset $S$ of chords of $\chi$ is consecutive in $D$ if $D$ contains a factor $F$ such that for every chord $c\in S$, $|c\cap F|=1$ and for every chord $c^{\prime }\notin S$, $c^{\prime }\cap F=\mathrm{\varnothing }$. The first and the last chord of the factor $F$ are called the bookends of $F$ (or of $S$). Let $a$ and $b$ be two endpoints of the chord diagram $D$. Then $D(a,b)$ is the factor of $D$ containing the set of endpoints comprised between $a$ and $b$ (not containing $a$ and $b$), while $D(b,a)$ contains those comprised between $b$ and $a$. In other words, we have that $D\sim aD(a,b)bD(b,a)$. Observe that $D{(a,b)}^r=D^r(b,a)$ and that $D{(b,a)}^r=D^r(a,b)$.

Let $D$ and $D^{\prime }$ be chord diagrams on $\chi$ and ${\chi }^{\prime }$, respectively, and let $x\in \chi$ and $x^{\prime }\in {\chi }^{\prime }$. We define the circle-join operation between $D$ and $D^{\prime }$ with respect to $x=\{x_1,x_2\}$ and $x^{\prime }=\{x_1^{\prime },x_2^{\prime }\}$ as follows:

The result is a chord diagram on the set $(\chi \cup {\chi }^{\prime })\setminus \{x,x^{\prime }\}$ (see Figure 3). We observe that the circle-join is not a commutative operation: $(D,x)\odot (D^{\prime },x^{\prime })\ne (D^{\prime },x^{\prime })\odot (D,x)$.

A circle graph $G=(V,E)$ is the intersection graph of a chord diagram $D$ on a set $\chi$ of chords of a circle. In other words, there exists a bijection $\rho :V\to \chi$ such that two vertices $x,y\in V$ are adjacent in $G$ if and only if the chords $\rho (x)$ and $\rho (y)$ intersect in $D$, that is if and only $D(x_1,x_2)$ contains one endpoint among $y_1$ and $y_2$ and $D(x_2,x_1)$ the other. We say that $D$ represents or encodes $G$. We observe that, in general, a circle graph is encoded by many different chord diagrams. For example, cliques and stars are circle graphs that are represented by many chord diagrams: every clique $G$ on vertex set $V$ is represented by $D\sim A{A}^r$ where $A$ is an arbitrary permutation of $V$; every star $G$ with center vertex $x$ is represented by $D\sim xAxA$ where $A$ is an arbitrary permutation of $V\setminus \{x\}$.

However, we have the following important property, announced in [15], partially proved in [2], formally proved in [7] (an alternative proof was given in [19]):

Since degenerate graphs (cliques and stars) are circle graphs, a consequence of Observation 6 is the following well-known characterization of circle graphs.

We describe the consistent symmetric cycle data-structure (CSC) introduced in [19] that represents chord diagrams and allows to efficiently perform the following operations: consecutive test (see Lemma 9), consecutive preserving join (see Lemma 10) and vertex insertion (see Lemma 11). Let $D$ be a chord diagram on the set $\chi$ of chords. The consistent symmetric cycle (CSC), denoted $𝐂(D)$, representing $D$ is a directed graph whose vertices are the chord endpoints of $\chi$, that is $\mu ={\bigcup }_{x\in \chi }\{x_1,x_2\}$. Every pair of consecutive endpoints in $D$ is linked by two symmetric arcs, hence forming a symmetric directed cycle. It follows that every endpoint has two out-neighbors, which we denote ${+}_{𝐂(D)}(\cdot )$ and ${-}_{𝐂(D)}(\cdot )$. For every chord $x$ we have the property ${+}_{𝐂(D)}(x_1)$ and ${+}_{𝐂(D)}(x_2)$ belong to one of the two connected components of $𝐂(D)\setminus \{x_1,x_2\}$ and ${-}_{𝐂(D)}(x_1)$ and ${-}_{𝐂(D)}(x_2)$ to the other. To complete $𝐂(D)$, the two endpoints of every chord are linked with symmetric arcs (see Figure 4).

Let $𝐂(D)$ be a CSC on the set $\chi$ of chords. Let $x_1$ and $x_2$ be the two endpoints of a chord $x$. We let ${+}_{𝐂(D)}(x_1,x_2)$ denote the factor of $𝐂(D)$ obtained by searching $𝐂(D)$ from ${+}_{𝐂(D)}(x_1)$ to ${+}_{𝐂(D)}(x_2)$. The factor ${-}_{𝐂(D)}(x_1,x_2)$ is defined similarly. In the example of Figure 4, we have ${+}_{𝐂(D)}(e_1,e_2)=c_2{d}_1{a}_1{b}_1{c}_1{a}_2$ and ${-}_{𝐂(D)}(e_1,e_2)=d_2{b}_2$. We observe that ${+}_{𝐂(D)}(x_1,x_2)={+}_{𝐂(D)}{(x_2,x_1)}^r$ and that either ${+}_{𝐂(D)}(x_1,x_2)=D(x_1,x_2)$ or ${+}_{𝐂(D)}(x_1,x_2)=D^r(x_1,x_2)$.

The following three lemmas state the complexity of basic operations on CSC’s that the algorithm has to perform. Their proofs are straightforward from the data-structure description of CSC’s. They have been formally discussed in [19] as Lemmas 5.5–5.7.

The data structure we use to encode the split-tree $\mathrm{𝐒𝐓}(G)$ of a circle graph $G$ is based on PC-trees [21, 13]. We call it the split PC-tree of $G$ and it is denoted $\mathrm{𝐏𝐂}(G)$ (see Figure 5 for an example). It stores all marker vertices of $\mathrm{𝐒𝐓}(G)$ and encodes the structure of $\mathrm{𝐒𝐓}(G)$ on top of them as follows. We select an arbitrary leaf of $\mathrm{𝐒𝐓}(G)$ as the root of $\mathrm{𝐏𝐂}(G)$, which we denote by $r$. Let $u$ be a node of the split-tree $\mathrm{𝐒𝐓}(G)$. For each marker vertex $q\in V(u)$, we store an outgoing arc to its opposite $q^{\prime }$, which is a marker vertex of $G(u^{\prime })$ for some node $u^{\prime }$ adjacent to $u$ in $\mathrm{𝐒𝐓}(G)$. Observe that this way, each tree-edge $e$ of $\mathrm{𝐒𝐓}(G)$ corresponds to a pair of oppositely oriented arcs. We assume moreover that for an arc $a$ of $\mathrm{𝐏𝐂}(G)$, the opposite arc, denoted $\overline{a}$, can be accessed in $O(1)$-time. The way marker vertices of $V(u)$ are stored depends on the type of the node $u$ in $\mathrm{𝐒𝐓}(G)$.

• $\mathrm{■}$

  Suppose $u$ is degenerate. Then $u$ is represented in $\mathrm{𝐏𝐂}(G)$ by a node object $𝐧(u)$ that stores (i) the type of $u$, (ii) a (doubly-linked) list $𝐋(u)$ of the marker vertices in $V(u)$ (iii) a pointer to the node of $V(u)$ whose arc points towards the root $r$, and (iv) in case $u$ is a star, a pointer to the marker vertex that is the center of the star. Further, each marker vertex of $V(u)$ is equipped with a pointer to the node object $𝐧(u)$.

• $\mathrm{■}$

  Suppose $u$ is not degenerate. Then $\mathrm{𝐏𝐂}(G)$ does not store any node object for $u$. Instead, the vertices of $V(u)$ are stored in a CSC $𝐂(u)$ representing a chord diagram of $G(u)$. For each vertex $x\in V(u)$, one of the two endpoints of the corresponding chord is made incident to the symmetric pointers representing the tree-edge $e$ of which $x$ is the extremity. Further, a flag is used to mark the vertex whose arc points towards the root $r$ of $\mathrm{𝐒𝐓}(G)$.

Observe that, given any marker vertex from $V(u)$ of some degenerate node $u$, we can determine the corresponding node object and thus also its parent arc in $O(1)$ time. On the other hand, due to the lack of a node object to represent a non-degenerate node $u$, finding the parent arc of $u$ is a costly operation. Indeed, given a marker vertex from $V(u)$, one has to traverse $𝐂(u)$ until the endpoint is found whose flag indicates that it is incident to the parent arc. On the positive side, by Lemma 10, given two CSC’s, it is possible to perform a node-join operation in $O(1)$ time and since the result is always a non-degenerate node, there is no need to update pointers to a node object, especially the pointer to the parent of the resulting node.

Gioan et al. [20, Theorem 4.14, Proposition 4.15–4.20] show that exactly one of the following cases occurs and in each case describe how to obtain the split-tree $\mathrm{𝐒𝐓}(G^{\prime })$, with $G^{\prime }=G+x$, from $\mathrm{𝐒𝐓}(G)=(T,ℱ)$.

1. 1.

   $T$ contains a clique node $u$ whose marker vertices are all perfect; or $T$ contains a star node $u$ whose marker vertices are all empty except its center, which is perfect; or $T$ contains a unique hybrid node $u$, which is prime.

   In each of these cases, the node $u$ is unique and the split-tree $\mathrm{𝐒𝐓}(G^{\prime })$ is obtained by adding to $T$ a leaf ${\mathrm{\ell }}_x$ adjacent to $u$, adding to $G(u)$ a new marker vertex $q_x$ adjacent to $P(u)$ and opposite to ${\mathrm{\ell }}_x$.

   We observe that the type of the updated node $u$ is the same as in $\mathrm{𝐒𝐓}(G)$. This implies that in the case $u$ is degenerate, by Theorem 8, $G+x$ is a circle graph. So let us discuss the case that $u$ is a prime node. It is then represented in $\mathrm{𝐏𝐂}(G)$ by a CSC $𝐂(u)$ encoding its chord diagram, which is unique. In $𝐂(u)$, for $G+x$ to be a circle graph, $MP(u)$ has to be consecutive with the mixed marker vertices being the bookends (see Lemma 14). If so, adding $q_x$ consists in inserting a new chord whose extremities become the new bookends of $P(u)$. Otherwise, we can conclude that $G+x$ is not a circle graph.

2. 2.

   $T$ contains a tree-edge $e$ whose extremities are both perfect, and this edge is unique; or $T$ contains a tree-edge with one perfect and one empty extremity, and this edge is unique.

   In this case the tree-edge $e$ is unique and $\mathrm{𝐒𝐓}(G^{\prime })$ is obtained by: i) subdividing $e$ with a new node $u_x$; ii) adding a leaf ${\mathrm{\ell }}_x$ adjacent to $u_x$; and iii) labelling $u_x$ by a clique of size $3$ (if both extremities of $e$ are perfect) or a star on two leaves whose center is opposite to the extremity of $e$ that is empty. Observe that since the new node $u_x$ is degenerate, by Theorem 8, $G+x$ is a circle graph.

3. 3.

   $T$ contains a hybrid node $u$, and this node is degenerate.

   In this case the node $u$ is unique and $\mathrm{𝐒𝐓}(G^{\prime })$ is obtained as follows. First perform a node-split on $u$ according to the split $(P^{\ast }(u),E^{\ast }(u))$, creating a new tree-edge $e$, whose extremities are both perfect or one is perfect and the other is empty. Then $e$ can be processed as in the previous case. Again, since the modified nodes and the new node are degenerate, by Theorem 8, $G+x$ is a circle graph.

4. 4.

   $T$ contains a (unique) fully mixed subtree $M$.

   In this case, the fully mixed subtree is first cleaned and then contracted into a single node $v$ by performing node-joins. When finally adding $x$, the graph $G(v)$ becomes a prime graph. Along the series of the node-joins, we need to compute chord diagrams that preserve the consecutive property of $N_{G^{\prime }}(x)$ (see Lemma 10). More precisely, the split-tree $\mathrm{𝐒𝐓}(G^{\prime })$ is obtained in three steps as follows:

   1. (i)

      First, we clean the fully mixed subtree by performing on each degenerate node $u$ of $M$ a node-split with respect to the splits $(P^{\ast }(u),V(u)\setminus P^{\ast }(u))$ and/or $(E^{\ast }(u),V(u)\setminus E^{\ast }(u))$.

      The resulting GLT is denoted $\mathrm{𝖼𝗅}(\mathrm{𝐒𝐓}(G))$. Observe that the set of mixed tree-edges is left unchanged and thereby $M$ can still be abusively considered as the fully mixed subtree of $\mathrm{𝖼𝗅}(\mathrm{𝐒𝐓}(G))$. The difference with $\mathrm{𝐒𝐓}(G)$ is now that every degenerate node of $M$ contains at most one perfect and at most one empty marker (see Figure 7). Moreover by Lemma 14, if $G+x$ is a circle graph, every node $u$ of $M$ has at most two mixed marker vertices which form the bookends of the factor certifying the consecutiveness of $MP(u)$. It follows that the degenerate nodes of $\mathrm{𝖼𝗅}(\mathrm{𝐒𝐓}(G))$ have bounded degree and each of them can be equipped with the accurate CSC in constant time. Otherwise, we can conclude that $G+x$ is not a circle graph.

   2. (ii)

      Then, we contract $M$ into a single node $v$ by performing for every mixed tree-edge $e=u{u}^{\prime }$ in $M$ a node-join on $u$ and $u^{\prime }$.

      As discussed above, each node-join has to return a chord diagram that preserves the consecutive property of $N_{G^{\prime }}(x)$. Testing if such a chord diagram exists and computing it, can be done efficiently using the CSC data-structure (see Lemma 10). If there is no such chord diagram, then the algorithm stops and concludes that the graph $G+x$ is not a circle graph.

   3. (iii)

      Finally, in the contracted GLT, we attach a leaf ${\mathrm{\ell }}_x$ adjacent to node $v$; and we add to $G(v)$ a new marker $q_x$ adjacent to the marker vertices of $P(u)$ and opposite to ${\mathrm{\ell }}_x$.

      In this last step, adding $q_x$ consists in inserting a new chord in the chord diagram of $G(v)$, which is possible since it satisfies the consecutive property of $N_{G^{\prime }}(x)$ (see Lemma 11).

Given that $\mathrm{𝐒𝐓}(G)$ (or $\mathrm{𝐏𝐂}(G)$) has been correctly marked with respect to $N_{G^{\prime }}(x)$, where $G^{\prime }=G+x$, the correctness of the updating algorithm described in Subsection 5.1 is proved by Gioan et al. [19] and has been discussed along its description. However, its complexity analysis relies on the split PC-tree data-structure. To achieve an overall linear running time, we implement the updating algorithm in such a way that each vertex $x$ is processed in amortized $O(|N_{G^{\prime }}(x)|)$ time. Compared to the works of Gioan et al. [20, 19], the main challenge is that, given a marker vertex $q$ that belongs to a prime node $u$, our split PC-tree data structure does not allow to efficiently determine the parent of $u$. Using the fact that such nodes are prime, we have a chord diagram for them, and $x$ is inserted according to a LexBFS order allows us to anyway determine the parent without sacrificing the running time at least in all cases where this information is needed. Using the information acquired in the first step, the second step can be implemented in much the same way as in the work of Gioan et al. [19]. The major difference is that, in contrast to the data structure they use, ours allows to implement the contraction of fully mixed edges in Case 4 in constant time as there is no need to propagate the parent pointer information. Let us recall that, given a graph $G^{\prime }=G+x$ such that $x$ is a good vertex and $G$ is a circle graph, and given the split PC-tree $\mathrm{𝐏𝐂}(G)$ encoding $ST(G)=(T,ℱ)$, the insertion algorithm works in two steps:

1. 1.

   compute $T(N_{G^{\prime }}(x))$, the minimal subtree of $T$ covering $N_{G^{\prime }}(x)$;

2. 2.

   identify the cases according to the description of Subsection 5.1 and update the split-tree correspondingly.

We start discussing the implementation of the first step. For the sake of complexity efficiency, as stated by Lemma 15, if $G^{\prime }$ is a circle graph, we guarantee to compute $T(N_{G^{\prime }}(x))$ in the expected time complexity. Otherwise, the algorithm may be able to conclude, already at that step, that $G^{\prime }=G+x$ is not a circle graph. The reader has to keep in mind that if $\mathrm{𝐏𝐂}(G)$ encodes the split-tree $\mathrm{𝐒𝐓}(G)=(T,ℱ)$, the tree $T$ is not explicitly stored in $\mathrm{𝐏𝐂}(G)$ since we are lacking node objects to represent the prime nodes of $\mathrm{𝐒𝐓}(G)$. However the tree-edges of $T$ are present in $\mathrm{𝐏𝐂}(G)$. The algorithm identifies these tree-edges.