text:
# Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time

## 1 Introduction

There is a long history of applications for the problem of adding edges to a graph in order to satisfy connectivity specifications (see  for recent examples). Correspondingly, the problem has been extensively studied for making general graphs $`k`$-edge connected or $`k`$-vertex connected for various values of $`k`$  as well as for making vertex subsets suitably connected .

In this paper, we focus on augmenting bipartite graphs. A graph is componentwise biconnected if every connected component either is biconnected or is an isolated vertex. This paper presents a linear-time algorithm for the problem of inserting the smallest number of edges into a given bipartite graph to make it componentwise biconnected while maintaining its bipartiteness. This problem and related bipartite augmentation problems arise naturally from research on statistical data security . To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. A basic issue concerning the effectiveness of this practice is how a table maker can suppress a small number of cells in addition to the sensitive ones so that the resulting table does not leak significant information. This protection problem can be reduced to augmentation problems for bipartite graphs . In particular, a linear-time algorithm for our augmentation problem immediately yields a linear-time algorithm for suppressing the smallest number of additional cells so that no nontrivial information about any individual row or column is revealed to an adversary .

Section 2 formally states our augmentation problem and discusses main results. Section 3 proves an optimal bound on the smallest number of additional edges needed for the problem. Section 4 gives a linear-time algorithm to solve the augmentation problem.

## 2 Problem formulation, main results, and basic concepts

In this paper, all graphs are undirected and have neither self loops nor multiple edges.

### 2.1 The augmentation problem

Two vertices of a graph are biconnected if they are in the same connected component and remain so after the removal of any single edge or any single vertex other than either of them. A set of vertices is biconnected if every pair of its vertices are biconnected; similarly, a graph is biconnected if its set of vertices is biconnected. To suit our application of protecting sensitive information in statistical tables, this definition for biconnectivity is slightly different from the one used in standard textbooks. In particular, we define a connected component of an isolated vertex to be biconnected and one with exactly two vertices to be not biconnected.

A block of a graph is the induced subgraph of a maximal subset of vertices that is biconnected. A graph is componentwise biconnected if every connected component is a block. Throughout this paper, $`G=(A,B,E)`$ denotes a bipartite graph. A legal edge of $`G`$ is an edge in $`A\times B`$ but not in $`E`$. A biconnector of $`G`$ is a set $`L`$ of legal edges such that $`(A,B,EL)`$ is componentwise biconnected. An optimal biconnector is one with the smallest number of edges. Note that if $`A=\mathrm{}`$ or $`B=\mathrm{}`$, $`G`$ is componentwise biconnected. If $`|A|=1`$ and $`B\mathrm{}`$ (or $`|B|=1`$ and $`A\mathrm{}`$), $`G`$ has no biconnector. If $`|A|2`$ and $`|B|2`$, $`G`$ has a biconnector. In light of these observations, the optimal biconnector problem is the following: given $`G=(A,B,E)`$ with $`|A|2`$ and $`|B|2`$, find an optimal biconnector of $`G`$.

The remainder of this paper assumes $`|A|2`$ and $`|B|2`$. Also, let $`n`$ and $`m`$ be the numbers of vertices and edges in $`G`$, respectively.

Given an edge subset $`E^{}`$ and a vertex subset $`V^{}`$ of $`G`$, $`GV^{}`$ denotes $`G`$ without the vertices in $`V^{}`$ and their adjacent edges. $`GE^{}`$ denotes $`(A,B,EE^{})`$, i.e., the resulting $`G`$ after the edges in $`E^{}`$ are deleted. $`GE^{}`$ denotes $`(A,B,EE^{})`$, i.e., the resulting $`G`$ after the edges in $`E^{}`$ are added to $`G`$.

### 2.2 Basic definitions

A cut vertex or edge of a graph is one whose removal increases the number of connected components. A singular connected component is one formed by an isolated vertex. A singular block is one with exactly one vertex. An isolated block is one that is also a connected component. A pendant block is a singular block consisting of a vertex of degree $`1`$ or a nonsingular block containing exactly one cut vertex. Let $`\mathrm{\Lambda }(G)`$ denote the set of pendant blocks of $`G`$.

A vertex of $`G`$ is type $`A`$ or $`B`$ if it is in $`A`$ or $`B`$, respectively. A block of $`G`$ is type $`A`$ or $`B`$ if all of its noncut vertices are in $`A`$ or $`B`$, respectively; a block is type $`AB`$ if it has at least one noncut vertex in $`A`$ and one in $`B`$. A legal pair of $`G`$ is formed by two distinct elements in $`\mathrm{\Lambda }(G)`$ paired according to the following rules. Type $`A`$ may pair with type $`B`$ or $`AB`$. Type $`B`$ may pair with type $`A`$ or $`AB`$. Type $`AB`$ may pair with all three types. A binding edge for a legal pair is a legal edge between two noncut vertices, one from each of the two blocks of the pair.

###### Lemma 1

1. A noncut vertex is in exactly one block. Each pendant block contains a noncut vertex.
2. A singular pendant block of $`G`$ is either type $`A`$ or $`B`$ while a nonsingular pendant block is type $`AB`$ and has at least two vertices from $`A`$ and at least two from $`B`$.
3. There exists a binding edge for each legal pair of $`G`$.

Proof:  Straightforward.

Let $`\mathrm{\Lambda }^{}\mathrm{\Lambda }(G)`$. A legal matching of $`\mathrm{\Lambda }^{}`$ is a set of legal pairs between elements in $`\mathrm{\Lambda }^{}`$ such that each element in $`\mathrm{\Lambda }^{}`$ is in at most one legal pair. A maximum legal matching of $`\mathrm{\Lambda }^{}`$ is one with the largest cardinality possible. $`(\mathrm{\Lambda }^{})`$ denotes the cardinality of a maximum legal matching of $`\mathrm{\Lambda }^{}`$. For a maximum legal matching of $`\mathrm{\Lambda }^{}`$, let

$$(\mathrm{\Lambda }^{})=|\mathrm{\Lambda }^{}|2(\mathrm{\Lambda }^{}),$$

i.e., the number of elements in $`\mathrm{\Lambda }^{}`$ that are not in the given maximum legal matching. Note that $`(\mathrm{\Lambda }^{})`$ is the same for any maximum legal matching of $`\mathrm{\Lambda }^{}`$.

###### Lemma 2

1. Let $`W_1`$ and $`W_2`$ be two disjoint nonempty sets of pendant blocks with $`(W_1W_2)>0`$. Then some $`w_1W_1`$ and $`w_2W_2`$ form a legal pair with $`(W_1W_2\{w_1,w_2\})=(W_1W_2)1`$.
2. Let $`n_A,n_B`$ and $`n_{AB}`$ be the numbers of type $`A`$, $`B`$ and $`AB`$ pendant blocks in $`\mathrm{\Lambda }(G)`$, respectively. Then, $`(\mathrm{\Lambda }(G))=n_A+n_B+n_{AB}2(\mathrm{\Lambda }(G))`$, and $`(\mathrm{\Lambda }(G))=\alpha +\beta +\gamma `$, where $`\alpha =\mathrm{min}\{n_A,n_B\}`$, $`\beta =\mathrm{min}\{|n_An_B|,n_{AB}\}`$ and $`\gamma =\frac{n_{AB}\beta }{2}`$.

Proof:  The first statement follows from the fact that $`W_1W_2`$ has a maximum legal matching that contains a legal pair between $`W_1`$ and $`W_2`$. The second statement follows from the fact that a maximum legal matching can be obtained by iteratively applying any applicable rule below:

* If there are one unpaired type $`A`$ pendant block and one unpaired type $`B`$ pendant block, then we pair a type $`A`$ pendant block and a type $`B`$ one.
* If there is no unpaired type $`B`$ $`(`$respectively, $`A`$$`)`$ pendant block and there are one unpaired type $`A`$ $`(`$respectively, $`B`$$`)`$ pendant block and one unpaired type $`AB`$ pendant block, then we pair a type $`A`$ $`(`$respectively, $`B`$$`)`$ pendant block with a type $`AB`$ one.
* If all unpaired pendant blocks are type $`AB`$, then we pair two such blocks.

For all vertices $`uG`$, $`𝒟(u,G)`$ denotes the number of connected components in $`X\{u\}`$ where $`X`$ is the connected component of $`G`$ containing $`u`$. $`𝒞(G)`$ denotes the number of connected components in $`G`$ that are not blocks. $`(G)`$ denotes the number of edges in an optimal biconnector of $`G`$. When $`G`$ is connected, our target size for an optimal biconnector is:

$$\eta (G)=\underset{uG}{\mathrm{max}}\{𝒟(u,G)+𝒞(G)2,(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))\}.$$

### 2.3 Main results

We first prove a lower bound on the size of an optimal biconnector and then discuss two main results of this paper.

###### Lemma 3

1. $`G`$ is componentwise biconnected if and only if $`\eta (G)=0`$.
2. $`(G)\eta (G)`$.

Proof:  Statement 1 is straightforward. To prove Statement 2, it suffices to show $`(G)(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$ and $`(G)\mathrm{max}_{uG}𝒟(u,G)+𝒞(G)2`$. Let $`L`$ be an optimal biconnector of $`G`$.

To prove $`(G)(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$, note that $`\mathrm{\Lambda }(GL)`$ is empty. Thus, every block in $`\mathrm{\Lambda }(G)`$ contains an endpoint of an edge in $`L`$. Since all the edges in $`L`$ are legal, $`L`$ contains at least $`(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$ edges.

To prove $`(G)\mathrm{max}_{uG}𝒟(u,G)+𝒞(G)2`$, we need such an $`L`$ that the non-block connected components of $`G`$ are all contained in the same connected component of $`GL`$. If a given $`L`$ has not yet satisfied this property, then let $`X_1`$ and $`X_2`$ be two non-block connected components of $`G`$ that are contained in two different connected components $`X_1^{}`$ and $`X_2^{}`$ of $`GL`$, respectively. Let $`e_1=(u_1,v_1)X_1^{}`$ and $`e_2=(u_2,v_2)X_2^{}`$ be two edges in $`L`$. Such $`e_1`$ and $`e_2`$ exist because $`X_1`$ and $`X_2`$ are not biconnected in $`G`$, but $`X_1^{}`$ and $`X_2^{}`$ are biconnected in $`GL`$. Next, let $`e_1^{}=(u_1,v_2)`$ and $`e_2^{}=(u_2,v_1)`$. Then, $`L^{}=(L\{e_1,e_2\})\{e_1^{},e_2^{}\}`$ remains an optimal biconnector of $`G`$. Also, $`L^{}`$ connects $`X_1^{}\{e_1\}`$ and $`X_2^{}\{e_2\}`$, which include $`X_1`$ and $`X_2`$. By repeating this endpoint switching process, we can construct a desired $`L`$. With such an $`L`$, we proceed to prove $`(G)\mathrm{max}_{uG}𝒟(u,G)+𝒞(G)2`$. Since this claim trivially holds if $`G`$ is componentwise biconnected, we focus on the case where $`G`$ is not componentwise biconnected. Then, $`𝒟(u,G)`$ is maximized by some $`u`$ that is in a non-block connected component $`G`$. Let $`H_u`$ be the connected component of $`GL`$ containing $`u`$. Since $`GL`$ is componentwise biconnected, $`H_u\{u\}`$ is connected. Then, because $`H_u\{u\}L`$ has $`𝒟(u,G)+𝒞(G)1`$ connected components, $`|L|𝒟(u,G)+𝒞(G)2`$, proving our claim.

The next theorem is a main result of this paper.

###### Theorem 4

If $`G`$ is connected, then $`(G)=\eta (G)`$.

Proof:  By Lemma 3, $`(G)\eta (G)`$. For ease of understanding, the proof for $`(G)\eta (G)`$ is delayed to Theorem 9 in §3.

The next theorem generalizes Theorem 4 to $`G`$ that may or may not be connected.

* Let $`𝒞_1(G)`$ be the number of connected components of $`G`$ that are neither isolated edges nor blocks.
* Let $`𝒞_2(G)`$ be the number of isolated edges; note that $`𝒞(G)=𝒞_1(G)+𝒞_2(G)`$.
* Let $`𝒞_3(G)`$ be the number of connected components that are nonsingular blocks.

###### Theorem 5

Case M1: $`𝒞_1(G)=1`$ and $`𝒞_2(G)=0`$. Then $`(G)=\eta (G)`$.

Case M2: $`𝒞_1(G)+𝒞_2(G)2`$ and $`(\mathrm{\Lambda }(G))=0`$. Then $`(G)=\eta (G)`$.

Case M3: $`𝒞_1(G)+𝒞_2(G)2`$ and $`(\mathrm{\Lambda }(G))>0`$. Then $`(G)=\eta (G)`$.

Case M4: $`𝒞_1(G)=0`$, $`𝒞_2(G)=1`$, and $`𝒞_3(G)=0`$. Then $`(G)=3`$.

Case M5: $`𝒞_1(G)=0`$, $`𝒞_2(G)=1`$, and $`𝒞_3(G)>0`$. Then $`(G)=2`$.

Case M6: $`𝒞(G)=0`$. Then $`(G)=0`$.

Proof:

Case M1. Let $`G_1`$ be the connected component of $`G`$ that is neither an isolated edge nor a block. Theorem 4 applies to the case where $`G_1`$ contains at least two vertices in $`A`$ and at least two in $`B`$. Thus, we may assume without loss of generality that $`G_1`$ contains exactly one vertex $`uA`$ and $`r`$ vertices $`v_1,v_2,\mathrm{},v_rB`$ with $`r2`$. Note that $`\eta (G)=r`$. Because $`|A|>1`$ and $`𝒞_2(G)=0`$, there is an isolated vertex $`wA`$ or there is a nonsingular block in $`G`$ containing two vertices $`w_1,w_2A`$. In the former case, $`\{(w,v_1),\mathrm{},(w,v_r)\}`$ is an optimal biconnector; in the latter case, $`\{(w_1,v_1)\}\{(w_2,v_2),(w_2,v_3),\mathrm{},(w_2,v_r)\}`$ is an optimal biconnector.

Case M2. Since $`(\mathrm{\Lambda }(G))=0`$, we may assume without loss of generality that all the pendant blocks are type $`A`$. Note that $`𝒞_2(G)=0`$, $`𝒞_1(G)2`$ and $`\eta (G)=|\mathrm{\Lambda }(G)|`$. Let $`G_0,\mathrm{},G_{𝒞_1(G)1}`$ be the connected components of $`G`$ that are neither isolated edges nor blocks. Since each $`G_i`$ has more than two vertices, $`G_i`$ has a vertex $`y_iB`$. Let $`W_{i,1},\mathrm{},W_{i,r_i}`$ be the pendant blocks of $`G_i`$. Each $`W_{i,j}`$ contains a noncut vertex $`x_{i,j}A`$. The set $`\{(x_{i,j},y_{i+1mod𝒞_1(G)})0i<𝒞_1(G)\text{ and }1jr_i\}`$ is a biconnector. By Lemma 3(2), this biconnector is optimal.

Case M3. By Lemma 3, $`(G)\eta (G)`$. To prove the upper bound, let $`e`$ be a legal edge of $`G`$. Let $`G^{}=G\{e\}`$. We first show how to choose $`e`$ so that $`\eta (G^{})=\eta (G)1`$. Since $`(\mathrm{\Lambda }(G))>0`$, by Lemma 2(1), we can find a legal pair $`w_1`$ and $`w_2`$ in different connected components with $`(\mathrm{\Lambda }(G)\{w_1,w_2\})=(\mathrm{\Lambda }(G))1`$. By Lemma 1(3), let $`e`$ be a binding edge for $`w_1`$ and $`w_2`$. Note that $`𝒞(G^{})=𝒞(G)1`$, $`\mathrm{\Lambda }(G^{})=\mathrm{\Lambda }(G)\{w_1,w_2\}`$, $`(\mathrm{\Lambda }(G^{}))=(\mathrm{\Lambda }(G))1`$, $`(\mathrm{\Lambda }(G^{}))=(\mathrm{\Lambda }(G))`$ and $`\mathrm{max}_{uG^{}}𝒟(u,G^{})=\mathrm{max}_{uG}𝒟(u,G)`$. Thus, $`\eta (G^{})=\eta (G)1`$.

This process reduces $`𝒞(G)`$ and $`(\mathrm{\Lambda }(G))`$ by $`1`$ each. We iterate this process until either (1) $`𝒞_1(G)+𝒞_2(G)=1`$ or (2) $`𝒞_1(G)+𝒞_2(G)2`$ and $`(\mathrm{\Lambda }(G))=0`$. In the latter case, we use Case M2 to complete the proof. In the former case, note that we add an edge to combine two non-singular non-biconnected connected components into a connected component. This new connected component is neither an isolated edge nor a block. Thus, $`𝒞_1(G)>0`$; i.e., $`𝒞_1(G)=1`$ and $`𝒞_2(G)=0`$ in the resulting $`G`$. We then use Case M1 to complete the proof of this case.

Case M4. Let $`(r,c)`$ be the isolated edge. Let $`r^{}A`$ and $`c^{}B`$ be two isolated vertices. Then, $`\{(r,c^{}),(r^{},c),(r^{},c^{})\}`$ is an optimal biconnector of $`G`$.

Case M5. Let $`G^{}`$ be a connected component that is a nonsingular block in $`G`$. $`G^{}`$ has a vertex $`rA`$ and a vertex $`cB`$. Let $`(r^{},c^{})`$ be the isolated edge of $`G`$. Then, $`\{(r,c^{}),(r^{},c)\}`$ is an optimal biconnector of $`G`$.

Case M6. This case is straightforward.

## 3 A matching upper bound for a connected $`𝐆`$

This section assumes that $`G`$ is connected.

The block tree of $`G`$ is a tree $`\mathrm{\Psi }(G)`$ defined as follows. $`D_1`$ denotes the set of nonsingular blocks of $`G`$. $`D_2`$ is that of singular pendant ones. $`D_3`$ is that of singular non-pendant ones. $`C`$ is that of cut vertices. $`K`$ is that of cut edges. The vertex set of $`\mathrm{\Psi }(G)`$ is $`D_1D_2CK`$, where $`D_3`$ is excluded because if $`\{u\}D_3`$, then $`uC`$. The vertices in $`\mathrm{\Psi }(G)`$ corresponding to $`D_1D_2`$ are called the b-vertices; those corresponding to $`CK`$ are the c-vertices. To distinguish between an edge in $`G`$ and one in $`\mathrm{\Psi }(G)`$, let $`<y_1,y_2>`$ instead of $`(y_1,y_2)`$ denote an edge between two vertices $`y_1`$ and $`y_2`$ in $`\mathrm{\Psi }(G)`$. The edge set of $`\mathrm{\Psi }(G)`$ is the union of the following sets:

* $`\{<d_1,c>d_1D_1\text{ and }cC\text{ such that }cD_1\}`$;
* $`\{<c,e>cC\text{ and }eK`$ such that $`c`$ is an endpoint of $`e\}`$;
* $`\{<e,d_2>eK\text{ and }d_2D_2\text{ such that an endpoint of }e\text{ is in }d_2\}`$.

Figure 1 illustrates $`G`$ and its blocks while Figure 2 illustrates its block tree.

###### Lemma 6

1. $`\mathrm{\Psi }(G)`$ is a tree with $`O(n)`$ vertices. Its leaves are the $`|\mathrm{\Lambda }(G)|`$ pendant blocks of $`G`$.
2. For all cut vertices $`u`$ in $`G`$, $`𝒟(u,G)`$ equals the degree of $`u`$ in $`\mathrm{\Psi }(G)`$.

Proof:  The proof is straightforward and similar to that for similar constructs .

Let $`P_{u,v}`$ denote the tree path between two vertices $`u`$ and $`v`$ in $`\mathrm{\Psi }(G)`$. Let $`|P_{u,v}|`$ be the number of vertices in $`P_{u,v}`$.

###### Lemma 7

Let $`Y_1`$ and $`Y_2`$ be a legal pair of $`G`$. Let $`e`$ be a binding edge for $`Y_1`$ and $`Y_2`$. Let $`G^{}=G\{e\}`$.

1. The cut vertices of $`G`$ corresponding to c-vertices in $`P_{Y_1,Y_2}`$ and the vertices of $`G`$ in the b-vertices on $`P_{Y_1,Y_2}`$ form a new block $`Y_e`$ in $`G^{}`$. The b-vertices of $`\mathrm{\Psi }(G^{})`$ are $`Y_e`$ and those of $`\mathrm{\Psi }(G)`$ not on $`P_{Y_1,Y_2}`$.
2. The c-vertices in $`\mathrm{\Psi }(G^{})`$ are those in $`\mathrm{\Psi }(G)`$ excluding the ones on $`P_{Y_1,Y_2}`$ that are of degree $`2`$ in $`\mathrm{\Psi }(G)`$.
3. The edge set of $`\mathrm{\Psi }(G^{})`$ is the union of

* the set of edges in $`\mathrm{\Psi }(G)`$ whose two endpoints are still in $`\mathrm{\Psi }(G^{})`$;
    * $`\{<u,Y_e>uP_{Y_1,Y_2}`$ is a cut vertex of $`G`$ that remains in $`\mathrm{\Psi }(G^{})\}`$;
    * $`\{<u,Y_e>uP_{Y_1,Y_2}`$ is a cut vertex of $`G`$ incident to $`P_{Y_1,Y_2}`$ in $`\mathrm{\Psi }(G)\}`$.
4. The number of vertices in $`\mathrm{\Psi }(G^{})`$ is at most that for $`\mathrm{\Psi }(G)`$ minus $`\frac{|P_{Y_1,Y_2}|1}{2}`$.
5. If $`P_{Y_1,Y_2}`$ contains a b-vertex of degree at least four in $`\mathrm{\Psi }(G)`$ or two vertices each of degree at least three, then $`\mathrm{\Lambda }(G^{})=\mathrm{\Lambda }(G)\{Y_1,Y_2\}`$.

Proof:  The proof is straightforward and similar to those for similar constructs .

A cut vertex $`u`$ of $`G`$ is massive if $`𝒟(u,G)1>(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$; it is critical if $`𝒟(u,G)1=(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$.

###### Lemma 8

Assume $`\mathrm{\Lambda }(G)>3`$.

1. $`G`$ has at most two critical vertices. If it has two, then $`(\mathrm{\Lambda }(G))=0`$.
2. $`G`$ has at most one massive vertex. If it has one, then it has no critical vertex.

Proof:  The proof follows from Lemma 6, the inequality $`(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))\frac{|\mathrm{\Lambda }(G)|}{2}`$, and basic counting arguments for trees.

The next theorem is the main result of this section.

###### Theorem 9

$`(G)\eta (G)`$.

Proof:  By Lemma 8, we divide the proof into the following five cases. The first case is discussed in Lemma 10; the other cases are proved in §3.1–§3.4, respectively.

Case S1: $`|\mathrm{\Lambda }(G)|3`$.

Case S2: $`|\mathrm{\Lambda }(G)|>3`$ and $`(\mathrm{\Lambda }(G))=0`$.

Case S3: $`|\mathrm{\Lambda }(G)|>3`$, $`(\mathrm{\Lambda }(G))>0`$, and $`G`$ has two critical vertices.

Case S4: $`|\mathrm{\Lambda }(G)|>3`$, $`(\mathrm{\Lambda }(G))>0`$, and $`G`$ has no massive vertex and at most one critical vertex.

Case S5: $`|\mathrm{\Lambda }(G)|>3`$, $`(\mathrm{\Lambda }(G))>0`$, and $`G`$ has exactly one massive vertex.

###### Lemma 10

For Case S1, Theorem 9 holds. Furthermore, given $`G`$, an optimal biconnector can be computed in $`O(m+n)`$ time.

Proof:  Straightforward.

### 3.1 Case S2 of Theorem 9

###### Lemma 11

Theorem 9 holds for Case S2.

Proof:  Let $`k=|\mathrm{\Lambda }(G)|`$. Since $`(\mathrm{\Lambda }(G))=0`$, $`\eta (G)=k`$ by Lemma 6. It suffices to construct a biconnector $`L`$ of $`k`$ edges for $`G`$. Let $`Y_1,\mathrm{},Y_k`$ be the pendant blocks of $`G`$. Since $`(\mathrm{\Lambda }(G))=0`$, $`Y_i=\{y_i\}`$ and we may assume $`y_iB`$ without loss of generality. Then, $`G`$ has a cut edge $`(x_i,y_i)`$ for each $`y_i`$, where $`x_iA`$. Since $`|A|2`$ and $`(\mathrm{\Lambda }(G))=0`$, there is some $`x_jx_1`$. Let $`G^{}`$ be the connected component of $`G\{x_1\}`$ containing $`x_j`$. Let $`L`$ be the set of legal edges $`(y_i,x_1)`$ for all $`y_iG^{}`$ and $`(y_i,x_j)`$ for all $`y_iG^{}`$. It is straightforward to prove that $`L`$ is as desired by means of Lemma 7.

### 3.2 Case S3 of Theorem 9

A path $`v_1,\mathrm{},v_k`$ in $`\mathrm{\Psi }(G)`$ is branchless if for all $`i`$ with $`1<i<k`$ the degree of $`v_i`$ in $`\mathrm{\Psi }(G)`$ is two. Let $`u_1`$ and $`u_2`$ be the critical vertices of $`G`$. A leaf clings to $`u_i`$ in $`\mathrm{\Psi }(G)`$ if there is a branchless path between it and $`u_i`$.

###### Lemma 12

1. $`\eta (G)=(\mathrm{\Lambda }(G))=\frac{|\mathrm{\Lambda }(G)|}{2}`$.
2. $`\mathrm{\Psi }(G)`$ has a branchless path between $`u_1`$ and $`u_2`$, and exactly $`\frac{|\mathrm{\Lambda }(G)|}{2}`$ leaves cling to $`u_1`$ only while the other $`\frac{|\mathrm{\Lambda }(G)|}{2}`$ leaves cling to $`u_2`$ only.
3. $`\mathrm{\Lambda }(G)`$ has a maximum legal matching in which each legal pair is between one clinging to $`u_1`$ and one clinging to $`u_2`$.

Proof:  Statement 1 follows Lemma 8. Statement 2 follows from basic counting arguments for trees. Statement 3 follows from the first two and Lemma 2(1).

###### Lemma 13

Theorem 9 holds for Case S3.

Proof:  We add to $`G`$ a binding edge for each legal pair in the maximum legal matching of Lemma 12. By Lemmas 7 and 12, the resulting graph is biconnected. We add $`\frac{|\mathrm{\Lambda }(G)|}{2}`$ edges, which by Lemma 12(1) is optimal.

### 3.3 Case S4 of Theorem 9

Since $`|\mathrm{\Lambda }(G)|>3`$, we can divide Case S4 into two subcases:

Case S4-1: $`\mathrm{\Psi }(G)`$ has exactly one vertex of degree at least three.

Case S4-2: $`\mathrm{\Psi }(G)`$ has more than one vertex of degree at least three.

###### Lemma 14

Theorem 9 holds for Case S4-1.

Proof:  Let $`x`$ be the vertex in $`\mathrm{\Psi }(G)`$ of degree at least three. There are two cases:

Case 1: $`x`$ is a $`b`$-vertex. Then, $`\eta (G)=(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$.

Case 2: $`x`$ is a $`c`$-vertex. Since $`x`$ is not massive, $`\eta (G)=𝒟(x,G)1=(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$ and $`(\mathrm{\Lambda }(G))=1`$.

In either case, let $`N_1`$ be a maximum legal matching of $`\mathrm{\Lambda }(G)`$; next, let $`N_2`$ be a set of legal pairs formed by pairing each pendant block not yet matched in $`N_1`$ with one already matched. Then, $`N=N_1N_2`$ is a set of the smallest number of legal pairs of $`G`$ such that each element in $`\mathrm{\Lambda }(G)`$ is in a pair. We add to $`G`$ a binding edge for each pair in $`N`$. Since $`(\mathrm{\Lambda }(G))>0`$, we add $`\eta (G)`$ edges. Since $`(\mathrm{\Lambda }(G))>0`$ in Case 1 and $`(\mathrm{\Lambda }(G))=1`$ in Case 2, these edges form a desired biconnector by Lemma 7.

To discuss Case S4-2, we further assume that $`\mathrm{\Psi }(G)`$ is rooted at a vertex with at least two neighbors; however, the degree of a vertex in $`\mathrm{\Psi }(G)`$ still refers to its number of neighbors instead of children.

The next lemma chooses an advantageous root for $`\mathrm{\Psi }(G)`$ for our augmentation algorithm. Given a vertex $`v`$ in $`\mathrm{\Psi }(G)`$, a branch of $`v`$, also called a $`v`$-branch, is the subtree of $`\mathrm{\Psi }(G)`$ rooted at a child of $`v`$. A chain of $`v`$, also called a $`v`$-chain, is a $`v`$-branch that contains exactly one leaf in $`\mathrm{\Psi }(G)`$.

Let $`c^{}`$ be a c-vertex in $`\mathrm{\Psi }(G)`$ of the largest possible degree.

###### Lemma 15

In Case S4-2, we can reroot $`\mathrm{\Psi }(G)`$ at a vertex $`h`$ such that

1. either $`h`$ is of degree two and no $`h`$-branch is a chain or $`h`$ is of degree at least three;
2. if $`c^{}`$ is critical, then $`h=c^{}`$.

Proof:  Let $`r`$ be the current root of $`\mathrm{\Psi }(G)`$. There are three cases.

Case 1: $`c^{}`$ is not critical, and either $`r`$ is of degree two and no $`r`$-branch is a chain or $`r`$ is of degree at least three. We set $`h=r`$.

Case 2: $`c^{}`$ is not critical, $`r`$ is of degree two, and an $`r`$-branch is a chain. Note that $`\mathrm{\Psi }(G)`$ has a vertex $`r^{}`$ of degree at least three. We set $`h=r^{}`$.

Case 3: $`c^{}`$ is critical. Since $`|\mathrm{\Lambda }(G)|>3`$, $`c^{}`$ is of degree three or more. We set $`h=c^{}`$.

###### Lemma 16

Let $`h`$ be the root of $`\mathrm{\Psi }(G)`$. In Case S4-2, if either $`h`$ is of degree two and no $`h`$-branch is a chain or $`h`$ is of degree at least three, then $`G`$ has a legal pair $`w_1`$ and $`w_2`$ such that

1. $`P_{w_1,w_2}`$ passes through $`h`$ and two vertices of degree at least three;
2. $`(\mathrm{\Lambda }(G)\{w_1,w_2\})=(\mathrm{\Lambda }(G))1`$.

Proof:  There are two cases.

Case 1: The degree of $`h`$ is two and no $`h`$-branch is a chain. Let $`T^{}`$ be an $`h`$-branch.

Case 2: The degree of $`h`$ is at least three. Since this is Case S4-2, some descendant of $`h`$ has degree at least three. Let $`T^{}`$ be the $`h`$-branch containing that descendant.

Let $`W_1`$ be the set of leaves in $`T^{}`$. Let $`W_2=\mathrm{\Lambda }(G)W_1`$. By Lemma 2(1), there exist a legal pair $`w_1W_1`$ and $`w_2W_2`$ with $`(\mathrm{\Lambda }(G)\{w_1,w_2\})=(\mathrm{\Lambda }(G))1`$. Then, $`P_{w_1,w_2}`$ contains $`h`$ as desired. Furthermore, in Case 1, $`P_{w_1,w_2}`$ contains a vertex of degree at least three in $`T^{}`$ and another in $`\mathrm{\Psi }(G)T^{}`$; in Case 2, $`h`$ itself is of degree at least three, and $`P_{w_1,w_2}`$ contain a vertex of degree at least three in $`T^{}`$. In both cases, $`P_{w_1,w_2}`$ is as desired.

###### Lemma 17

In Case S4-2, we can add a legal edge to $`G`$ such that

1. the resulting graph $`G^{}`$ satisfies Case S1, S2, S3 or S4;
2. $`\eta (G^{})=\eta (G)1`$;
3. if $`G`$ has a critical vertex, then that vertex remains critical in $`G^{}`$.

Proof:  We use Lemma 15 to reroot $`\mathrm{\Psi }(G)`$, use Lemma 16 to pick a legal pair $`w_1`$ and $`w_2`$, and then add a binding edge for this pair to $`G`$. By Lemmas 16(1) and 7(5), $`\mathrm{\Lambda }(G^{})=\mathrm{\Lambda }(G)\{w_1,w_2\}`$. By Lemma 16(2), $`(\mathrm{\Lambda }(G^{}))=(\mathrm{\Lambda }(G))1`$. Hence $`(\mathrm{\Lambda }(G^{}))+(\mathrm{\Lambda }(G^{}))=(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))1`$. There are two cases.

Case 1: $`G`$ has no critical vertex. Then, by Lemma 7, $`\mathrm{max}_{uG^{}}𝒟(u,G^{})\mathrm{max}_{uG}`$ $`𝒟(u,G)(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$.

Case 2: $`G`$ has a critical vertex. Then, $`c^{}`$ is the critical vertex and $`𝒟(c^{},G)>\mathrm{max}_{uc^{}}𝒟(u,G)`$. By Lemmas 15(2), 16(1), and Lemma 7, $`\mathrm{max}_{uG^{}}𝒟(u,G^{})=\mathrm{max}_{uG}`$ $`𝒟(u,G)1=(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$. Hence $`c^{}`$ remains to be a critical vertex.

In either case, $`\mathrm{max}_{uG^{}}𝒟(u,G^{})1(\mathrm{\Lambda }(G^{}))+(\mathrm{\Lambda }(G^{}))`$. Then, $`\eta (G^{})=\eta (G)1`$. Also, $`G^{}`$ has no massive vertex and thus satisfies Case S1, S2, S3 or S4.

###### Lemma 18

Theorem 9 holds for Case S4.

Proof:  For Case S4-1, we use Lemma 14. For Case S4-2, we add one edge to $`G`$ at a time using Lemma 17 until the resulting graph $`G^{}`$ does not satisfy Case S4-2. By Lemma 17(1), $`G^{}`$ satisfies Case S1, S2, S3 or S4-1. Thus, we apply Lemma 10, 11, 13, or 14 to $`G^{}`$ accordingly. By Lemma 17(2), the number of edges added is $`\eta (G)`$.

### 3.4 Case S5 of Theorem 9

Let $`r`$ be the massive cut vertex of $`G`$. Let $`\mathrm{\Psi }(G)`$ be rooted at $`r`$.

###### Lemma 19

1. $`\eta (G)=𝒟(r,G)1>(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))>𝒟(u,G)1`$ for any vertex $`ur`$.
2. $`𝒟(r,G)4`$ and there are at least four $`r`$-chains.
3. The tree $`\mathrm{\Psi }(G)`$ contains a legal pair $`Y_1`$ and $`Y_2`$ as well as two distinct $`r`$-branches $`T_1`$ and $`T_2`$ such that $`T_1`$ is a chain, $`Y_1T_1`$, and $`Y_2T_2`$.

Proof:

Statement 1. This statement follows from the definition of Case S5.

Statement 2. Let $`\delta _1`$ be the number of $`r`$-chains. Then, $`𝒟(r,G)\delta _1`$ and $`|\mathrm{\Lambda }(G)|2(𝒟(r,G)\delta _1)+\delta _1`$. So $`𝒟(r,G)\delta _12𝒟(r,G)|\mathrm{\Lambda }(G)|`$. Let $`\delta _2=(𝒟(r,G)1)((\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G)))`$. Because $`r`$ is massive, $`\delta _21`$. Note that $`|\mathrm{\Lambda }(G)|=2(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$. Thus $`𝒟(r,G)\delta _12\delta _2+2+(\mathrm{\Lambda }(G))4`$.

Statement 3. Let $`T_1`$ be an $`r`$-chain. Let $`Y_1`$ be the leaf of $`\mathrm{\Psi }(G)`$ in $`T_1`$. Because $`(\mathrm{\Lambda }(G))>0`$, $`\mathrm{\Psi }(G)`$ contains a leaf $`Y_2Y_1`$ that forms a legal pair with $`Y_1`$. Let $`T_2`$ be the $`r`$-branch that contains $`Y_2`$. Then, $`Y_1`$, $`Y_2`$, $`T_1`$ and $`T_2`$ are as desired.

###### Lemma 20

We can add a legal edge to $`G`$ such that for the resulting graph $`G^{}`$,

1. $`\eta (G^{})=\eta (G)1`$;
2. $`𝒟(r,G^{})=𝒟(r,G)1`$.

Proof:  Let $`Y_1`$, $`Y_2`$, $`T_1`$ and $`T_2`$ be as stated in Lemma 19(3). The added edge is a binding edge for $`Y_1`$ and $`Y_2`$. By Lemma 7, the b-vertices and c-vertices on $`P_{Y_1,Y_2}`$ form a new block $`Y^{}`$ in $`G^{}`$. $`Y^{}`$ may or may not be a leaf in $`\mathrm{\Psi }(G^{})`$; in either case, $`(\mathrm{\Lambda }(G^{}))+(\mathrm{\Lambda }(G^{}))(\mathrm{\Lambda }(G))+(\mathrm{\Lambda }(G))`$. Note that $`P_{Y_1,Y_2}`$ contains $`r`$. Thus, by Lemmas 7 and 19(2), $`r`$ remains a cut vertex in $`G^{}`$ with $`𝒟(r,G^{})=𝒟(r,G)1`$ while $`𝒟(v,G^{})𝒟(v,G)`$ for all vertices $`vr`$. Consequently, $`\eta (G^{})=\eta (G)1`$.

###### Lemma 21

Theorem 9 holds for Case S5. Moreover, this case can be reduced in linear time to Case S1, S2, S3 or S4.

Proof:  We add one edge to $`G`$ at a time using Lemma 20 until the resulting graph $`G^{}`$ satisfies Case S1, S2, S3 or S4. Thus, we apply Lemma 10, 11, 13 or 18 accordingly. By Lemma 20(1), $`\eta (G)`$ edges are added. To implement this proof in linear time, we first define a data structure as follows.

Let $`Q`$ be the set of leaves of $`\mathrm{\Psi }(G)`$ that are in the $`r`$-chains. We set up a counter for the number of these leaves. We also set up three doubly linked lists containing those of them that are types $`A`$, $`B`$, and $`AB`$, respectively.

We set up a counter for the number of $`r`$-branches that are not chains. For each such branch, we set up a doubly linked list for the leaves of $`\mathrm{\Psi }(G)`$ in it. We also set up three doubly linked lists for the leaves in these branches that are types $`A`$, $`B`$, and $`AB`$, respectively.

Given $`G`$, we can set up these linked lists and counters in linear time. We next use this data structure to find a legal pair $`Y_1`$ and $`Y_2`$ by means of Lemma 19(3). Since $`|Q|4`$ by Lemma 19(2), there are two cases.

Case 1: Some $`Y_1`$ and $`Y_2Q`$ form a legal pair. This is our desired pair. Note the $`r`$-chains containing $`Y_1`$ and $`Y_2`$ in $`\mathrm{\Psi }(G)`$ are contracted into a new chain in $`\mathrm{\Psi }(G^{})`$ consisting of a single leaf of type $`AB`$.

Case 2: $`Q`$ contains only type $`A`$ or $`B`$ leaves. Select any $`Y_1Q`$. Since $`(\mathrm{\Lambda }(G))>0`$, some $`Y_2\mathrm{\Lambda }(G)Q`$ forms a desire legal pair with $`Y_1`$. Note that $`Y_1`$ and $`Y_2`$ are no longer pendant blocks in $`G^{}`$ and the newly created block is not a pendant block of $`G^{}`$, either. The $`r`$-branch containing $`Y_2`$ becomes a chain if in $`G`$ it contains exactly two pendant blocks.

It takes $`O(1)`$ time to decide which of these two cases holds. In either case, the selection of $`Y_1`$ and $`Y_2`$ takes in $`O(1)`$ time using the linked lists. Once $`Y_1`$ and $`Y_2`$ are found, we can find a binding edge in $`O(1)`$ time in a straightforward manner. After the edge is added to $`G`$, we can update the data structure in $`O(1)`$ time for $`G^{}`$. Then, we use Lemma 2(2) and the counters to check whether $`G^{}`$ satisfies Case S5 in $`O(1)`$ time. We repeat this process until $`G^{}`$ does not satisfies Case S5. At this point, we complete the reduction. Since we iteratively add at most $`O(n)`$ edges in Case S5, the reduction takes linear time.

## 4 Computing an optimal biconnector in linear time

###### Theorem 22

Given $`G`$, an optimal biconnector is computable in $`O(m+n)`$ time.

We prove this theorem by means of Theorems 5 and 9 as follows.

Given $`G`$, it takes $`O(m+n)`$ time to determine which case of Theorem 5 holds. Then, it takes $`O(m+n)`$ time in a straightforward manner to compute an optimal biconnector for Cases M2, M4, M5 and M6; reduce Case M3 to Case M1 or M2; and reduce Case M1 to Theorem 9.

Next, it takes $`O(m+n)`$ time to determine which case of Theorem 9 holds. Then, it is straightforward to compute an optimal biconnector in $`O(m+n)`$ time for Cases S1, S2, and S3. Lemma 21 reduces Case S5 in $`O(m+n)`$ time to Case S1, S2, S3 or S4. By Lemma 14, we can find an optimal biconnector in $`O(m+n)`$ time for Case S4-1. The remaining proof shows how to reduce Case S4-2 to Case S1, S2, S3 or S4-1 in $`O(m+n)`$ time by implementing the proof of Lemma 18.

We define a data structure $`\mathrm{\Delta }(G)`$ as follows. First, we root $`\mathrm{\Psi }(G)`$ at a vertex of degree two or more as in §3.3 and classify each vertex $`u`$ by a 4-bit code $`\sigma _0\sigma _1\sigma _2\sigma _3`$ based on the subtree $`T_u`$ of $`\mathrm{\Psi }(G)`$ rooted at $`u`$:

* $`\sigma _0=1`$ if and only if $`T_u`$ has more than one leaf;
* $`\sigma _1`$, $`\sigma _2`$ or $`\sigma _3=1`$ if and only if $`T_u`$ contains a leaf of type $`A`$, $`B`$ or $`AB`$, respectively.

The code has at most ten combinations, i.e., $`0100`$, $`0010`$, $`0001`$ and all the combinations with $`\sigma _0=1`$ except $`1000`$. $`\mathrm{\Delta }(G)`$ is $`\mathrm{\Psi }(G)`$ augmented with the following items:

1. At each vertex in $`\mathrm{\Psi }(G)`$, $`\mathrm{\Delta }(G)`$ maintains its degree and a doubly linked list for the children of $`u`$ with the same $`\sigma _0\sigma _1\sigma _2\sigma _3`$ code. There are ten such lists.
2. There are three counters for the numbers of leaves in $`\mathrm{\Psi }(G)`$ of types $`A`$, $`B`$ and $`AB`$, respectively.
3. The c-vertices of degree at least three are partitioned into groups of the same degree. Each nonempty group is arranged into a doubly linked list. The lists themselves are connected by a doubly linked list in the increasing order of vertex degrees.

We do not need parent pointers in $`\mathrm{\Delta }(G)`$, which are subtle to update . This finishes the description of $`\mathrm{\Delta }(G)`$. We can build $`\mathrm{\Delta }(G)`$ from $`G`$ in $`O(m+n)`$ time.

###### Lemma 23

1. Let $`r`$ be the current root of $`\mathrm{\Delta }(G)`$. Let $`h`$ be as stated in Lemma 15. Given $`\mathrm{\Delta }(G)`$, if $`r`$ is critical, we can reroot $`\mathrm{\Delta }(G)`$ in $`O(1)`$ time according to Lemma 15; $`O(n)`$ time if $`r`$ is not critical but $`h`$ is; or $`O(|P_{r,h}|)`$ time if neither is.
2. Given $`\mathrm{\Delta }(G)`$, we can find $`w_1`$ and $`w_2`$ of Lemma 16 in $`O(|P_{w_1,w_2}|)`$ time.

Proof:

Statement 1. We implement the proof Lemma 15 using the following steps.

1. Use Item 3 of $`\mathrm{\Delta }(G)`$ to find $`c^{}`$.
2. Use Items 1 and 2 of $`\mathrm{\Delta }(G)`$ and Lemma 2(2) to decide which case of the proof of Lemma 15 holds.
3. 1. For Case 1 of the proof of Lemma 15, set $`h=r`$ and $`\mathrm{\Delta }(G)`$ is unchanged.
    2. For Case 2 of the proof of Lemma 15, first use Item 1 of $`\mathrm{\Delta }(G)`$ to find the nearest desired descendant $`r^{}`$ of $`r`$ and then reroot $`\mathrm{\Delta }(G)`$ at $`h=r^{}`$ and update it accordingly.
    3. For Case 3 of the proof of Lemma 15, if $`rc^{}`$, then recompute $`\mathrm{\Delta }(G)`$ from $`\mathrm{\Psi }(G)`$ to root at $`h=c^{}`$; otherwise, $`r=c^{}`$, and $`\mathrm{\Delta }(G)`$ is unchanged.

Since Steps 1 and 2 take $`O(1)`$ time, the the time complexity of each case of this statement is bounded by that of Step 3.

Case 1: $`r`$ is critical. Step 3c runs with $`r=c^{}`$ in $`O(1)`$ time.

Case 2: $`r`$ is not critical but $`h`$ is. Step 3c runs with $`rc^{}`$ in $`O(n)`$ time.

Case 3: Neither $`r`$ nor $`h`$ is critical. Then, Step 3a or Step 3b is performed. Step 3a takes $`O(1)`$ time. For Step 3b, the search for $`r^{}`$ takes $`O(1)`$ time per vertex on $`P_{r,r^{}}`$. Since the internal vertices of $`P_{r,r^{}}`$ all have degree two, updating Item 1 of $`\mathrm{\Delta }(G)`$ along this path takes $`O(1)`$ time per vertex. Item 1 of $`\mathrm{\Delta }(G)`$ outside this path and the other two items remain the same. Thus, this case takes $`O(P_{r,h})`$ total time as desired.

Statement 2. We implement the proof of Lemma 16 using the following steps.

1. Use Item 1 of $`\mathrm{\Delta }(G)`$ to decide which case of the proof of Lemma 16 holds.
2. Use Item 2 of $`\mathrm{\Delta }(G)`$ and Lemma 2(2) to find all possible pairs of types $`t_1`$ and $`t_2`$ such that $`\mathrm{\Lambda }(G)`$ has a maximum matching that contains a legal pair between type $`t_1`$ and type $`t_2`$.
3. For each such pair of $`t_1`$ and $`t_2`$, perform the following computation until $`w_1`$ and $`w_2`$ are found.

1. For Case 1 of the proof of Lemma 16, $`w_1`$ and $`w_2`$ are in the two branches of the root of $`\mathrm{\Delta }(G)`$ separately. Use Item 1 of $`\mathrm{\Delta }(G)`$ at the root to decide whether the desired $`w_1`$ and $`w_2`$ exist. If they exist, use Item 1 of $`\mathrm{\Delta }(G)`$ to search for them.
    2. For Case 2 of the proof of Lemma 16, $`w_1`$ and $`w_2`$ are in two separate branches of the root, of which one is not a chain. The remaining computation is similar to that of Step 3a.

By Lemma 15, some pair $`t_1`$ and $`t_2`$ yields the desired $`w_1`$ and $`w_2`$. Steps 1 and 2 take $`O(1)`$ time. There are $`O(1)`$ possible pairs of $`t_1`$ and $`t_2`$. For each such pair, checking the existence of $`w_1`$ and $`w_2`$ takes $`O(1)`$ time. If they exist, searching for them takes $`O(1)`$ time per vertex on the path $`P_{w_1,w_2}`$.

The next lemma completes the proof of Theorem 22.

###### Lemma 24

Case S4-2 is reducible to Case S1, S2, S3 or S4-1 in $`O(m+n)`$ time.

Proof:  Given $`G`$ in Case S4-2 as input, the reduction algorithm is as follows:

1. Construct $`\mathrm{\Delta }(G)`$.
2. repeat

1. Use Lemma 23(1) to reroot $`\mathrm{\Delta }(G)`$.
    2. Use Lemma 23(2) to find a legal pair $`w_1`$ and $`w_2`$.
    3. Add a binding edge $`e`$ for $`w_1`$ and $`w_2`$ into $`G`$.
    4. Use Lemma 7 to update $`\mathrm{\Delta }(G)`$ while rerooting it at the new b-vertex $`Y_e`$ resulting from the insertion of $`e`$.

until $`G`$ does not satisfy Case S4-2.

Since Step 1 takes $`O(m+n)`$ time, it suffices to prove that Step 2 takes $`O(n)`$ time. By Lemma 16(1), each iteration of Step 2 reduces $`|\mathrm{\Lambda }(G)|`$ by two. Since $`|\mathrm{\Lambda }(G)|<n`$, the repeat loop has less than $`n`$ iterations. Then, since the until condition can be checked in $`O(1)`$ time per iteration using Lemma 2(2) and Items 2 and 3 of $`\mathrm{\Delta }(G)`$, the until step takes $`O(n)`$ total time. Similarly, Step 2c takes $`O(1)`$ time per iteration and $`O(n)`$ total time in a straightforward manner.

We next show that Steps 2a, 2b and 2d also take $`O(n)`$ total time. For a given iteration, let $`G_0`$ and $`G_1`$ denote $`G`$ before and after $`e`$ is inserted, respectively.

Step 2a. We show that each case in the proof of Lemma 23(1) takes $`O(n)`$ total time as follows.

Case 1. This case takes $`O(1)`$ time per iteration and thus $`O(n)`$ total time.

Case 2. By Lemma 17(3), this case can only happen once in the above augmentation algorithm. Hence, this case takes $`O(n)`$ total time.

Case 3. This case takes $`O(1)`$ time per edge on $`P_{r,h}`$ for an iteration. Note that the degree of a vertex in $`\mathrm{\Delta }(G)`$ never increases by edge insertion. Then, since $`\mathrm{\Delta }(G_1)`$ is rooted at $`Y_e`$ with $`e`$ connecting two leaves of $`\mathrm{\Delta }(G_0)`$, each edge on $`P_{r,h}`$ is traversed only once to reroot $`\mathrm{\Delta }(G)`$ for this case throughout all the iterations. Therefore, this case takes $`O(n)`$ total time.

Step 2b. This step takes $`O(|P_{w_1,w_2}|)`$ time per iteration. Since there are $`O(n)`$ iterations, by Lemma 7(4), this step takes $`O(n)`$ total time.

Step 2d. We bound the time for updating each item of $`\mathrm{\Delta }(G)`$ as follows.

Item 1 of $`\mathrm{\Delta }(G)`$. Notice that $`P_{w_1,w_2}`$ passes through the root of $`\mathrm{\Delta }(G_0)`$. Also, $`\mathrm{\Delta }(G_1)`$ is rooted at $`Y_2`$. These properties make it straightforward to update this item in $`O(|P_{w_1,w_2}|)`$ time per iteration. Since there are $`O(n)`$ iterations, by Lemma 7(4), this step takes $`O(n)`$ total time.

Item 2 of $`\mathrm{\Delta }(G)`$. By Lemma 16(1), $`\mathrm{\Lambda }(G_1)=\mathrm{\Lambda }(G_0)\{w_1,w_2\}`$. Thus it takes $`O(1)`$ time to update this item per iteration and $`O(n)`$ total time.

Item 3 of $`\mathrm{\Delta }(G)`$. Let $`u`$ be a c-vertex in $`\mathrm{\Delta }(G_0)`$. If $`uP_{w_1,w_2}`$, it has the same degree in $`\mathrm{\Delta }(G_0)`$ and $`\mathrm{\Delta }(G_1)`$ and is not relocated in this item. If $`uP_{w_1,w_2}`$, its degree reduces at most 2 in $`\mathrm{\Delta }(G_1)`$ and can be relocated in $`O(1)`$ time. Therefore, this item can be updated in $`O(|P_{w_1,w_2}|)`$ time per iteration, i.e., $`O(n)`$ total time as shown for Item 1.

## Acknowledgments

We are very grateful to Dan Gusfield for insightful discussions and to the anonymous referee for extremely thorough comments.


format: text

text:
# Variable Line Profiles Due to Non-Axisymmetric Patterns in an Accretion Disc around a Rotating Black Hole1

## 1. Introduction

Time-dependent phenomena are of extreme richness, variety, and observational relevance for accreting black-hole systems (e.g., Kato et al. 1998; Krolik 1999). Clearly, astrophysically realistic processes must result from the interplay of different factors which affect light-curves and produce spectral features. Here we concentrate on the X-ray spectral band.

Rapid temporal changes of the flux and of individual spectral features are observed in many active galactic nuclei (AGN) and in Galactic black-hole candidates (GBHCs). Variability patterns fit well with the widely adopted scenario of these objects as massive black holes surrounded by accretion flows, in the form of a disc or a torus (e.g., Ulrich et al. 1997). The X-ray variability of AGN and of GBHCs is often attributed to instabilities in their accretion flows causing changes in the inner and outer boundaries of the radiating disc region or relatively persistent non-axisymmetric inhomogeneities in the disc itself. This paper deals with variability properties which can be due to spiral structures forming in the inner part of the disc at distances $`<100r_\mathrm{g}`$ from the centre. We consider rotating (Kerr) black holes together with spiral waves of density perturbation in the disc matter. The waves are supposed to modify the emissivity pattern of the gaseous flow.

A power-law continuum is observed in X-ray spectra, which is thought to provide primary irradiation of the flow. Numerical computations of local reflection spectra from X-ray irradiated material suggest that the emissivity depends strongly on the nature and location of the primary source (e.g., Martocchia, Matt 1996; Martocchia 2000, and references therein), and also on the ionization structure and density profile of the flow (Done, Nayakshin 2001). Only in the case of density larger than a critical value and small ionization parameter, the matter behaves like a pure optically thick medium from which a typical cold iron line is emitted (Nayakshin et al. 2000; Dumont et al. 2000). The extent to which ionization in the disk influences emission and absorption features is subject of much debate.

As far as the power-law continuum is concerned, a plausible scheme suggests that this spectral component is produced in a hot Comptonizing medium (corona) above the disc. Another possibility is that magnetic reconnection causes temporary, strong flashes of radiation (flares) near the inflowing matter (Galeev et al. 1979; Coppi 1992; Haardt et al. 1994; Nayakshin 1998). Several mechanisms have been proposed for flares, but the available spectroscopy does not allow us to decide among them; see Malzac and Jourdain (2000) for recent discussion and further references. The flares are supposed to irradiate the gas in their neighbourhood, contributing to short-term variability (Mineshige et al. 1994; Yonehara et al. 1997). Furthermore, the coronal activity may be localized in asymmetric and rapidly evolving areas. In both cases (flares vs. inhomogeneous coronal activity) variations in the primary flux are expected, which also determine the variation in the additional spectral features due to Compton reflection (a continuum “hump”) and fluorescence (lines).

In this work we explored the expected spectral line profiles in the region where relativistic light-travel time, energy shift and lensing effects influence substantially the observed radiation fluxes, temporal variability, and the lines centroid energy. We assumed that a perturbation (of density and ionization structure) develops on length-scales of ten or a few tens of gravitational radii, giving rise to emissivity contrast against the background of the axisymmetric flow. The spirals become active after being illuminated from the primary source. Here, one has to distinguish between two cases: (i) the primary illumination independent from the origin of the spiral perturbation of the disc; (ii) the two phenomena (the disc perturbation and the flare) being connected to each other. The second case is particularly relevant for binary systems with Roche-lobe overflow; in such a situation, the outer end of the spiral pattern coincides with the place where the overflowing material hits the disc. This is the place where a flare or a spot develops. Therefore, we consider the emissivity variations with simultaneous contributions from the spiral pattern and from the flare.

We computed the predicted, variable line profiles with the aim of assessing the importance of the mentioned effects, especially the degree of the line flux and energy fluctuations that could be assigned to the existence of such non-axial structures. We also mention our computational approach, which can be adapted to different intrinsic emissivities and the source geometry, and, for the sake of illustration, we determine free parameters of the phenomenological model for the variable iron K$`\alpha `$ emission of the Seyfert galaxy MCG$``$6–30–15.

Rapid variations have been reported in the X-ray continuum and in the K$`\alpha `$ iron line of MCG$``$6–30–15 (6–7 keV), namely, Iwasawa et al. (1996, 1999) described the spectral changes which occurred during ASCA observations in 1994 and 1997. It is important to examine how the changes of selected spectral features — and the fluorescent iron feature in particular — reflect the changes in primary illumination, because this helps to constrain the geometry of the emitting regions, for instance by reverberation techniques (Reynolds et al. 1999; for a recent review, see Fabian et al. 2000).

We start the next section by giving some further hints on the physical models which justify our interest in considering the spiral-type patterns.

## 2. The Model

In AGN, variability time-scales go down to less than one hour, which is almost comparable with the light-crossing time ($`t_\mathrm{c}`$) at distances of the order of the gravitational radius ($`r_\mathrm{g}`$) of a supermassive black hole: $`t_\mathrm{c}10^2M_7`$ s, where $`M_7`$ is the central mass in units of $`10^7M_{}`$. Other time-scales relevant to black-hole accretion discs (orbital, thermal, sound-crossing, and viscous) are typically longer than $`t_\mathrm{c}`$. Characteristic time-scales of the observed variability also depend on the inclination of the system with respect to an observer, and can be scaled with the mass of the central object. Moreover, time intervals become longer very near to the hole if gravitational delays predicted by general relativity are taken into consideration.

### 2.1. Astrophysical Motivations

The irradiation of the disc from a varying source of primary X-rays does not lead to instantaneous response, but generates reflection or fluorescence. A delay occurs depending on the geometrical and physical state of the gaseous material. For example, Blandford and McKee (1982) and Taylor (1996) have discussed the intrinsic delays of the response in the case of clouds geometry, but here such effects are not considered for simplicity. Instead, it is the location of the primary source — often identified in one or more flaring regions — together with reflection patterns in the disc which determine the observed signal. A single variability event is therefore made of a primary flare and a complex response due to Compton reflection (or fluorescence, in the case of the iron line) by the disc matter at various distances from the hole.

Several people have considered the reprocessing of primary X-rays recently (for references, see Dumont et al. 2000; Karas et al. 2000; Nayakshin et al. 2000). Reprocessed radiation reaches the observer from different regions of the system. Individual rays experience unequal time lags of $`\delta t`$ for purely geometrical reasons, and other relativistic effects occur in the very vicinity of the hole and are relevant for the source variability, namely, lensing and Doppler boosting (Rauch, Blandford 1994). In the case of long-lived patterns ($`tt_\mathrm{c}`$) in the disc, there is, indeed, a substantial contribution to the variability caused by the orbital motion (Abramowicz et al. 1991; Mangalam, Wiita 1993). If the disc is strictly equatorial, two types of such patterns have been examined in more detail: spots (which could be identified with vortices in gaseous discs; cf. Abramowicz et al. 1992; Adams, Watkins 1995; Karas 1997), and spiral waves. In principle it is possible to distinguish different origins of the varying emission, namely, short-lived flares which decay on the dynamical time-scale versus long-duration features (Lawrence, Papadakis 1993; Kawaguchi et al. 2000). To that purpose, the geometry of the system needs to be constrained sufficiently. In addition to intrinsic variations, obscuration is involved along the path of light rays towards the observer. The light propagation is affected by the presence of refractive interstellar medium on the line of sight (Rickett et al. 1984) which contributes, together with internal and random obscuration, to rapid and high-amplitude flickering seen by the distant observer (Abrassart, Czerny 2000). These non-intrinsic effects are beyond the scope of this paper.

The spiral waves represent large-scale structures (size comparable with the radius), which can be induced by non-axisymmetric perturbations (Sanders, Huntley 1976; Wada 1994; Lee, Goodman 2000) or due to magnetic instabilities (Tagger et al. 1990). Also, a pattern resembling a single-armed spiral is produced from an extended spot after its decay due to shear motion in the differentially rotating disc. Even though such a pattern is only a transient feature, it may last sufficiently long to produce observable effects. Thus, the spirals are expected to arise naturally in accretion discs and to persist there for times longer than the orbital period of the flow particles. Sanders, Huntley (1976) demonstrated that the formation of a two-arm spiral wave is a natural response of differentially rotating gaseous discs to an oval gravitational perturbation, much like in the case of a self-gravitating stellar system into which the gas is assumed to be embedded. Recently, Kuo and Yuan (1999) examined the excitation of spiral waves in Lindblad resonances by comparing the asymptotic theory of bar-driven waves with the corresponding results of numerical computations. In a different way, Tagger and Pellat (1999) showed that spirals can be formed due to a certain kind of magnetic instability; such waves remain localized close to the inner radius of the disc. In general, spiral patterns can develop an odd or even number of arms depending on the type of the perturbing forces that act on the disc.

Spiral patterns have been treated in the theory of stellar systems, and widely discussed in the context of non-axisymmetric perturbations which can modify density profiles and emissivities of gas discs (Goldreich, Tremaine 1979; Sawada et al. 1986; Różyczka, Spruit 1993). The status of SPH computations was summarized recently by Lanzafame, Maravigna and Belvedere (2000) who examined the role of stellar-mass ratio on the formation of spiral structures in binaries. The spirals meet numerous applications also with respect to cataclysmic variables (Steeghs, Stehle 1999). Furthermore, the modulation of X-rays by spiral waves was also proposed with regard to polars (Murray et al. 1999).

Most of the attention with regard to spiral-waves spectral features has been motivated by studies of cataclysmic variables and other stellar-mass binary systems. It was noted that the variation in the density profile and ionization of accretion flows, predicted by numerical and semi-analytical methods, is followed by temperature modulation, and therefore by a change in the gas (thermal) emissivity within the spiral patterns. A similar effect is also expected for the X-ray irradiated accretion flows in AGN due to an increase in the matter density along the patterns (if optical thickness $`\tau \mathrm{}<1`$) or variations in the ionization structure (the emissivity is not sensitive to density changes if $`\tau 1`$). A phenomenological description appears to be adequate for the current scenario of X-rays reprocessing in AGN cores, and is convenient for the numerical computation of line profiles.

As far as AGNs are concerned, spiral waves have been explored as possible sources of spectral line variations in the context of broad emission-line regions (Chen, Halpern 1990; Chakrabarti, Wiita 1993, 1994; Eracleous 1998) and in maser sources (Maoz, McKee 1998). In these studies, because the radiation originates at distances $`\mathrm{}>10^3r_\mathrm{g}`$ from the centre, general-relativity effects are unimportant and variability time-scales are of the order of several months to years. On the other hand, Sanbuichi, Fukue and Kojima (1994) considered spirals extending close to a Schwarzschild black hole where the effects of general relativity play a role, and showed examples of relativistically distorted spectra.

### 2.2. A Toy Model of Spiral-Wave Emissivity

We parametrize the Kerr spacetime in terms of the black hole specific angular momentum $`(0a1)`$. In the disc plane, we consider both the spiral and a decaying spot localized at the spiral’s outer end (radial location and azimuth of the spot are thus determined by the spiral’s shape and its orientation with respect to the observer). Such a spot can represent a temporary off-axis flare (its maximum amplitude $`A_\mathrm{m}`$ is a free parameter). See figure 1 for a general scheme of the model.

The complexities of primary X-ray reprocessing are overpassed by directly parametrizing the emissivity. Our approach to the emissivity parametrization is close to the computations of Sanbuichi et al. (1994) and Bao and Wiita (1999), who considered a non-rotating black hole.

The spiral pattern is characterized by the emissivity distribution in the equatorial plane,

$$j_\mathrm{e}^{(\mathrm{s})}(\nu ;r_\mathrm{e},\phi _\mathrm{e})=j_0(\nu \nu _0)r_{\mathrm{e}}^{}{}_{}{}^{\gamma }\mathrm{sin}^\beta \phi _\mathrm{e}(r_\mathrm{e}),$$
(1)
where the frequency-dependent term, $`j_0`$, is taken as a narrow Gaussian profile, while the power-law index, $`\gamma `$, describes the overall radial decrease in the emissivity. The spiral rotates with respect to the observer, and its shape is logarithmic and determined by the function $`\phi _\mathrm{e}(r)=\phi +\alpha \mathrm{log}(r/r_0)`$, where $`\mathrm{arctan}\alpha `$ is the pitch angle, and $`r_0`$ is the outer radius where the wave is being excited.222The locally emitted intensity (denoted by subscript “e”) is related to the observed intensity at spatial infinity (subscript “o”) by the formula $`j_\mathrm{e}(\nu _\mathrm{e};t\delta t)/\nu _\mathrm{e}^3=j_\mathrm{o}(\nu _\mathrm{o};t)/\nu _\mathrm{o}^3,`$ where the ratio $`g\nu _\mathrm{o}/\nu _\mathrm{e}`$ defines the redshift factor and $`\delta t\delta t(r_\mathrm{e},\phi _\mathrm{e};\theta _\mathrm{o},a)`$ is time delay due to the light-travel time along the ray. See Fanton et al. (1997) and Martocchia, Karas and Matt (2000) for further details on ray-tracing computations. This parametrization approximates the spiral pattern evolving on the background of a Keplerian disc. The azimuthal form of the spiral depends also on the type of perturbation, so what we use here is one of the possible modes, which appears to be simple enough for illustration purposes.

As already discussed, the model takes inspiration from spirals in close binaries where a spot arises following the interaction between the stream (after the Roche-lobe overflow) and the disc (e.g., Wolf et al. 1998). The radiation flux in the spot decays with an e-folding time of $`q\mathrm{}>1`$ orbital periods, $`t_\mathrm{k}=2\pi (r_\mathrm{e}^{3/2}+a)`$. Again, the frequency-dependent part, $`j_0`$, of the spot intrinsic profile is taken in the Gaussian form and is assumed to be sufficiently narrow (its smearing is due mainly to radial component of the source orbital motion), while the amplitude, $`A(r,\phi )`$, decreases exponentially with the distance from the flare center located at $`r_0`$,

$$j_\mathrm{e}^{(\mathrm{f})}(\nu ;r_\mathrm{e},\phi _\mathrm{e})=j_0(\nu \nu _0)A(r_\mathrm{e},\phi _\mathrm{e})t^q.$$
(2)
Here, $`A(r,\phi )=A_\mathrm{m}\mathrm{exp}(\mathrm{\Delta }r)`$ with, typically, the spot size $`\mathrm{\Delta }r=|𝒓𝒓_0|\mathrm{}<1`$ and $`r_020`$. Hence, the resulting emissivity is a sum of contributions (1) and (2): $`j_\mathrm{e}=j_\mathrm{e}^{(\mathrm{s})}+j_\mathrm{e}^{(\mathrm{f})}`$.

It is the exact form of the emissivity distribution along the disc surface which determines the observed flux in the line wings and, in particular, which of the two wings — the bluish or the reddish one, appears more pronounced in the predicted spectrum. Thereby the lines are more complex than one would expect on the basis of intuition with simple ring-type sources (double-horn profiles). Here, we assume that a spiral with two arms extends from $`r=r_0`$ down to $`r_{\mathrm{ms}}`$, being terminated at the innermost stable orbit. Single-armed spirals show comparable spectral characteristics, but their variations occur with a double period and a somewhat higher amplitude, similar to the case of an elongated spot.

### 2.3. Light-Travel Time Near a Black Hole

Now we concentrate our attention on the consequences of finite light-travel time upon line variations.

One can write an order-of-magnitude (Euclidean) estimate of the maximum light-travel time delay, $`\delta t_\mathrm{m}`$, of rays originating in an equatorial ring (radius $`r_\mathrm{e}`$ centered on the black hole): $`\delta t_\mathrm{m}(r_\mathrm{e},\theta _\mathrm{o})\pi ^1r_\mathrm{e}^{1/2}\mathrm{sin}\theta _\mathrm{o}`$ ($`\theta _\mathrm{o}`$ is the observer’s inclination). Here, $`\delta t_\mathrm{m}`$ characterizes the mutual delay of the signals emitted at different parts of the ring, and is defined as the span in arrival times of the rays originating at different $`\phi _\mathrm{e}`$.333Light rays were approximated as straight lines for the purpose of estimating $`\delta t_\mathrm{m}`$ here. For consistency with subsequent paragraphs, the standard notation will be adopted for Kerr spacetime in Boyer–Lindquist coordinates (Misner et al. 1973). Geometrized units $`c=G=1`$ are used and all lengths are made dimensionless by expressing them in units of the typical mass of the central black hole, $`MM_710^7M_{}`$. Usually, $`r_\mathrm{e}`$ is supposed to be greater than a marginally stable orbit, $`r_{\mathrm{ms}}`$: $`r_{\mathrm{ms}}=3r_\mathrm{g}`$ for a non-rotating black hole with $`a=0,`$ and $`r_{\mathrm{ms}}r_\mathrm{g}`$ for a maximally rotating black hole, $`a1`$ ($`r_\mathrm{g}1+\sqrt{1a^2}`$). Light-travel time can be ignored provided $`\delta t_\mathrm{m}1`$. On the other hand, the lags become increasingly important when the radiation source extends very close to the black-hole horizon where the resulting situation is further complicated by the lensing effect.

The geometrical time lag can be roughly characterized by $`\delta t_\mathrm{m}`$, which indicates whether the Euclidean formula estimates the correct value of the light-travel time with an acceptable precision, or whether relativistic effects modify the actual delays significantly. Figure 2 gives $`\delta t_\mathrm{m}`$ for a source located at $`r_\mathrm{e}r_{\mathrm{ms}}`$. The solid curves represent the values of the delay computed in Kerr spacetime, while the dotted lines (slope $`1/2`$) show the approximation. Relativistic corrections become increasingly important for $`r_\mathrm{e}/r_\mathrm{g}\mathrm{}<3`$, in which case $`\delta t_\mathrm{m}`$ increases sharply. On the other hand, the difference between the exact value of $`\delta t_\mathrm{m}`$ and its Euclidean approximation is less than 10 % for a source location $`\mathrm{}>5r_\mathrm{g}`$.

Figure 3 shows the absolute value of light-travel time difference $`\delta t`$ between a reference ray (arbitrarily chosen but fixed) and a ray coming from a given point of emission $`\{r_\mathrm{e},\phi _\mathrm{e}\}`$ in the equatorial plane ($`\theta =90^\mathrm{o})`$. In this figure, $`\delta t`$ was calculated in Kerr metric (no approximation was used here). Given $`a`$ and $`\theta _\mathrm{o}`$, the values of $`\delta t`$ determine where in the disc the corrections on the time lag play an important role. Reference values of $`\delta t`$ can be transformed to physical units, as measured by a distant observer, by the relation $`\overline{\delta t}[\mathrm{s}]10^2M_7\delta t`$. The equatorial plane is portrayed from above (along the common rotation axis of the hole and of the disc), and a distant observer is located at the top (Cartesian $`y\mathrm{}`$; coordinates $`x`$ and $`y`$ are introduced in the disc plane by $`x^2+y^2=r_\mathrm{e}^2`$). Contours of constant time lag are almost horizontal far from the hole. A distortion of the contours from straight lines occurs near to the hole due to a lensing effect and gravitational delay. (Indeed, the contour lines can even become split into two disjoint parts.) Next, the redshift function, $`g`$, is also plotted by another set of contour lines in figure 3. Relativistic effects on the time lag and redshift are more important for a maximally rotating black hole (right panels) because of the smaller $`r_{\mathrm{ms}}`$.

### 2.4. Parameters of Spiral-Wave Line Profiles

Spiral-wave structures produce a rich variety of spectra and light curves, much broader than we can observe in the case of localized spots. Apart from the black hole angular momentum, $`a`$, and the orientation angle of the source with respect to observer, $`\theta _\mathrm{o}`$, one can identify several parameters related to the geometry and orbital motion of such spirals which determine the spectral variability:

$``$ The non-axisymmetric intrinsic emissivity of the source is described by equation (1) with free parameters ($`\alpha `$, $`\beta `$, $`\gamma `$, $`r_0`$) determining the azimuthal and radial dependence of emissivity.

$``$ Doppler shifts between the emitted and detected radiation increase the centroid energy and intensity of the rays originating at the approaching side of the source, and vice versa for the receding side (factor $`g^3`$). This effect tends to enlarge the width of the spectral features and to enhance the observed flux at its high-energy tail.

$``$ Gravitational redshift affects mainly photons coming from the inner parts of the source. This effect decreases the centroid energy of the line.

$``$ Light-travel time determines, along with the shape of the spiral, which photons are received at the same instant of time. We remark that contours of constant time delay are deformed near the hole. Hence, variability amplitude can be much accentuated if the spiral coincides with one of the contours at certain orbital phase. This effect influences the flux from some patterns under suitable orientation.

$``$ Gravitational lensing enhances the flux from the far side of the source (the part of the source which is at the upper conjunction with the hole). This tends to increase the observed flux around the centroid energy.

All parameters of the intrinsic emissivity and of the black hole spacetime enter in computations of the individual ray trajectories which form the resulting radiation flux at the detector. We find that the dependence of observed profiles on $`\gamma `$ is rather weak for a typical choice of $`0\mathrm{}<\gamma \mathrm{}<2`$. One should be aware of other implicit parameters which were kept fixed in the present model: the inner radius of the spiral pattern (here $`r_{\mathrm{ms}}`$), the (small) width of the intrinsic Gaussian local line profile, the number of spiral patterns (here $`n=2`$), and duration of the flare ($`>t_\mathrm{k}`$). In all of these computations, for the sake of simplicity the radiation was emitted isotropically in the rest frame of the gaseous medium.

## 3. Results

A typical line profile of a double-armed spiral is shown in figure 4 where the observed spectral feature is plotted as a function of the observed energy and orbital phase. The variation in the spectrum is shown over the whole revolution of the pattern by $`2\pi `$ in azimuth (as the normalized phase ranges from 0 to 1), while energy axis is normalized to the local emission energy, $`\nu _\mathrm{e}`$. Contours of the dynamical spectrum are shown by projecting the surface plot onto the plane of energy vs. phase. Here, one can clearly identify that the contribution of the spiral alone is repeated twice in each of the subplots (because we considered double arms), but the total signal does not bear this property because of the decaying flare contribution. Next, figures 5–6 show these contours for different model parameters. The contours are plotted with uniform spacings between the maximum flux and zero flux of the signal from which the underlying continuum is subtracted.

### 3.1. The Predicted Form of Observed Profiles

The parameter space has been explored systematically in the following manner.

$``$ Black-hole angular momentum: $`a=0`$ (columns denoted by letters a, c, e, g), and $`a=1`$ (b, d, f, h). The two cases correspond to a non-rotating and to maximally rotating hole, respectively.

$``$ Observer inclination: $`\theta _\mathrm{o}=20^\mathrm{o}`$ (the rows denoted by roman numbers iiii), $`\theta _\mathrm{o}=50^\mathrm{o}`$ (ivvi), and $`\theta _\mathrm{o}=80^\mathrm{o}`$ (viiix). The disc plane is $`\theta _\mathrm{o}=90^\mathrm{o}`$.

$``$ The outer edge of the spiral pattern: $`r_0=7`$ (i, iv, vii), $`r_0=13`$ (ii, v, viii), and $`r_0=20`$ (iii, vi, ix). Units of $`GM/c^2`$ are used.

$``$ The form of spiral pattern, as defined by its pitch angle $`\mathrm{arctan}\alpha `$ and contrast $`\beta `$ in eq. (1): $`\alpha =3`$, $`\beta =8`$ (a, b); $`\alpha =\sqrt{3}`$, $`\beta =8`$ (c, d); $`\alpha =6`$, $`\beta =8`$ (e, f); $`\alpha =6`$, $`\beta =18`$ (g, h). Large values of $`\beta `$ correspond to well-defined spirals (with small width and large contrast), while large values of $`\alpha `$ define tightly wound spirals (corresponding to high Mach number in the disc medium).

$``$ A contribution of the flare to the line in terms of its duration parameter, $`q=2`$ (units of the orbital period), and the initial flux, $`A_\mathrm{m}`$. The average ratio of the flare-to-spiral intrinsic emissivity in the centre of the line was taken as $`A_\mathrm{m}=1:2^4`$ for a weak flare (figure 5) and $`A_\mathrm{m}=1:1`$ for a strong one (figure 6).

In each of the sub-figures the spectra were computed with sufficient resolution in energy and phase ($`10^2\times 10^2`$ grid) by the ray-tracing code (Martocchia 2000).

One can recognize several characteristic features of the dynamical spectra. The flare is easily distinguished in figure 6 where it was assumed to be more intense with respect to the spiral pattern than in figure 5. However, even in the latter situation the Doppler boosted radiation of the flare dominates over the extended spiral when the disc is viewed at large inclination, and especially if the whole source is near to the horizon ($`r_07`$; see the row vii). Next, one can recognize the effect of gravitational redshift if the source is seen almost along the rotation axis (iiii), whereas this effect turns out to be less visible in very broad spectral features corresponding to large inclinations (viiix).

### 3.2. The Case of MCG$``$6–30–15

While the two plates in figures 5–6 has given us a general feeling for the influence of different parameters, a suitable ($`\chi ^2`$ minimizing) routine is used in practice for fitting the computed profiles to data.

Figure 7 shows the best fits to three iron-line profiles in MCG$``$6–30–15 (we use exactly the same data as defined by Iwasawa et al. 1996). These correspond to the spectral states of the source during its 1994 observation with the ASCA satellite. Here, we do not intend to exactly mimic what is going on in the source, because this appears to be premature with the available data. It is, however, possible to constrain the distance from the centre at which the line could originate, depending on the angular momentum of the hole and inclination of the observer.

The curves shown in the right panels are those to which the $`\chi ^2`$ minimizing routine converges in the parameter space (as described in subsection 3.1.). The reduced $`\chi ^2`$ is (from top to bottom): $`\chi ^2/𝖽.𝗈.𝖿.=72/53`$, $`40/55`$, $`60/40`$ for the three phases, respectively. Here, $`a=0`$, $`\theta _\mathrm{o}=20^\mathrm{o}`$, $`r_0=13`$, $`\alpha =6`$, $`\beta =18`$, $`A_\mathrm{m}=1/16`$. We thus find that the data are well fitted by the double arm at moderate inclination angles. In such a case, the dependence of the observed profile on $`a`$ is negligible because a substantial part of the line flux originates sufficiently above $`r_{\mathrm{ms}}`$.

## 4. Discussion

In the present work we did not intend to ameliorate the fits of MCG$``$6–30–15 data further. It is, however, worth noticing that even the adopted, rather simple scheme produces acceptable fits and the required, reddened line centroid also with small values of $`a`$. One can thus address the question if those redshifted and variable profiles of the iron line could be achieved without the necessity of invoking a large mass ($`>10^7M_{}`$) of the central object and/or its fast rotation, which have recently been put in certain doubt by several people. It is thus legitimate to consider all different viable options because various effects contribute to the line formation, and the interpretation of observed profiles is not straightforward.444Weaver and Yaqoob (1998) and Reynolds and Begelman (1997) proposed alternative schemes which do not involve fast rotation of the black hole. Nowak and Chiang (2000) discussed the possible caveats in interpretations of the present time-resolved spectra, and they concluded that the central mass is about $`10^6M_{}`$, much less than previously considered. A rather small mass, however, requires efficient emission, which also seems to pose a problem, so the issue has not been settled yet. A self-consistent interpretation of the profiles cannot be achieved without regard to the underlying continuum component where it is crucial to distinguish between line and continuum photons.

Our discussion is relevant for X-ray variability of some spectral states observed in AGN and GBHCs; it is quite obvious, however, that only a part of the complex variability behaviour could be attributed to motion of large scale structures, such as spiral waves. The model is complementary to the discussion of instant off-axis flares inducing the observed line variations, which enable one to restrict the geometry of the source by means of the reverberation technique. Proper evaluation of the light-travel time from different parts of the source is important in both schemes.

## 5. Conclusions

We computed variable line profiles due to non-axisymmetric spiral-type patterns near a Kerr black hole. We adopted several simplifying assumptions and constrained some of the parameters to fixed values. Yet, we could show that a big variety of line profiles are reproduced and the data of MCG$``$6–30–15 which we used for illustration purposes can be modeled without the necessity of $`a1`$, although such a possibility is not rejected. Because the existence of spiral features is expected on the basis of theoretical models, our discussion seems to be better substantiated than data fitting by ad hoc functions. Also, the adopted approach uses computed profiles, rather than being restricted to integral quantities (centroid energy, line width, etc.); it can thus provide robust results once better-resolved data become available.

Our present scheme can be considered as complementary to the picture of Reynolds et al. (1999) and Ruszkowski (2000), who examined off-axis flares above the disc surface as the origin of line variations, and to Vaughan and Edelson (2001), who addressed the problem of the link between line and continuum variations. Naturally, the phenomenological description of the source will have to be supplemented by a time-dependent physical model of X-ray reprocessing.

Although we applied our computations only to the case of MCG$``$6–30–15, there is a more general interest in the problem of spectral features from inner parts of gaseous discs endowed with spirals. Compact binaries with matter overflow represent another class of objects where our computations could be useful. Patterns like those discussed in this paper can be introduced in order to explain asymmetric lines and variability observed in UV/optical spectral bands from the broad-line region (Dumont, Collin-Soufrin 1990; Corbin 1997), and periodicities reported in the optical light curve of the blazar OJ 287 (Takalo 1994; Villata et al. 1998). In these cases, however, the radiation is emitted at distances exceeding $`10^3`$ gravitational radii, so that the general relativity calculations are unnecessary and the computations can be performed in a much faster way.

Even though the results cannot be conclusive with the present-day resolution, there is evident potentiality of this approach with planned missions, like Constellation-X and XEUS. The model of spirals illustrates the opportunity of tracing the surface structures on accretion discs.

We acknowledge support from the grants GACR 205/00/1685 and 202/99/0261. V K thanks for hospitality of the International School for Advanced Studies (Trieste) and Observatoire de Paris-Meudon.

## References

Abramowicz, M. A., Bao, G., Lanza, A., & Zhang, X.-H. 1991, A&A, 245, 454

Abramowicz, M. A., Lanza, A., Spiegel, E. A., & Szuszkiewicz, E. 1992, Nature, 356, 41

Abrassart, A., & Czerny, B. 2000, A&A, 356, 475

Adams, F. C., & Watkins, R. 1995, ApJ, 451, 314

Bao, G., & Wiita, P. 1999, ApJ, 519, 80

Blandford, F. D., & McKee, C. F. 1982, ApJ, 255, 419

Chakrabarti, S. K., & Wiita, P. J. 1993, A&A, 271, 216

Chakrabarti, S. K., & Wiita, P. J. 1994, ApJ, 434, 518

Chen, K., & Halpern, J. P. 1990, ApJ, 354, L1

Coppi, P. S. 1992, MNRAS, 258, 657

Corbin, M. R. 1997, ApJ, 485, 517

Done, C., & Nayakshin, S. 2001, ApJ, 546, 419

Dumont, A.-M., & Collin-Soufrin, S. 1990, A&A Suppl, 229, 313

Dumont, A.-M., Abrassart, A., & Collin, S. 2000, A&A, 357, 823

Eracleous, M. 1998, Adv. Space Res., 21, 33

Fabian, A. C., Iwasawa, K., Reynolds, C. S., & Young, A. J. 2000, PASP, 112, 1145

Fanton, C., Calvani, M., de Felice, F., & Čadež, A. 1997, PASJ, 49, 159

Galeev, A. A., Rosner, R., & Vaiana, G. S. 1979, ApJ, 229, 318

Goldreich, P., & Tremaine, S. 1979, ApJ, 233, 857

Haardt, F., Maraschi, L., & Ghisellini, G. 1994, ApJ, 432, L95

Iwasawa, K., Fabian, A. C., Young, A. J., Inoue, H., & Matsumoto, C. 1999, MNRAS, 306, L19

Iwasawa, K., Fabian, A. C., Reynolds, C. S., Nandra, K., Otani, C., Inoue, H., Hayashida, K., Brandt, W. N. et al. 1996, MNRAS, 282, 1038

Karas, V. 1997, MNRAS, 288, 12

Karas, V., Czerny B., Abrassart A., & Abramowicz M. A. 2000, MNRAS, 318, 547

Kato, S., Fukue, J., & Mineshige, S. 1998, Black-Hole Accretion Disks (Kyoto: Kyoto University Press)

Kawaguchi, T., Mineshige, S., Machida, M., Matsumoto, R., & Shibata, K. 2000, PASJ, 52, L1

Krolik, J. H. 1999, Active Galactic Nuclei: From the Central Black Hole to the Galactic Environment (Princeton: Princeton University Press)

Kuo, C.-L., & Yuan, C. 1999, ApJ, 512, 79

Lanzafame, G., Maravigna, F., & Belvedere, G. 2000, PASJ, 52, 515

Lawrence, A., & Papadakis, I. 1993, ApJ, 414, L85

Lee, E., & Goodman, J. 2000, MNRAS, 308, 984

Malzac, J., & Jourdain, E. 2000, A&A, 359, 843

Mangalam, A. V., & Wiita, P. J. 1993, ApJ, 406, 420

Maoz, E., & McKee, C. F. 1998, ApJ, 494, 218

Marsh, T. R., & Horne, K. 1988, MNRAS, 235, 269

Martocchia, A. 2000, X-ray Spectral Signatures of Accreting Black Holes, Ph.D. Thesis, SISSA Trieste

Martocchia, A., Karas, V., & Matt, G. 2000, MNRAS, 312, 817

Martocchia, A., & Matt, G. 1996, MNRAS, 282, L53

Misner, C. W., Thorne, K. S., & Wheeler, J. A. 1973, Gravitation (New York: W. H. Freeman and Co.)

Mineshige, S., Ouchi, N. B., & Nishimori, H. 1994, PASJ, 46, 97

Murray, J. R., Armitage, P. J., Ferrario, L., & Wickramasinghe, D. T. 1999, MNRAS, 302, 189

Nayakshin, S. V. 1998, Physics of Accretion Disks with Magnetic Flares, Ph.D. Thesis, University of Arizona

Nayakshin, S., Kazanas, D., & Kallman, T. R. 2000, ApJ, 537, 798

Nowak, M. A., & Chiang, J. 2000, ApJ, 531, L13

Rauch, K., & Blandford, R. D. 1994, ApJ, 421, 46

Reynolds, C. S., & Begelman, M. C. 1997, ApJ, 488, 109

Reynolds, C. S., Young, A. J., Begelman, M. C., & Fabian, A. C. 1999, ApJ, 514, 164

Rickett, B. J., Coles, W. A., & Bourgois, G. 1984, A&A, 134, 390

Różyczka, M., & Spruit, H. C. 1993, ApJ, 417, 677

Ruszkowski, M. 2000, MNRAS, 315, 1

Sanbuichi, K., Fukue, J., & Kojima, Y. 1994, PASJ, 46, 605

Sanders, R. H., & Huntley, J. M. 1976, ApJ 209, 53

Sawada, K., Matsuda, T., & Hachisu, I. 1986, MNRAS, 219, 75

Steeghs, D., & Stehle, R. 1999, MNRAS, 307, 99

Tagger, M., Henriksen, R. N., Sygnet, J. F., & Pellat, R. 1990, ApJ, 353, 654

Tagger, M., & Pellat, R. 1999, A&A, 349, 1003

Takalo, L. 1994, Vistas Astron., 38, 77

Taylor, J. A. 1996, ApJ, 470, 269

Ulrich, M.-H., Maraschi, L., & Urry, C. M. 1997, ARA&A, 35, 445

Vaughan, S., & Edelson, R. 2001, ApJ, preprint

Villata, M., Raiteri, C. M., Sillanpää, A., & Takalo, L. O. 1998, MNRAS, 293, L13

Wada, K. 1994, PASJ, 46, 165

Weaver, K. A., & Yaqoob, T. 1998, ApJ, 502, L139

Wolf, S., Barwig, H., Bobinger, A., Mantel, K.-H., & Šimić, D. 1998, A&A, 332, 984

Yonehara, A., Mineshige, S., & Welsh, W. F. 1997, ApJ, 486, 388