# Spectral expansion properties of pseudorandom bipartite graphs

Dandan Fana,b, Xiaofeng Guc, Huiqiu Lina
a School of Mathematics, East China University of Science and Technology,
Shanghai 200237, China
b College of Mathematics and Physics, Xinjiang Agricultural University,
Urumqi, Xinjiang 830052, China
c Department of Computing and Mathematics, University of West Georgia,
Carrollton, GA 30118, USA
Email<EMAIL_ADDRESS>(D. Fan<EMAIL_ADDRESS>(X. Gu<EMAIL_ADDRESS>(H. Lin)

###### Abstract

An $(a,b)$-biregular bipartite graph is a bipartite graph with bipartition
$(X,Y)$ such that each vertex in $X$ has degree $a$ and each vertex in $Y$ has
degree $b$. By the bipartite expander mixing lemma, biregular bipartite graphs
have nice pseudorandom and expansion properties when the second largest
adjacency eigenvalue is not large. In this paper, we prove several explicit
properties of biregular bipartite graphs from spectral perspectives. In
particular, we show that for any $(a,b)$-biregular bipartite graph $G$, if the
spectral gap is greater than $\frac{2(k-1)}{\sqrt{(a+1)(b+1)}}$, then $G$ is
$k$-edge-connected; and if the spectral gap is at least
$\frac{2k}{\sqrt{(a+1)(b+1)}}$, then $G$ has at least $k$ edge-disjoint
spanning trees. We also prove that if the spectral gap is at least
$\frac{(k-1)\max\\{a,b\\}}{2\sqrt{ab-(k-1)\max\\{a,b\\}}}$, then $G$ is
$k$-connected for $k\geq 2$; and if the spectral gap is at least
$\frac{6k+2\max\\{a,b\\}}{\sqrt{(a-1)(b-1)}}$, then $G$ has at least $k$ edge-
disjoint spanning 2-connected subgraphs. We have stronger results in the
paper.

MSC 2020: 05C50, 05C48, 05C40, 05C70

Key words: eigenvalue, pseudorandom bipartite graph, biregular graph,
connectivity, edge connectivity, spanning tree packing

##  1 Introduction

An expander graph is a sparse graph that has strong connectivity properties,
quantified using vertex, edge or spectral expansion. Expander graphs have many
applications in computer science such as complexity theory, communication
network, and the theory of error-correcting codes. Expanders are usually
regular graphs, however, unbalanced bipartite expanders are better suited for
applications in many situations. In particular, an idea of bipartite expander
graphs called magical graphs can be used to construct super concentrators and
good error correcting codes, see [34] for more details. In this paper, we
study bipartite expander properties from spectral perspectives.

Let $\lambda_{i}:=\lambda_{i}(G)$ denote the $i$th largest eigenvalue of the
adjacency matrix of a simple graph $G$ on $n$ vertices, for $i=1,2,\cdots,n$.
By the Perron-Frobenius Theorem, $\lambda_{1}$ is always positive (unless $G$
has no edges) and $|\lambda_{i}|\leq\lambda_{1}$ for all $i\geq 2$. If $G$ is
not a complete graph, then $\lambda_{2}$ is nonnegative. Let
$\lambda=\max_{2\leq i\leq
n}|\lambda_{i}|=\max\\{|\lambda_{2}|,|\lambda_{n}|\\}$, that is, $\lambda$ is
the second largest absolute eigenvalue. For a $d$-regular graph, it is well
known that $\lambda_{1}=d$. A $d$-regular graph on $n$ vertices with the
second largest absolute eigenvalue $\lambda$ is called an
$(n,d,\lambda)$-graph. The Alon-Boppana bound [1] states that $\lambda\geq
2\sqrt{d-1}-o(1)$. For non-bipartite $d$-regular graph $G$, if $\lambda(G)\leq
2\sqrt{d-1}$, then $G$ is a Ramanujan graph. Basically, Ramanujan graphs are
those graphs attaining the Alon-Boppana bound, and thus are expander graphs
with optimal asymptotic spectral properties.

A pseudorandom graph with $n$ vertices of edge density $p$ is a graph that
behaves like a truly random graph $G(n,p)$. The first quantitative definition
of pseudorandom graphs was introduced by Thomason [47, 48] who defined jumbled
graphs. It is well known that an $(n,d,\lambda)$-graph for which
$\lambda=\Theta(\sqrt{d})$ is a very good pseudorandom graph, according to the
celebrated expander mixing lemma. For more about pseudorandom graphs, see the
survey [37] by Krivelevich and Sudakov.

######  Theorem 1.1 (Expander mixing lemma).

Let $G$ be an $(n,d,\lambda)$-graph. Then for every two subsets $A$ and $B$ of
$V(G)$,

$\left|e(A,B)-\frac{d}{n}|A||B|\right|\leq\lambda\sqrt{|A||B|\left(1-\frac{|A|}{n}\right)\left(1-\frac{|B|}{n}\right)},$

where $e(A,B)$ denotes the number of edges with one end in $A$ and the other
end in $B$ $($edges with both ends in $A\cap B$ are counted twice$)$.

The expander mixing lemma is usually attributed to Alon and Chung [3].
However, this idea was used earlier with a different form in the PhD thesis
[32] of Haemers. In fact, Haemers provided the expander mixing lemma for
bipartite graphs.

An $(X,Y)$-bipartite graph is a bipartite graph with bipartition $(X,Y)$. An
$(X,Y)$-bipartite graph is called $(a,b)$-biregular if each vertex in $X$ has
degree $a$ and each vertex in $Y$ has degree $b$. Note that we must have
$a|X|=b|Y|$. It is known that $\lambda_{1}(G)=\sqrt{ab}$ and
$\lambda_{n}(G)=-\sqrt{ab}$ for any $(a,b)$-biregular bipartite graph $G$ on
$n$ vertices. Godsil and Mohar [24], Feng and Li [22], and Li and Solé [39]
proved an analog of Alon-Boppana bound that
$\lambda_{2}\geq\sqrt{a-1}+\sqrt{b-1}-o(1)$ for $(a,b)$-biregular bipartite
graphs. An $(a,b)$-biregular bipartite graph $G$ is Ramanujan if
$\lambda_{2}(G)\leq\sqrt{a-1}+\sqrt{b-1}$. In other words, biregular bipartite
Ramanujan graphs are those who attain the optimal lower bound of
$\lambda_{2}$. When $a=b$, we obtain regular bipartite Ramanujan graphs. It is
proven in [43] that there are infinite many $(a,b)$-biregular bipartite
Ramanujan graphs for $a,b\geq 3$. Explicit examples of biregular bipartite
Ramanujan graphs were constructed in [20]. For random biregular bipartite
graphs, the second largest eigenvalue has been studied in [4] and [51], while
the the spectral distribution was studied in [19] and [49].

For convenience, an $(a,b)$-biregular $(X,Y)$-bipartite graph is also called
an $(X,Y,a,b)$-graph. The following bipartite expander mixing lemma first
appeared in [32, Theorem 3.1.1] and also in [33, Theorem 5.1], but this exact
form and the proof can be found in [18].

######  Theorem 1.2 (Bipartite expander mixing lemma).

Let $G$ be an $(X,Y,a,b)$-graph on at least $3$ vertices. Then for every two
subsets $A\subseteq X$ and $B\subseteq Y$,

$\left|e(A,B)-\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|A||B|\right|\leq\lambda_{2}\sqrt{|A||B|\left(1-\frac{|A|}{|X|}\right)\left(1-\frac{|B|}{|Y|}\right)}.$

Note that $a|X|=b|Y|$ and it follows that
$\frac{\sqrt{ab}}{\sqrt{|X||Y|}}=\frac{b}{|X|}=\frac{a}{|Y|}$. Since the
spectrum of any bipartite graph is symmetric about zero, $\lambda_{2}$
actually is the third largest absolute eigenvalue. As mentioned in [18], the
bipartite expander mixing lemma is especially applicable when $\lambda_{2}$ is
small. In this case, for any two subsets $A\subseteq X$ and $B\subseteq Y$,
$e(A,B)$ is close to $\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|A||B|$. The edge
distribution is similar to the random bipartite graph and thus
$(X,Y,a,b)$-graphs are pseudorandom bipartite graphs.

##  2 Main results

In this section, we discover several explicit expander-related properties of
biregular bipartite graphs, including edge connectivity, vertex connectivity,
spanning tree packing number, as well as rigidity in the Euclidean plane.
These extend results of pseudorandom graphs to pseudorandom bipartite graphs.

###  2.1 Edge connectivity

The edge connectivity of a graph $G$, denoted by $\kappa^{\prime}(G)$, is the
minimum number of edges whose removal produces a disconnected graph. If
$\kappa^{\prime}(G)\geq k$, then $G$ is $k$-edge-connected. Krivelevich and
Sudakov [37] showed that any $(n,d,\lambda)$-graph $G$ with $d-\lambda\geq 2$
is $d$-edge-connected. The result was improved by Cioabă [10] using
$\lambda_{2}$. In fact, Cioabă [10] proved that for $d\geq k\geq 2$, if $G$ is
a $d$-regular graph of order $n$ with
$\lambda_{2}(G)<d-\frac{n(k-1)}{(d+1)(n-d-1)}$, then $\kappa^{\prime}(G)\geq
k$; and in particular, if $\lambda_{2}(G)<d-\frac{2(k-1)}{d+1}$, then
$\kappa^{\prime}(G)\geq k$. These imply corresponding results in pseudorandom
graphs. We would also like to point out that the results were generalized to
irregular cases in [30, 40]. Here we prove an analogue for biregular bipartite
graphs.

######  Theorem 2.1.

Let $G$ be an $(X,Y,a,b)$-graph with $a,b\geq k$. If

$\displaystyle\lambda_{2}<\sqrt{ab}-\frac{(k-1)\sqrt{|X||Y|}}{2\sqrt{\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}|X|-\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{)}\Big{(}|Y|-\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{)}}},$
(1)

then $\kappa^{\prime}(G)\geq k$. In particular, if

$\displaystyle\lambda_{2}<\sqrt{ab}-\frac{k-1}{\sqrt{\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{\lceil}\frac{b+1}{2}\Big{\rceil}}},$
(2)

then $\kappa^{\prime}(G)\geq k$.

Note that $\lambda_{1}-\lambda_{2}$ is usually called the spectral gap and
$\lambda_{1}=\sqrt{ab}$ for $(X,Y,a,b)$-graphs. The spectral gap of biregular
bipartite graphs has been shown to be very useful in error correcting codes,
matrix completion and community detection (see [4, 7, 46], among others). The
above theorem indicates that if the spectral gap is greater than
$\frac{k-1}{\sqrt{\lceil\frac{a+1}{2}\rceil\lceil\frac{b+1}{2}\rceil}}$, then
$G$ is $k$-edge-connected.

###  2.2 Vertex connectivity

The vertex connectivity of a graph $G$, denoted by $\kappa(G)$, is the minimum
number of vertices whose removal produces a disconnected graph. If
$\kappa(G)\geq k$, then $G$ is $k$-connected. By a result of Fiedler [23] on
algebraic connectivity, for a non-complete graph $G$,
$\kappa(G)\geq\delta-\lambda_{2}$, where $\delta$ is the minimum degree of
$G$. For any $(n,d,\lambda)$-graph $G$ with $d\leq n/2$, Krivelevich and
Sudakov[37] showed that $\kappa(G)\geq d-36\lambda^{2}/d$, and the result was
generalized in [27]. We study the vertex connectivity of biregular bipartite
graphs.

######  Theorem 2.2.

Let $G$ be an $(X,Y,a,b)$-graph with $a,b\geq k\geq 2$. If

$\displaystyle\lambda_{2}\leq\sqrt{ab}-\frac{(k-1)\max\\{a,b\\}}{2\sqrt{ab-(k-1)\max\\{a,b\\}}},$
(3)

then $\kappa(G)\geq k$.

In general, the theorem is not comparable with Fiedler’s result. But in many
cases, it seems our theorem can be better. For $d$-regular bipartite graphs
$G$, the theorem indicates that if $\lambda_{2}\leq
d-\frac{(k-1)\sqrt{d}}{2\sqrt{d-k+1}}$, then $\kappa(G)\geq k$, which is
stronger than Fiedler’s result when $\kappa(G)\leq 3d/4$. For any
$(a,b)$-biregular bipartite graph with $a\geq b\geq k\geq 2$, it implies that
if $\lambda_{2}\leq\sqrt{a}\left(\sqrt{b}-\frac{k-1}{2\sqrt{b-k+1}}\right)$,
then $\kappa(G)\geq k$. Apparently, the result would be better if $G$ is
unbalanced.

###  2.3 Edge-disjoint spanning trees

The spanning tree packing number (or simply STP number) of a graph $G$,
denoted by $\tau(G)$, is the maximum number of edge-disjoint spanning trees
contained in $G$. The well known spanning tree packing theorem (Theorem 3.1 in
the next section) by Nash-Williams [44] and independently by Tutte [50]
provides a structural characterization of graphs $G$ with $\tau(G)\geq k$. The
spanning tree packing number has been well studied from spectral perspectives.
In fact, by the connection between edge connectivity and the spanning tree
packing number, the result of Cioabă [10] implies that for any $d$-regular
connected graph $G$, if $\lambda_{2}(G)<d-\frac{2(2k-1)}{d+1}$ for $d\geq
2k\geq 4$, then $\kappa^{\prime}(G)\geq 2k$, and consequently $\tau(G)\geq k$.
Cioabă and Wong [15] conjectured that the sufficient condition can be improved
to $\lambda_{2}(G)<d-\frac{2k-1}{d+1}$, and they confirmed the conjecture for
$k=2,3$. Gu et al. [30] extended it to general graphs and provided some
partial results. The conjecture of Cioabă and Wong [15] was completely settled
in [41], in which the authors proved for general graphs $G$ that if
$\lambda_{2}(G)<\delta-\frac{2k-1}{\delta+1}$ for $\delta\geq 2k\geq 4$, then
$\tau(G)\geq k$, where $\delta$ denotes the minimum degree of $G$. Stronger
results via eigenvalues of other matrices were also obtained in [41]. Most
recently, the results of [41] have been shown to be essentially best possible
in [14] by constructing extremal graphs. Later on, a similar result in
pseudorandom graphs was proved in [27] via expander mixing lemma, and a
spectral radius condition was obtained in [21].

We study the problem in biregular bipartite graphs. Indeed, the result in [41]
for general graphs can be applied to bipartite graphs, however, we can prove
the following improved theorem.

######  Theorem 2.3.

Let $G$ be an $(X,Y,a,b)$-graph with $a,b\geq 2k$. If

$\displaystyle\lambda_{2}\leq\sqrt{ab}-\frac{k}{\sqrt{\lceil\frac{a+1}{2}\rceil\lceil\frac{b+1}{2}\rceil}},$

then $\tau(G)\geq k$.

The theorem indicates that if the spectral gap is at least
$\frac{k}{\sqrt{\lceil\frac{a+1}{2}\rceil\lceil\frac{b+1}{2}\rceil}}$, then
$G$ has at least $k$ edge-disjoint spanning trees.

###  2.4 Rigidity in the Euclidean plane

A $d$-dimensional bar-and-joint framework $(G,p)$ is the combination of an
undirected simple graph $G=(V(G),E(G))$ and a map
$p:V(G)\rightarrow\mathbb{R}^{d}$ that assigns a point in $\mathbb{R}^{d}$ to
each vertex of $G$. Let $\|\cdot\|$ denote the Euclidean norm in
$\mathbb{R}^{d}$. Two frameworks $(G,p)$ and $(G,q)$ are said to be equivalent
(resp., congruent) if $\|p(u)-p(v)\|=\|q(u)-q(v)\|$ holds for all $uv\in E(G)$
(resp., for all $u,v\in V(G)$). A framework $(G,p)$ is generic if the
coordinates of its points are algebraically independent over $\mathbb{Q}$. The
framework $(G,p)$ is rigid in $\mathbb{R}^{d}$ if there exists an
$\varepsilon>0$ such that every framework $(G,q)$ equivalent to $(G,p)$
satisfying $\|p(u)-q(u)\|<\varepsilon$ for all $u\in V(G)$ is actually
congruent to $(G,p)$. A generic framework $(G,p)$ is rigid in $\mathbb{R}^{d}$
if and only if every generic framework of $G$ is rigid in $\mathbb{R}^{d}$.
Hence, generic rigidity can be considered as a property of the underlying
graph. We say that a graph $G$ is rigid in $\mathbb{R}^{d}$ if every/some
generic framework of $G$ is rigid in $\mathbb{R}^{d}$, and it is redundantly
rigid in $\mathbb{R}^{d}$ if $G-e$ is rigid in $\mathbb{R}^{d}$ for every
$e\in E(G)$.

A framework $(G,p)$ is globally rigid in $\mathbb{R}^{d}$ if every framework
that is equivalent to $(G,p)$ is congruent to $(G,p)$. It was proved in [25]
that if there exists a generic framework $(G,p)$ in $\mathbb{R}^{d}$ that is
globally rigid, then any other generic framework $(G,q)$ in $\mathbb{R}^{d}$
is also globally rigid. Thus we say that $G$ is globally rigid in
$\mathbb{R}^{d}$ if there exists a globally rigid generic framework $(G,p)$ in
$\mathbb{R}^{d}$. By a combination of the results in [17, 35], a graph $G$ is
globally rigid in $\mathbb{R}^{2}$ if and only if $G$ is 3-connected and
redundantly rigid, or $G$ is a complete graph on at most three vertices.

In this paper, we consider rigidity in the Euclidean plane $\mathbb{R}^{2}$
only. Rigidity in $\mathbb{R}^{2}$ has been well studied. For a subset
$X\subseteq V(G)$, let $G[X]$ be the subgraph of $G$ induced by $X$ and $E(X)$
denote the edge set of $G[X]$. A graph $G$ is sparse if $|E(X)|\leq 2|X|-3$
for every $X\subseteq V(G)$ with $|X|\geq 2$. If in addition
$|E(G)|=2|V(G)|-3$, then $G$ is called a Laman graph. A graph $G$ is rigid in
$\mathbb{R}^{2}$ if and only if $G$ contains a spanning Laman subgraph. This
characterization was first discovered by Pollaczek-Geiringer [45] and
rediscovered by Laman [38], and thus is also called the Geiringer-Laman
condition. Lovász and Yemini [42] gave a new characterization of rigid graphs
and showed that every $6$-connected graph is globally rigid in
$\mathbb{R}^{2}$. This result was improved by [36] using an idea of mixed
connectivity and later by [31] using a relaxation of connectivity called
essential connectivity.

Cioabă, Dewar and Gu [12] studied spectral conditions for rigidity and global
rigidity in $\mathbb{R}^{2}$ via algebraic connectivity. One of the results
implies that for a graph $G$ with minimum degree $\delta\geq 6k$, if
$\lambda_{2}(G)<\delta-2-\frac{2k-1}{\delta-1}$, then $G$ contains at least
$k$ edge-disjoint spanning rigid subgraphs. For biregular bipartite graphs, we
prove the following different result.

######  Theorem 2.4.

Let $G$ be an $(X,Y,a,b)$-graph with $a,b\geq 6k$. If

$\displaystyle\lambda_{2}\leq\sqrt{ab}-\frac{3k+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-1}{2}\rceil\lceil\frac{b-1}{2}\rceil}},$

then $G$ has at least $k$ edge-disjoint spanning rigid subgraphs.

It is well known that any rigid graph with at least 3 vertices is 2-connected.
Thus Theorem 2.4 implies a sufficient condition for a biregular bipartite
graph containing $k$ edge-disjoint spanning 2-connected subgraphs, and so it
can be considered as an extension of Theorem 2.3.

######  Corollary 2.5.

Let $G$ be an $(a,b)$-biregular bipartite graph with $a,b\geq 6k$. If

$\lambda_{2}\leq\sqrt{ab}-\frac{3k+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-1}{2}\rceil\lceil\frac{b-1}{2}\rceil}},$

then $G$ has at least $k$ edge-disjoint spanning 2-connected subgraphs.

When $k=1$, we obtain a sufficient condition for rigid graphs.

######  Corollary 2.6.

Let $G$ be an $(a,b)$-biregular bipartite graph with $a,b\geq 6$. If

$\lambda_{2}\leq\sqrt{ab}-\frac{3+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-1}{2}\rceil\lceil\frac{b-1}{2}\rceil}},$

then $G$ is rigid.

We also discover a similar condition for global rigidity.

######  Theorem 2.7.

Let $G$ be an $(X,Y,a,b)$-graph with $a,b\geq 6$. If

$\displaystyle\lambda_{2}\leq\sqrt{ab}-\frac{3+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-2}{2}\rceil\lceil\frac{b-2}{2}\rceil}},$

then $G$ is globally rigid.

The rigidity of regular Ramanujan graphs and regular bipartite Ramanujan
graphs was studied in [11]. Recall that an $(a,b)$-biregular bipartite graph
is Ramanujan if $\lambda_{2}\leq\sqrt{a-1}+\sqrt{b-1}$. Our results imply the
rigidity of $(a,b)$-biregular bipartite Ramanujan graphs for given values of
$a,b$.

##  3 The proofs of main results

In this section, we will prove the theorems. One of the main tools is the
bipartite expander mixing lemma. Let $V(G)=V$ in the proofs below.

###  3.1 The proofs of Theorems 2.1, 2.2 and 2.3

###### The proof of Theorem 2.1.

Suppose to the contrary that there is a nonempty proper subset $A$ of $V(G)$
such that $e(A,V-A)\leq k-1$. First, notice that $A\cap X\neq\emptyset$, for
otherwise, $A\subseteq Y$ and so $e(A,V-A)=b|A|\geq k$, a contradiction.
Similarly $A\cap Y\neq\emptyset$. Let $A\cap X=S$, $A\cap Y=T$,
$X-S=S^{\prime}$ and $Y-T=T^{\prime}$. Then $(V-A)\cap X=S^{\prime}$ and
$(V-A)\cap Y=T^{\prime}$. It follows that
$e(A,V-A)=e(S,T^{\prime})+e(S^{\prime},T)$.

We claim that $2|S|\geq b+1$. Otherwise, $2|S|\leq b$, then
$e(A,V-A)=a|S|+b|T|-2e(S,T)\geq a|S|+b|T|-2|S||T|\geq a|S|\geq k$, which also
leads to a contradiction. Similarly, we have $2|S^{\prime}|\geq b+1$,
$2|T|\geq a+1$ and $2|T^{\prime}|\geq a+1$. Let $|X|=x$, $|Y|=y$, $|S|=s$ and
$|T|=t$. By Theorem 1.2,

$\displaystyle e(S,T^{\prime})$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|S||T^{\prime}|-\lambda_{2}\sqrt{|S||T^{\prime}|\left(1-\frac{|S|}{|X|}\right)\left(1-\frac{|T^{\prime}|}{|Y|}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
s(y-t)-\lambda_{2}\sqrt{s(y-t)\left(1-\frac{s}{x}\right)\left(1-\frac{y-t}{y}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
s(y-t)-\frac{\lambda_{2}}{\sqrt{xy}}\sqrt{s(y-t)(x-s)t}.$

Similarly,

$\displaystyle e(S^{\prime},T)$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|S^{\prime}||T|-\lambda_{2}\sqrt{|S^{\prime}||T|\left(1-\frac{|S^{\prime}|}{|X|}\right)\left(1-\frac{|T|}{|Y|}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot(x-s)t-\frac{\lambda_{2}}{\sqrt{xy}}\sqrt{(x-s)ts(y-t)}.$

Thus

$\displaystyle e(A,V-A)$ $\displaystyle=e(S,T^{\prime})+e(S^{\prime},T)$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{xy}}\cdot\left(s(y-t)+(x-s)t\right)-\frac{2\lambda_{2}}{\sqrt{xy}}\sqrt{s(x-s)t(y-t)}.$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
2\sqrt{s(x-s)t(y-t)}-\frac{2\lambda_{2}}{\sqrt{xy}}\sqrt{s(x-s)t(y-t)}.$
$\displaystyle=\frac{\sqrt{ab}-\lambda_{2}}{\sqrt{xy}}\cdot
2\sqrt{s(x-s)t(y-t)}.$

It is not hard to see that $s(x-s)$ is minimized at
$s=\lceil\frac{b+1}{2}\rceil$ or $s=x-\lceil\frac{b+1}{2}\rceil$, and $t(y-t)$
is minimized at $t=\lceil\frac{a+1}{2}\rceil$ or
$t=y-\lceil\frac{a+1}{2}\rceil$, and hence

$\displaystyle e(A,V-A)$
$\displaystyle\geq\frac{2\sqrt{ab}-2\lambda_{2}}{\sqrt{xy}}\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}x-\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{)}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{(}y-\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{)}}.$

By (1), we have $e(A,V-A)>k-1$, a contradiction. Therefore
$\kappa^{\prime}(G)\geq k$.

To prove (2) is also sufficient, notice that $x=|S|+|S^{\prime}|\geq
2\lceil\frac{b+1}{2}\rceil$ and so
$1-\frac{\lceil\frac{b+1}{2}\rceil}{x}\geq\frac{1}{2}$. Similarly,
$1-\frac{\lceil\frac{a+1}{2}\rceil}{y}\geq\frac{1}{2}$. Thus

$\displaystyle e(A,V-A)$
$\displaystyle\geq\frac{2\sqrt{ab}-2\lambda_{2}}{\sqrt{xy}}\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}x-\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{)}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{(}y-\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{)}}$
$\displaystyle=2(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}1-\frac{\lceil\frac{b+1}{2}\rceil}{x}\Big{)}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{(}1-\frac{\lceil\frac{a+1}{2}\rceil}{y}\Big{)}}$
$\displaystyle\geq(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{\lceil}\frac{b+1}{2}\Big{\rceil}}.$

By (2), we have $e(A,V-A)>k-1$, a contradiction. Therefore
$\kappa^{\prime}(G)\geq k$. ∎

###### The proof of Theorem 2.2.

Suppose to the contrary that $\kappa(G)\leq k-1$. Let $W$ be a vertex cut with
$|W|\leq k-1$ such that $|W\cap X|=k_{1}$, $|W\cap Y|=k_{2}$ and
$k_{1}+k_{2}\leq k-1$. Suppose that $A_{1},A_{2},\ldots,A_{p}$ are the
components of $G-W$, where $p\geq 2$. Without loss of generality, we assume
that $e(A_{1},W)\leq e(A_{2},W)\leq\cdots\leq e(A_{p},W)$. On the one hand, we
have
$e(A_{1},V-A_{1})=e(A_{1},W)\leq\frac{k_{1}a+k_{2}b}{p}\leq\frac{k_{1}a+k_{2}b}{2}$.
On the other hand, let $W\cap X=W_{1}$, $W\cap Y=W_{2}$, $A_{1}\cap X=S$,
$A_{1}\cap Y=T$, $X-(S\cup W_{1})=S^{\prime}$ and $Y-(T\cup
W_{2})=T^{\prime}$. It is easy to verify that $|S|\geq b-k_{1}$, $|T|\geq
a-k_{2}$, $|S^{\prime}|\geq b-k_{1}$ and $|T^{\prime}|\geq a-k_{2}$. Let
$|X|=x$, $|Y|=y$, $|S|=s$ and $|T|=t$. Then, by Theorem 1.2, we have

$\displaystyle e(S,Y-T)$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|S||Y-T|-\lambda_{2}\sqrt{|S||Y-T|\left(1-\frac{|S|}{|X|}\right)\left(1-\frac{|Y-T|}{|Y|}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
s(y-t)-\lambda_{2}\sqrt{s(y-t)\left(1-\frac{s}{x}\right)\left(1-\frac{y-t}{y}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
s(y-t)-\frac{\lambda_{2}}{\sqrt{xy}}\sqrt{s(y-t)(x-s)t}.$

Similarly,

$\displaystyle e(X-S,T)$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|X-S||T|-\lambda_{2}\sqrt{|X-S||T|\left(1-\frac{|X-S|}{|X|}\right)\left(1-\frac{|T|}{|Y|}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot(x-s)t-\frac{\lambda_{2}}{\sqrt{xy}}\sqrt{(x-s)ts(y-t)}.$

Thus

$\displaystyle e(A_{1},V-A_{1})$ $\displaystyle=e(S,Y-T)+e(X-S,T)$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{xy}}\cdot\left(s(y-t)+(x-s)t\right)-\frac{2\lambda_{2}}{\sqrt{xy}}\sqrt{s(x-s)t(y-t)}.$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
2\sqrt{s(x-s)t(y-t)}-\frac{2\lambda_{2}}{\sqrt{xy}}\sqrt{s(x-s)t(y-t)}.$
$\displaystyle=\frac{\sqrt{ab}-\lambda_{2}}{\sqrt{xy}}\cdot
2\sqrt{s(x-s)t(y-t)}.$

Observe that $s(x-s)$ is minimized at $s=b-k_{1}$, and $t(y-t)$ is minimized
at $t=a-k_{2}$. Thus

$e(A_{1},V-A_{1})\geq\frac{2(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{(b-k_{1})(x-(b-k_{1}))(a-k_{2})(y-(a-k_{2}))}.$

Since $k=k_{1}+k_{2}>0$, at least one of $k_{1}$ and $k_{2}$ is more than 0.
Assume that $k_{1}>0$ (the case $k_{2}>0$ is similar). Then
$x=|S|+|S^{\prime}|+k_{1}>2(b-k_{1})$ and $y=|T|+|T^{\prime}|+k_{2}\geq
2(a-k_{2})$, and hence $1-\frac{b-k_{1}}{x}>\frac{1}{2}$ and
$1-\frac{a-k_{2}}{y}\geq\frac{1}{2}$. Therefore,

$\displaystyle e(A_{1},V-A_{1})$
$\displaystyle\geq\frac{2(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{(b-k_{1})(x-(b-k_{1}))(a-k_{2})(y-(a-k_{2}))}$
(4)
$\displaystyle=2(\sqrt{ab}-\lambda_{2})\cdot\sqrt{(b-k_{1})\Big{(}1-\frac{b-k_{1}}{x}\Big{)}(a-k_{2})\Big{(}1-\frac{a-k_{2}}{y}\Big{)}}$
$\displaystyle>(\sqrt{ab}-\lambda_{2})\cdot\sqrt{(a-k_{2})(b-k_{1})}.$

Notice that $k_{1}a+k_{2}b\leq
k_{1}\max\\{a,b\\}+k_{2}\max\\{a,b\\}\leq(k-1)\max\\{a,b\\}$, and so
$(a-k_{2})(b-k_{1})=ab-(k_{1}a+k_{2}b)+k_{1}k_{2}\geq ab-(k-1)\max\\{a,b\\}$.
By (3) and (4),

$\displaystyle
e(A_{1},V-A_{1})>(\sqrt{ab}-\lambda_{2})\cdot\sqrt{ab-(k-1)\max\\{a,b\\}}\geq\frac{(k-1)\max\\{a,b\\}}{2}\geq\frac{k_{1}a+k_{2}b}{2},$

a contradiction. Thus $\kappa(G)\geq k$. ∎

To prove Theorem 2.3, we need the spanning tree packing theorem. Let
$(V_{1},\ldots,V_{t})$ be a sequence of disjoint vertex subsets of $V(G)$ and
$e(V_{1},\ldots,V_{t})$ be the number of edges whose ends lie in different
$V_{i}$’s. The following fundamental theorem on spanning tree packing number
was established by Nash-Williams [44] and Tutte [50], independently.

######  Theorem 3.1 (Nash-Williams [44] and Tutte [50]).

Let $G$ be a connected graph. Then $\tau(G)\geq k$ if and only if for any
partition $(V_{1},\ldots,V_{t})$ of $V(G)$,

$e(V_{1},\ldots,V_{t})\geq k(t-1).$

###### The proof of Theorem 2.3.

Assume to the contrary that $\tau(G)\leq k-1$. By Theorem 3.1, there exists a
partition $(V_{1},V_{2},\cdots,V_{t})$ of $V(G)$ such that

$\displaystyle e(V_{1},V_{2},\cdots,V_{t})\leq k(t-1)-1.$ (5)

Without loss of generality, we assume that $e(V_{1},V-V_{1})\leq
e(V_{2},V-V_{2})\leq\cdots\leq e(V_{t},V-V_{t})$. Let $p$ be the largest index
such that $e(V_{p},V-V_{p})\leq 2k-1$. We first claim that $p\geq 2$, for
otherwise if $p\leq 1$, then $e(V_{2},V-V_{2})\geq 2k$, and so

$e(V_{1},V_{2},\cdots,V_{t})=\frac{1}{2}\sum_{1\leq i\leq
t}e(V_{i},V-V_{i})\geq\frac{1}{2}\sum_{2\leq i\leq t}e(V_{i},V-V_{i})\geq
k(t-1),$

contradicting (5). Thus $p\geq 2$.

We assert that $V_{i}\cap X\neq\emptyset$ for $1\leq i\leq p$. If not, there
exists some $j$ ($1\leq j\leq p$) such that $V_{j}\subseteq Y$, and thus,
$e(V_{j},V-V_{j})=b|V_{j}|\geq 2k$, a contradiction. Similarly $V_{i}\cap
Y\neq\emptyset$ for $1\leq i\leq p$. Let $V_{i}\cap X=S_{i}$, $V_{i}\cap
Y=T_{i}$, $X-S_{i}=S_{i}^{\prime}$ and $Y-T_{i}=T^{\prime}_{i}$ where $1\leq
i\leq p$. We next assert that $2|S_{i}|\geq b+1$ for $1\leq i\leq p$.
Otherwise if $2|S_{i}|\leq b$ for $1\leq i\leq p$, then

$\displaystyle e(V_{i},V-V_{i})$
$\displaystyle=a|S_{i}|+b|T_{i}|-2e(S_{i},T_{i})$ $\displaystyle\geq
a|S_{i}|+b|T_{i}|-2|S_{i}||T_{i}|$ $\displaystyle\geq
a|S_{i}|+b|T_{i}|-b|T_{i}|~{}~{}~{}(\mbox{since $2|S_{i}|\leq b$})$
$\displaystyle=a|S_{i}|$ $\displaystyle\geq 2k~{}~{}(\mbox{since $a\geq 2k$
and $|S_{i}|\geq 1$}),$

a contradiction. Similarly, we have $2|S^{\prime}_{i}|\geq b+1$, $2|T_{i}|\geq
a+1$ and $2|T^{\prime}_{i}|\geq a+1$ for $1\leq i\leq p$.

Let $|X|=x$, $|Y|=y$, $|S_{i}|=s_{i}$ and $|T_{i}|=t_{i}$ where $1\leq i\leq
p$. By Theorem 1.2, for $1\leq i\leq p$, we have

$\displaystyle e(S_{i},T^{\prime}_{i})$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|S_{i}||T^{\prime}_{i}|-\lambda_{2}\sqrt{|S_{i}||T^{\prime}_{i}|\left(1-\frac{|S_{i}|}{|X|}\right)\left(1-\frac{|T^{\prime}_{i}|}{|Y|}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
s_{i}(y-t_{i})-\lambda_{2}\sqrt{s_{i}(y-t_{i})\left(1-\frac{s_{i}}{x}\right)\left(1-\frac{y-t_{i}}{y}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
s_{i}(y-t_{i})-\frac{\lambda_{2}}{\sqrt{xy}}\sqrt{s_{i}t_{i}(y-t_{i})(x-s_{i})}.$

and

$\displaystyle e(S^{\prime}_{i},T_{i})$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{|X||Y|}}|S^{\prime}_{i}||T_{i}|-\lambda_{2}\sqrt{|S^{\prime}_{i}||T_{i}|\left(1-\frac{|S^{\prime}_{i}|}{|X|}\right)\left(1-\frac{|T_{i}|}{|Y|}\right)}$
$\displaystyle=\frac{\sqrt{ab}}{\sqrt{xy}}\cdot(x-s_{i})t_{i}-\frac{\lambda_{2}}{\sqrt{xy}}\sqrt{s_{i}t_{i}(x-s_{i})(y-t_{i})}.$

Thus, for $1\leq i\leq p$,

$\displaystyle e(V_{i},V-V_{i})$
$\displaystyle=e(S_{i},T^{\prime}_{i})+e(S^{\prime}_{i},T_{i})$ (6)
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{xy}}\cdot\left(s_{i}(y-t_{i})+(x-s_{i})t_{i}\right)-\frac{2\lambda_{2}}{\sqrt{xy}}\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})}$
$\displaystyle\geq\frac{\sqrt{ab}}{\sqrt{xy}}\cdot
2\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})}-\frac{2\lambda_{2}}{\sqrt{xy}}\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})}$
$\displaystyle=\frac{2(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})}.$

Note that $s_{i}(x-s_{i})$ attains the minimum value at
$s_{i}=\lceil\frac{b+1}{2}\rceil$ and $t_{i}(y-t_{i})$ attains the minimum
value at $t_{i}=\lceil\frac{a+1}{2}\rceil$ for $1\leq i\leq p$. Thus

$\displaystyle e(V_{1},V_{2},\cdots,V_{t})$
$\displaystyle=\frac{1}{2}\Big{(}\sum_{1\leq i\leq
p}e(V_{i},V-V_{i})+\sum_{p+1\leq i\leq t}e(V_{i},V-V_{i})\Big{)}$
$\displaystyle\geq\frac{p(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})}+k(t-p)$
$\displaystyle\geq\frac{p(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}x-\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{)}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{(}y-\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{)}}+k(t-p).$

Notice that $x\geq\sum_{1\leq i\leq p}|S_{i}|\geq p\lceil\frac{b+1}{2}\rceil$
and $y\geq\sum_{1\leq i\leq p}|T_{i}|\geq p\lceil\frac{a+1}{2}\rceil$. Then
$1-\frac{\lceil\frac{b+1}{2}\rceil}{x}\geq\frac{p-1}{p}$ and
$1-\frac{\lceil\frac{a+1}{2}\rceil}{y}\geq\frac{p-1}{p}$, and hence

$\displaystyle e(V_{1},V_{2},\cdots,V_{t})$
$\displaystyle\geq\frac{p(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}x-\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{)}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{(}y-\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{)}}+k(t-p)$
$\displaystyle=p(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{(}1-\frac{\lceil\frac{b+1}{2}\rceil}{x}\Big{)}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}\Big{(}1-\frac{\lceil\frac{a+1}{2}\rceil}{y}\Big{)}}+k(t-p)$
$\displaystyle\geq
p(\sqrt{ab}-\lambda_{2})\cdot\frac{p-1}{p}\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}}+k(t-p)$
$\displaystyle=(p-1)(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{b+1}{2}\Big{\rceil}\Big{\lceil}\frac{a+1}{2}\Big{\rceil}}+k(t-p)$
$\displaystyle\geq(p-1)k+k(t-p)=k(t-1)$

when
$\lambda_{2}\leq\sqrt{ab}-\frac{k}{\sqrt{\lceil\frac{a+1}{2}\rceil\lceil\frac{b+1}{2}\rceil}}$.
This contradicts (5). Thus the result follows. ∎

###  3.2 The proofs of Theorems 2.4 and 2.7

For any partition $\pi$ of $V(G)$, let $E_{G}(\pi)$ denote the set of edges in
$G$ whose endpoints lie in different parts of $\pi$, and let
$e_{G}(\pi)=|E_{G}(\pi)|$. A part is trivial if it contains a single vertex.
Let $Z\subset V(G)$, and let $\pi$ be a partition of $V(G-Z)$ with $n_{0}$
trivial parts $v_{1},v_{2},\ldots,v_{n_{0}}$. Denote by
$n_{Z}(\pi)=\sum_{1\leq i\leq n_{0}}|Z_{i}|$, where $Z_{i}$ is the set of
vertices in $Z$ that are adjacent to $v_{i}$ for $1\leq i\leq n_{0}$. For any
$v\in V(G)$, let $N_{G}(v)$ and $d_{G}(v)$ be the neighborhood and degree of
$v$ in $G$, respectively. For any vertex $v\in V(G)$ and any subset $S\subset
V(G)$, let $d_{S}(v)=|N_{G}(v)\cap S|$.

######  Lemma 3.2 ([26]).

A graph $G$ contains $k$ edge-disjoint spanning rigid subgraphs if for every
$Z\subset V(G)$ and every partition $\pi$ of $V(G-Z)$ with $n_{0}$ trivial
parts and $n_{0}^{\prime}$ nontrivial parts,

$e_{G-Z}(\pi)\geq k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi).$

###### The proof of Theorem 2.4.

Assume to the contrary that $G$ contains no $k$ edge-disjoint spanning rigid
subgraphs. By Lemma 3.2, there exist a subset $Z$ of $V$ and a partition $\pi$
of $V(G-Z)$ with $n_{0}$ trivial parts $v_{1},v_{2},\ldots,v_{n_{0}}$ and
$n_{0}^{\prime}$ nontrivial parts $V_{1},V_{2},\ldots,V_{n_{0}^{\prime}}$ such
that

$\displaystyle e_{G-Z}(\pi)\leq
k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi)-1,$ (7)

where $n_{Z}(\pi)=\sum_{1\leq i\leq n_{0}}|Z_{i}|$, and $Z_{i}$ is the set of
vertices in $Z$ that are adjacent to $v_{i}$ for $1\leq i\leq n_{0}$. Let
$V(G-Z)=V^{*}$ and let $\delta$ be the minimum degree of $G$. Then
$\delta=\min\\{a,b\\}\geq 6k$. Observe that
$d_{G-Z}(v_{i})\geq\delta-|Z_{i}|\geq 6k-|Z_{i}|$ for $1\leq i\leq n_{0}$.
Thus

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle=\frac{1}{2}\left(\sum_{1\leq i\leq
n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G-Z}(v_{j})\right)$ $\displaystyle\geq\frac{1}{2}\left(\sum_{1\leq
i\leq n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+\delta n_{0}-\sum_{1\leq j\leq
n_{0}}|Z_{j}|\right)$ $\displaystyle\geq\frac{1}{2}\left(\sum_{1\leq i\leq
n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+6kn_{0}-n_{Z}(\pi)\right),$

and hence

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle\geq
3kn_{0}-\frac{1}{2}n_{Z}(\pi).$ (8)

We have the following two claims.

Claim 1.

$|Z|\leq 2$.

Otherwise, $|Z|\geq 3$. By (7),

$\displaystyle e_{G-Z}(\pi)\leq
k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi)-1\leq 2kn_{0}-3k-n_{Z}(\pi)-1.$

Combining this with (8) yields that $kn_{0}+3k+\frac{1}{2}n_{Z}(\pi)+1\leq 0$,
which is impossible because $n_{0}\geq 0$, $k\geq 1$ and $n_{Z}(\pi)\geq 0$.

Claim 2.

$n_{0}^{\prime}\geq 2$.

Otherwise, $n_{0}^{\prime}\leq 1$. By Claim 1 and (7), we get

$\displaystyle e_{G-Z}(\pi)\leq
k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi)-1\leq 2kn_{0}-k|Z|-1-n_{Z}(\pi).$

Combining this with (8), we have $kn_{0}+1+\frac{1}{2}n_{Z}(\pi)+k|Z|\leq 0$,
which is also impossible.

Assume that $e(V_{1},V^{*}-V_{1})\leq e(V_{2},V^{*}-V_{2})\leq\cdots\leq
e(V_{n^{\prime}_{0}},V^{*}-V_{n^{\prime}_{0}})$. Let $q$ be the largest index
such that $e(V_{q},V^{*}-V_{q})\leq 6k-2k|Z|-1$. We first assert that $q\geq
2$. If not, $e(V_{2},V^{*}-V_{2})\geq 6k-2k|Z|$. Then

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle=\frac{1}{2}\left(\sum_{1\leq i\leq
n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G-Z}(v_{j})\right)$
$\displaystyle\geq\frac{1}{2}\left((6k-2k|Z|)(n^{\prime}_{0}-1)+6kn_{0}-n_{Z}(\pi)\right)$
$\displaystyle=k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi)-1+kn_{0}+1+k|Z|+\frac{1}{2}n_{Z}(\pi)$
$\displaystyle>k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi)-1~{}~{}(\mbox{since
$|Z|\geq 0$, $n_{Z}(\pi)\geq 0$, $k\geq 1$ and $n_{0}\geq 0$}),$

contradicting (7). This implies that $q\geq 2$. We next assert that $V_{i}\cap
X\neq\emptyset$ for $1\leq i\leq q$. If not, there exists some $j$ ($1\leq
j\leq q$) such that $V_{j}\subseteq Y$. Combining this with Claim 1,
$|V_{j}|\geq 2$, $k\geq 1$ and $b\geq 6k$, we have

$e(V_{j},V^{*}-V_{j})\geq e(V_{j},V-V_{j})-|Z||V_{j}|=(b-|Z|)|V_{j}|\geq
2(b-|Z|)>6k-2k|Z|,$

a contradiction. Similarly $V_{i}\cap Y\neq\emptyset$ for $1\leq i\leq q$. Let
$V_{i}\cap X=S_{i}$, $V_{i}\cap Y=T_{i}$, $X-S_{i}=S_{i}^{\prime}$ and
$Y-T_{i}=T^{\prime}_{i}$ where $1\leq i\leq q$. We also assert that
$2|S_{i}|\geq b+1-|Z|$ for $1\leq i\leq q$. If not, there exists some $j$
($1\leq j\leq q$) such that $2|S_{j}|\leq b-|Z|$. Since
$d_{V_{j}}(v)\leq\max\\{|S_{j}|,|T_{j}|\\}$ for each $v\in Z$, it follows that

$\displaystyle e(V_{j},V^{*}-V_{j})$ $\displaystyle\geq
a|S_{j}|+b|T_{j}|-2e(S_{j},T_{j})-|Z|\max\\{|S_{j}|,|T_{j}|\\}$
$\displaystyle\geq
a|S_{j}|+b|T_{j}|-2|S_{j}||T_{j}|-|Z|\max\\{|S_{j}|,|T_{j}|\\}$
$\displaystyle\geq
a|S_{j}|+|Z||T_{j}|-|Z|\max\\{|S_{j}|,|T_{j}|\\}~{}~{}~{}(\mbox{since
$2|S_{j}|\leq b-|Z|$})$ $\displaystyle\geq a~{}~{}(\mbox{since $0\leq|Z|\leq
2$, $|T_{j}|\geq 1$ and $|S_{j}|\geq 1$})$ $\displaystyle\geq
6k-2k|Z|~{}~{}(\mbox{since $a\geq 6k$, $k\geq 1$ and $0\leq|Z|\leq 2$}),$

a contradiction. Similarly, we have $2|S^{\prime}_{i}|\geq b+1-|Z|$,
$2|T_{i}|\geq a+1-|Z|$ and $2|T^{\prime}_{i}|\geq a+1-|Z|$ for $1\leq i\leq
q$. Let $|X|=x$, $|Y|=y$, $|S_{i}|=s_{i}$ and $|T_{i}|=t_{i}$ where $1\leq
i\leq q$. By using the same argument as (6), we have

$e(V_{i},V-V_{i})\geq\frac{2(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})},$

where $1\leq i\leq q$. Note that $s_{i}(x-s_{i})$ is minimized at
$s_{i}=\lceil\frac{b+1-|Z|}{2}\rceil$, and $t_{i}(y-t_{i})$ is minimized at
$t_{i}=\lceil\frac{a+1-|Z|}{2}\rceil$. Then for $1\leq i\leq q$,

$e(V_{i},V-V_{i})\geq\frac{2(\sqrt{ab}\\!-\\!\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{\Big{\lceil}\frac{b+1\\!-\\!|Z|}{2}\Big{\rceil}\Big{(}x\\!-\\!\Big{\lceil}\frac{b+1\\!-\\!|Z|}{2}\Big{\rceil}\Big{)}\Big{\lceil}\frac{a\\!+\\!1-|Z|}{2}\Big{\rceil}\Big{(}y\\!-\\!\Big{\lceil}\frac{a+1\\!-\\!|Z|}{2}\Big{\rceil}\Big{)}}.$

Notice that $x\geq\sum_{1\leq i\leq q}|S_{i}|\geq
q\lceil\frac{b+1-|Z|}{2}\rceil$ and $y\geq\sum_{1\leq i\leq q}|T_{i}|\geq
q\lceil\frac{a+1-|Z|}{2}\rceil$. Thus
$1-\frac{\lceil\frac{b+1-|Z|}{2}\rceil}{x}\geq\frac{q-1}{q}$ and
$1-\frac{\lceil\frac{a+1-|Z|}{2}\rceil}{y}\geq\frac{q-1}{q}$. Combining this
with $d_{G}(v)\leq\max\\{a,b\\}$ for each $v\in Z$, $e(V_{i},V-V_{i})\geq
e(V_{i},V^{*}-V_{i})\geq 6k-2k|Z|$ for $q+1\leq i\leq n^{\prime}_{0}$ and
$d_{G}(v_{i})\geq 6k$ for $1\leq i\leq n_{0}$, we have

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle=\frac{1}{2}\left(\sum_{1\leq i\leq
n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G-Z}(v_{j})\right)$ $\displaystyle\geq\frac{1}{2}\left(\sum_{1\leq
i\leq n_{0}^{\prime}}e(V_{i},V-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G}(v_{j})-|Z|\max\\{a,b\\}\right)$ $\displaystyle\geq
q(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{b+1-|Z|}{2}\Big{\rceil}\Big{(}1\\!-\\!\frac{\lceil\frac{b+1-|Z|}{2}\rceil}{x}\Big{)}\Big{\lceil}\frac{a+1-|Z|}{2}\Big{\rceil}\Big{(}1\\!-\\!\frac{\lceil\frac{a+1-|Z|}{2}\rceil}{y}\Big{)}}\\!+\\!k(n^{\prime}_{0}\\!-\\!q)(3\\!-\\!|Z|)$
$\displaystyle~{}~{}~{}+\frac{\sum_{1\leq j\leq
n_{0}}d_{G}(v_{j})}{2}-\frac{|Z|\max\\{a,b\\}}{2}$
$\displaystyle\geq(q-1)(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{a+1-|Z|}{2}\Big{\rceil}\Big{\lceil}\frac{b+1-|Z|}{2}\Big{\rceil}}+k(n^{\prime}_{0}-q)(3-|Z|)+3kn_{0}-\frac{|Z|\max\\{a,b\\}}{2}$
$\displaystyle=k(3\\!-\\!|Z|)n_{0}^{\prime}\\!+\\!2kn_{0}\\!-\\!3k\\!-\\!n_{Z}(\pi)-1\\!+\\!(q\\!-\\!1)(\sqrt{ab}\\!-\\!\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{a\\!+\\!1\\!-\\!|Z|}{2}\Big{\rceil}\Big{\lceil}\frac{b\\!+\\!1\\!-\\!|Z|}{2}\Big{\rceil}}\\!+\\!kn_{0}+n_{Z}(\pi)$
$\displaystyle~{}~{}+qk|Z|-\frac{|Z|\max\\{a,b\\}}{2}-3k(q-1)+1$
$\displaystyle\geq
k(3-|Z|)n_{0}^{\prime}+2kn_{0}-3k-n_{Z}(\pi)-1+\Big{(}q-1-\frac{|Z|}{2}\Big{)}\max\\{a,b\\}+qk|Z|+1$
$\displaystyle~{}~{}(\mbox{since
$\lambda_{2}\leq\sqrt{ab}-\frac{3k+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-1}{2}\rceil\lceil\frac{b-1}{2}\rceil}}$,
$k\geq 1$, $n_{0}\geq 0$, $q\geq 2$ and $n_{Z}(\pi)\geq 0$})$
$\displaystyle>k(3\\!-\\!|Z|)n_{0}^{\prime}+2kn_{0}\\!-\\!3k\\!-\\!n_{Z}(\pi)-1~{}~{}(\mbox{since
$q\geq 2$, $\max\\{a,b\\}\geq 6k$, $k\geq 1$ and $0\leq|Z|\leq 2$}),$

contradicting (7). Thus the result follows. ∎

###### The proof of Theorem 2.7.

By a combination of the results in [17, 35], a graph $G$ with more than $3$
vertices is globally rigid in $\mathbb{R}^{2}$ if and only if $G$ is
3-connected and redundantly rigid. Direct calculation yields that

$\displaystyle\lambda_{2}\leq\sqrt{ab}-\frac{3+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-2}{2}\rceil\lceil\frac{b-2}{2}\rceil}}<\sqrt{ab}-\frac{\max\\{a,b\\}}{\sqrt{ab-2\max\\{a,b\\}}},$

due to $a\geq 6$ and $b\geq 6$. By Theorem 2.2, $G$ is 3-connected.

It remains to show that $G$ is redundantly rigid. Suppose not, then there is
an edge $f$ of $G$ such that $G-f$ is not rigid. Furthermore, by Lemma 3.2,
there exist a subset $Z$ of $V(G)$ and a partition $\pi$ of $V(G-f-Z)$ with
$n_{0}$ trivial parts $v_{1},v_{2},\ldots,v_{n_{0}}$ and $n_{0}^{\prime}$
nontrivial parts $V_{1},V_{2},\ldots,V_{n_{0}^{\prime}}$ such that

$\displaystyle e_{G-f-Z}(\pi)\leq(3-|Z|)n_{0}^{\prime}+2n_{0}-4-n_{Z}(\pi).$
(9)

Note that $e_{G-f-Z}(\pi)\geq e_{G-Z}(\pi)-1$. Then

$\displaystyle e_{G-Z}(\pi)\leq(3-|Z|)n_{0}^{\prime}+2n_{0}-3-n_{Z}(\pi).$
(10)

Let $V(G-Z)=V^{*}$. Observe that $d_{G-Z}(v_{i})\geq\min\\{a,b\\}-|Z_{i}|\geq
6-|Z_{i}|$ for $1\leq i\leq n_{0}$. Thus

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle=\frac{1}{2}\left(\sum_{1\leq i\leq
n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G-Z}(v_{j})\right)\geq 3n_{0}-\frac{1}{2}n_{Z}(\pi).$ (11)

We get the following two claims.

Claim 1.

$|Z|\leq 2$.

Otherwise, $|Z|\geq 3$. Combining this with (10) and (11), we have
$n_{0}+3+\frac{1}{2}n_{Z}(\pi)\leq 0$. This is impossible because $n_{0}\geq
0$ and $n_{Z}(\pi)\geq 0$.

Claim 2.

$n_{0}^{\prime}\geq 2$.

Otherwise, $n_{0}^{\prime}\leq 1$. By Claim 1, (10) and (11), we have
$n_{0}+|Z|+\frac{1}{2}n_{Z}(\pi)\leq 0$. This implies that $n_{0}=0$,
$n^{\prime}_{0}=1$, $n_{Z}(\pi)=0$ and $|Z|=0$. From (9), we obtain that
$e_{G-f-Z}(\pi)\leq-1$, which is impossible.

Assume that $e(V_{1},V^{*}-V_{1})\leq e(V_{2},V^{*}-V_{2})\leq\cdots\leq
e(V_{n^{\prime}_{0}},V^{*}-V_{n^{\prime}_{0}})$. Let $q$ be the largest index
such that $e(V_{q},V^{*}-V_{q})\leq 6-2|Z|$. We first assert that $q\geq 2$.
If not, $e(V_{2},V^{*}-V_{2})\geq 7-2|Z|$. Then

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle=\frac{1}{2}\left(\sum_{1\leq i\leq
n_{0}^{\prime}}e(V_{i},V^{*}-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G-Z}(v_{j})\right)$
$\displaystyle\geq\frac{1}{2}\left((7-2|Z|)(n^{\prime}_{0}-1)+6n_{0}-n_{Z}(\pi)\right)$
$\displaystyle\geq(3-|Z|)n_{0}^{\prime}+2n_{0}-3-n_{Z}(\pi)+n_{0}+\frac{1}{2}(n^{\prime}_{0}-1)+|Z|+\frac{1}{2}n_{Z}(\pi)$
$\displaystyle>(3-|Z|)n_{0}^{\prime}+2n_{0}-3-n_{Z}(\pi)~{}~{}(\mbox{since
$|Z|\geq 0$, $n_{Z}(\pi)\geq 0$, $n^{\prime}_{0}\geq 2$ and $n_{0}\geq 0$}),$

contradicting (10). It follows that $q\geq 2$. We next assert that $V_{i}\cap
X\neq\emptyset$ for $1\leq i\leq q$. If not, there exists some $j$ ($1\leq
j\leq q$) such that $V_{j}\subseteq Y$. Combining this with Claim 1,
$|V_{j}|\geq 2$ and $b\geq 6$, we have

$e(V_{j},V^{*}-V_{j})\geq e(V_{j},V-V_{j})-|Z||V_{j}|=(b-|Z|)|V_{j}|\geq
2(b-|Z|)>6-2|Z|,$

a contradiction. Similarly $V_{i}\cap Y\neq\emptyset$ for $1\leq i\leq q$. Let
$V_{i}\cap X=S_{i}$, $V_{i}\cap Y=T_{i}$, $X-S_{i}=S_{i}^{\prime}$ and
$Y-T_{i}=T^{\prime}_{i}$ where $1\leq i\leq q$. We assert that $2|S_{i}|\geq
b-|Z|$ for $1\leq i\leq q$. If not, there exists some $j$ ($1\leq j\leq q$)
such that $2|S_{j}|\leq b-|Z|-1$. Since
$d_{V_{j}}(v)\leq\max\\{|S_{j}|,|T_{j}|\\}$ for each $v\in Z$, it follows that

$\displaystyle e(V_{j},V^{*}-V_{j})$ $\displaystyle\geq
a|S_{j}|+b|T_{j}|-2e(S_{j},T_{j})-|Z|\max\\{|S_{j}|,|T_{j}|\\}$
$\displaystyle\geq
a|S_{j}|+b|T_{j}|-2|S_{j}||T_{j}|-|Z|\max\\{|S_{j}|,|T_{j}|\\}$
$\displaystyle\geq
a|S_{j}|+(|Z|+1)|T_{j}|-|Z|\max\\{|S_{j}|,|T_{j}|\\}~{}~{}~{}(\mbox{since
$2|S_{j}|\leq b-|Z|-1$})$ $\displaystyle\geq a+1~{}~{}(\mbox{since
$0\leq|Z|\leq 2$, $|T_{j}|\geq 1$ and $|S_{j}|\geq 1$})$ $\displaystyle\geq
7-2|Z|~{}~{}(\mbox{since $a\geq 6$ and $0\leq|Z|\leq 2$}),$

a contradiction. Similarly, we have $2|S^{\prime}_{i}|\geq b-|Z|$,
$2|T_{i}|\geq a-|Z|$ and $2|T^{\prime}_{i}|\geq a-|Z|$ for $1\leq i\leq q$.
Let $|X|=x$, $|Y|=y$, $|S_{i}|=s_{i}$ and $|T_{i}|=t_{i}$ where $1\leq i\leq
q$. By using the same argument as (6), we have

$e(V_{i},V-V_{i})\geq\frac{2(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{s_{i}(x-s_{i})t_{i}(y-t_{i})},$

where $1\leq i\leq q$. Note that $s_{i}(x-s_{i})$ is minimized at
$s_{i}=\lceil\frac{b-|Z|}{2}\rceil$, and $t_{i}(y-t_{i})$ is minimized at
$t_{i}=\lceil\frac{a-|Z|}{2}\rceil$. Then for $1\leq i\leq q$,

$e(V_{i},V-V_{i})\geq\frac{2(\sqrt{ab}-\lambda_{2})}{\sqrt{xy}}\cdot\sqrt{\Big{\lceil}\frac{b-|Z|}{2}\Big{\rceil}\Big{(}x\\!-\\!\Big{\lceil}\frac{b-|Z|}{2}\Big{\rceil}\Big{)}\Big{\lceil}\frac{a-|Z|}{2}\Big{\rceil}\Big{(}y\\!-\\!\Big{\lceil}\frac{a-|Z|}{2}\Big{\rceil}\Big{)}}.$

Notice that $x\geq\sum_{1\leq i\leq q}|S_{i}|\geq
q\lceil\frac{b-|Z|}{2}\rceil$ and $y\geq\sum_{1\leq i\leq q}|T_{i}|\geq
q\lceil\frac{a-|Z|}{2}\rceil$. Thus
$1-\frac{\lceil\frac{b-|Z|}{2}\rceil}{x}\geq\frac{q-1}{q}$ and
$1-\frac{\lceil\frac{a-|Z|}{2}\rceil}{y}\geq\frac{q-1}{q}$. Combining this
with $d_{G}(v)\leq\max\\{a,b\\}$ for each $v\in Z$, $e(V_{i},V-V_{i})\geq
7-2|Z|$ for $q+1\leq i\leq n^{\prime}_{0}$ and $d_{G}(v_{i})\geq 6$ for $1\leq
i\leq n_{0}$, we have

$\displaystyle e_{G-Z}(\pi)$ $\displaystyle\geq\frac{1}{2}\left(\sum_{1\leq
i\leq n_{0}^{\prime}}e(V_{i},V-V_{i})+\sum_{1\leq j\leq
n_{0}}d_{G}(v_{j})-|Z|\max\\{a,b\\}\right)$ $\displaystyle\geq
q(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{b-|Z|}{2}\Big{\rceil}\Big{(}1\\!-\\!\frac{\lceil\frac{b-|Z|}{2}\rceil}{x}\Big{)}\Big{\lceil}\frac{a-|Z|}{2}\Big{\rceil}\Big{(}1\\!-\\!\frac{\lceil\frac{a-|Z|}{2}\rceil}{y}\Big{)}}\\!+\\!(n^{\prime}_{0}\\!-\\!q)\Big{(}\frac{7}{2}\\!-\\!|Z|\Big{)}+3n_{0}$
$\displaystyle~{}~{}~{}-\frac{|Z|\max\\{a,b\\}}{2}$
$\displaystyle\geq(q-1)(\sqrt{ab}-\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{a-|Z|}{2}\Big{\rceil}\Big{\lceil}\frac{b-|Z|}{2}\Big{\rceil}}+(n^{\prime}_{0}\\!-\\!q)\Big{(}\frac{7}{2}\\!-\\!|Z|\Big{)}+3n_{0}-\frac{|Z|\max\\{a,b\\}}{2}$
$\displaystyle=(3\\!-\\!|Z|)n_{0}^{\prime}\\!+\\!2n_{0}\\!-\\!3\\!-\\!n_{Z}(\pi)\\!+\\!(q\\!-\\!1)(\sqrt{ab}\\!-\\!\lambda_{2})\cdot\sqrt{\Big{\lceil}\frac{a\\!-\\!|Z|}{2}\Big{\rceil}\Big{\lceil}\frac{b\\!-\\!|Z|}{2}\Big{\rceil}}\\!+\\!n_{0}+n_{Z}(\pi)+q|Z|$
$\displaystyle~{}~{}-\frac{|Z|\max\\{a,b\\}}{2}-3(q-1)+\frac{n_{0}^{\prime}-q}{2}$
$\displaystyle\geq(3-|Z|)n_{0}^{\prime}+2n_{0}-3-n_{Z}(\pi)+\Big{(}q-1-\frac{|Z|}{2}\Big{)}\max\\{a,b\\}+q|Z|+n_{0}+\frac{n_{0}^{\prime}-q}{2}$
$\displaystyle~{}~{}(\mbox{since
$\lambda_{2}\leq\sqrt{ab}-\frac{3+\max\\{a,b\\}}{\sqrt{\lceil\frac{a-2}{2}\rceil\lceil\frac{b-2}{2}\rceil}}$,
$n_{0}\geq 0$, $q\geq 2$ and $n_{Z}(\pi)\geq 0$})$
$\displaystyle>(3\\!-\\!|Z|)n_{0}^{\prime}\\!+\\!2n_{0}\\!-\\!3\\!-\\!n_{Z}(\pi)~{}~{}(\mbox{since
$q\geq 2$, $\max\\{a,b\\}\geq 6$, $n_{0}\geq 0$, $n_{0}^{\prime}\geq q$ and
$0\leq|Z|\leq 2$}),$

contradicting (10). Thus the result follows. ∎

##  4 Final remarks

By the bipartite expander mixing lemma, biregular bipartite graphs are kinds
of pseudorandom graphs and expanders. In this paper, we proved several
spectral expansion properties of biregular bipartite graphs via the second
largest adjacency eigenvalue. There are two related problems that we would
like to mention.

Defined by Chvátal [9] in 1973, the toughness $t(G)$ of a connected non-
complete graph $G$ is defined as
$t(G)=\min\left\\{\frac{|S|}{\omega(G-S)}\right\\}$, in which the minimum is
taken over all proper subsets $S$ of $V(G)$ such that $G-S$ is disconnected
and $\omega(G-S)$ denotes the number of components of $G-S$. Toughness of
regular graphs from eigenvalues was first studied by Alon [2] who proved that
for any connected $d$-regular graph $G$,
$t(G)>\frac{1}{3}\left(\frac{d^{2}}{d\lambda+\lambda^{2}}-1\right)$. Brouwer
[5] independently showed that $t(G)>\frac{d}{\lambda}-2$ for any connected
$d$-regular graph $G$, and he also conjectured that
$t(G)\geq\frac{d}{\lambda}-1$ in [5, 6]. The conjecture has been settled in
[28] and was extended to general graphs in [29]. For bipartite graphs,
obviously the toughness is at most $1$, and some spectral conditions were
obtained in [16, 13]. For $(a,b)$-biregular bipartite graphs, the upper bound
on toughness can be improved to $\min\\{a/b,b/a\\}$. It would be interesting
to investigate toughness of biregular bipartite graphs via eigenvalues.

Let $c$ be a positive integer. A $c$-forest is a forest with exactly $c$
components. The $c$th-order edge toughness of a graph $G$ is defined as
$\tau_{c}(G)=\min\left\\{\frac{|F|}{\omega(G-F)-c}\right\\}$, where
$\omega(G-F)$ denotes the number of components of $G-F$ and the minimum is
taken over all subsets $F$ of $E(G)$ such that $\omega(G-F)>c$. Generalizing
the spanning tree packing theorem, Chen, Koh and Peng [8] proved that for
positive integers $k$ and $c=1,2,\cdots,|V(G)|-1$, a graph $G$ has $k$ edge-
disjoint spanning $c$-forests if and only if $\tau_{c}(G)\geq k$. For $c=1$,
this is a reformulation of Theorem 3.1. Cioabă and Wong [15] proposed an open
problem to find connections between eigenvalues and $\tau_{c}(G)$ for $c\geq
2$. It is interesting to study this question for biregular bipartite graphs.

### Acknowledgements

Dandan Fan was supported by the National Natural Science Foundation of China
(No. 12301454) and the Natural Science Foundation of Xinjiang Uygur Autonomous
Region (No. 2022D01B103), Xiaofeng Gu was supported by a grant from the Simons
Foundation (No. 522728), and Huiqiu Lin was supported by the National Natural
Science Foundation of China (Nos. 12271162 and 12326372), Natural Science
Foundation of Shanghai (Nos. 22ZR1416300 and 23JC1401500) and the Program for
Professor of Special Appointment (Eastern Scholar) at Shanghai Institutions of
Higher Learning (No. TP2022031).

## References

  * [1] N. Alon, Eigenvalues and Expanders, _Combinatorica_ 6 (1986) 83–96.
  * [2] N. Alon, Tough Ramsey graphs without short cycles, _J. Algebraic Combin._ 4 (1995) 189–195.
  * [3] N. Alon and F.R.K. Chung, Explicit construction of linear sized tolerant networks, _Discrete Math._ 72 (1988) 15–19.
  * [4] G. Brito, I. Dumitriu and K.D. Harris, Spectral gap in random bipartite biregular graphs and applications, _Combin. Probab. Comput._ 31(2) (2022) 229–267.
  * [5] A.E. Brouwer, Toughness and spectrum of a graph, _Linear Algebra Appl._ 226/228 (1995) 267–271.
  * [6] A.E. Brouwer, Spectrum and connectivity of graphs, _CWI Quarterly_ 9 (1996) 37–40.
  * [7] S.P. Burnwal and M. Vidyasagar, Deterministic completion of rectangular matrices using asymmetric Ramanujan graphs: Exact and stable recovery, _IEEE Transactions on Signal Processing_ 68 (2020) 3834–3848.
  * [8] C.C. Chen, K.M. Koh and Y.H. Peng, On the higher-order edge toughness of a graph, _Discrete Math._ 111 (1993) 113–123.
  * [9] V. Chvátal, Tough graphs and hamiltonian circuits, _Discrete Math._ 5 (1973) 215–228.
  * [10] S.M. Cioabă, Eigenvalues and edge-connectivity of regular graphs, _Linear Algebra Appl._ 432 (2010) 458–470.
  * [11] S.M. Cioabă, S. Dewar, G. Grasegger and X. Gu, Graph rigidity properties of Ramanujan graphs, _Electron. J. Combin._ 30(3) (2023) P3.12.
  * [12] S.M. Cioabă, S. Dewar and X. Gu, Spectral conditions for graph rigidity in the Euclidean plane, Discrete Math. 344 (2021), 112527.
  * [13] S.M. Cioabă and X. Gu, Connectivity, toughness, spanning trees of bounded degrees, and spectrum of regular graphs, _Czechoslovak Math. J._ 66 (2016) 913–924.
  * [14] S.M. Cioabă, A. Ostuni, D. Park, S. Potluri, T. Wakhare and W. Wong, Extremal graphs for a spectral inequality on edge-disjoint spanning trees, _Electron. J. Combin._ 29 (2022) P2.56.
  * [15] S.M. Cioabă and W. Wong, Edge-disjoint spanning trees and eigenvalues of regular graphs, _Linear Algebra Appl._ 437 (2012) 630–647.
  * [16] S.M. Cioabă and W. Wong, The spectrum and toughness of regular graphs, _Discrete Appl. Math._ 176 (2014) 43–52.
  * [17] R. Connelly, Generic global rigidity, _Discrete Comput. Geom._ 33 (4) (2005) 549–563.
  * [18] S. De Winter, J. Schillewaert and J. Verstraete, Large incidence-free sets in geometries, _Electron. J. Combin._ 19(4) (2012) #P24.
  * [19] I. Dumitriu and T. Johnson, The Marčenko-Pastur law for sparse random bipartite biregular graphs, _Random Structures Algorithms_ 48(2) (2016) 313–340.
  * [20] S. Evra, B. Feigon, K. Maurischat and O. Parzanchevski, Ramanujan Bigraphs, arXiv preprint arXiv:2312.06507 (2023).
  * [21] D. Fan, X. Gu and H. Lin, Spectral radius and edge‐disjoint spanning trees, J. Graph Theory 104 (2023) 697–711.
  * [22] K. Feng and W.-C. W. Li, Spectra of hypergraphs and applications, _J. Number Theory_ 60(1) (1996) 1–22.
  * [23] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298–305.
  * [24] C.D. Godsil and B. Mohar, Walk generating functions and spectral measures of infinite graphs, _Linear Algebra Appl._ 107 (1988) 191–206.
  * [25] S.J. Gortler, A. Healy, D. Thurston, Characterizing generic global rigidity, _Amer. J. Math._ 132(4) (2010) 897–939.
  * [26] X. Gu, Spanning rigid subgraph packing and sparse subgraph covering, _SIAM J. Discrete Math._ 32(2) (2018) 1305–1313.
  * [27] X. Gu, Toughness in pseudo-random graphs, _European J. Combin._ 92 (2021) 103255.
  * [28] X. Gu, A proof of Brouwer’s toughness conjecture, _SIAM J. Discrete Math._ 35 (2021) 948–952.
  * [29] X. Gu and W.H. Haemers, Graph toughness from Laplacian eigenvalues, _Algebraic Combinatorics_ 5(1) (2022) 53–61.
  * [30] X. Gu, H.-J. Lai, P. Li and S. Yao, Edge-disjoint spanning trees, edge connectivity and eigenvalues in graphs, _J. Graph Theory_ 81 (2016) 16–29.
  * [31] X. Gu, W. Meng, M. Rolek, Y. Wang and G. Yu, Sufficient conditions for 2-dimensional global rigidity, _SIAM J. Discrete Math._ 35(4) (2021) 2520–2534.
  * [32] W.H. Haemers, Eigenvalue techniques in design and graph theory, PhD thesis, 1979.
  * [33] W.H. Haemers, Interlacing eigenvalues and graphs, _Linear Algebra Appl._ 226-228 (1995) 593–616.
  * [34] S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, _Bulletin of the American Mathematical Society_ 43 (2006) 439–562.
  * [35] B. Jackson and T. Jordán, Connected rigidity matroids and unique realizations of graphs, J. Combin. Theory Ser. B 94 (2005) 1–29.
  * [36] B. Jackson and T. Jordán, A sufficient connectivity condition for generic rigidity in the plane, Discrete Appl. Math. 157 (2009) 1965–1968.
  * [37] M. Krivelevich and B. Sudakov, Pseudo-random graphs, More sets, graphs and numbers, _Bolyai Soc. Math. Stud._ 15, Springer, Berlin, 2006, 199–262.
  * [38] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970) 331–340.
  * [39] W.-C.W. Li and Patrick Solé, Spectra of regular graphs and hypergraphs and orthogonal polynomials, _European J. Combin._ 17(5) (1996) 461–477.
  * [40] Q. Liu, Y. Hong and H.-J. Lai, Edge-disjoint spanning trees and eigenvalues, _Linear Algebra Appl._ 444 (2014) 146–151.
  * [41] Q. Liu, Y. Hong, X. Gu and H.-J. Lai, Note on edge-disjoint spanning trees and eigevalues, _Linear Algebra Appl._ 458 (2014) 128–133.
  * [42] L. Lovász and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods 3 (1982) 91–98.
  * [43] A.W. Marcus, D.A. Spielman and N. Srivastava, Interlacing families I: bipartite Ramanujan graphs of all degrees, _Ann. of Math._ 182 (2015) 307–325.
  * [44] C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, _J. Lond. Math. Soc._ 36 (1961) 445–450.
  * [45] H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Z. Angew. Math. Mech. 7(1) (1927) 58–72.
  * [46] M. Sipser and D.A. Spielman, Expander codes, _IEEE transactions on Information Theory_ 42 (1996) 1710–1722.
  * [47] A. Thomason, Pseudo-random graphs, in: Proceedings of Random Graphs, Poznań 1985, M. Karoński, ed., _Ann. Discrete Math._ 33 (1987) 307–331.
  * [48] A. Thomason, Random graphs, strongly regular graphs and pseudo-random graphs, Surveys in Combinatorics, C. Whitehead, ed., LMS Lecture Note Series 123 (1987) 173–195.
  * [49] L.V. Tran, Local Law for Eigenvalues of Random Regular Bipartite Graphs, _Bull. Malays. Math. Sci. Soc._ 43(2) (2020) 1517–1526.
  * [50] W.T. Tutte, On the problem of decomposing a graph into $n$ factors, _J. Lond. Math. Soc._ 36 (1961) 221–230.
  * [51] Y. Zhu, On the second eigenvalue of random bipartite biregular graphs, _J. Theoret. Probab._ 36 (2023) 1269–1303.


compact natural language. His work on 2D layouts, named READ, won the best
paper award at this CVPR 2020 workshop. Earlier, he earned a M.Tech degree in
Electrical Engineering from the Indian Institute of Technology Gandhinagar. He
co-organized the Learning to Generate 3D Shapes and Scenes workshop at ECCV
2022.

Supriya Gadi Patil earned her M.Sc. degree from Simon Fraser University,
Canada. She was a part of the GrUVi lab, where she worked on incorporating
deep learning techniques for geometric modeling of 3D shapes and scenes,
mainly in the realm of reconstruction. Her expertise includes domain knowledge
of various 3D indoor scene datasets and scene reconstruction methods, which
nicely complements the content delivery of this survey report. In the past,
she earned a M.Tech degree in Computer Science from the Indian Institute of
Technology Hyderabad working in the area of Graph Neural Networks, and was a
student researcher at the Max Plank Institute for Software Systems (MPI-SWS),
Germany. In the industry, she worked on integrating machine learning models
into commercial products as a full-time employee at Adobe India.

Manyi Li is an Associate Researcher in the School of Software at Shandong
University. She received B.Sc. and Ph.D. degrees from Shandong University in
2013 and 2018 respectively and was a Post-Doctoral research scholar in the
GrUVi Lab at Simon Fraser University, from 2019–2021. Her main interests are
in 3D content creation and understanding, with a special focus on 3D man-made
objects and indoor scenes, which is highly correlated with this report. With
her collaborators, she authored the first hierarchical deep generative model,
named GRAINS, catered towards fast and diverse synthesis of 3D indoor scenes.
She has also worked on developing unsupervised learning techniques for object
understanding and reconstruction, which are relevant to object insertion in 3D
indoor scenes. She was a co-organizer of the Learning to Generate 3D Shapes
and Scenes workshop at CVPR 2021.

Matthew Fisher Matthew Fisher is a Principal Scientist at Adobe Research. He
obtained his Ph.D. in Computer Science from Stanford University and a B.S. in
CS from the California Institute of Technology. Matt’s research focuses on
combining computer graphics, vision, and machine learning to make it faster
and more fun to complete creative tasks. He has published over 50 papers in
graphics and vision, including many foundational papers in scene understanding
and scene synthesis such as 3D Graph Kernel, SceneSynth, FunctionalSceneSynth
and his Ph.D. thesis was on data-driven tools for scene modeling. His recent
work looks into applying deep generative models to help artists more quickly
design and model 3D objects and scenes. At Adobe Research, he works
extensively with creative professionals to build and deliver new tools that
accelerate the artistic process across painting, animation, and video editing
applications.

Manolis Savva is an Assistant Professor at Simon Fraser University, and a
Canada Research Chair in Computer Graphics. He completed his PhD at the
Stanford graphics lab, advised by Pat Hanrahan. His research focuses on human-
centric 3D scene analysis, 3D scene generation, and simulation for scene
understanding. He has also worked in data visualization, grounding of natural
language to 3D content, and in creating large-scale datasets for 3D deep
learning. He has published a number of papers in related areas including
Plan2Scene, Habitat, and PiGraphs. He organized workshops on relevant topics
such as the Embodied AI workshop (CVPR 2020, CVPR 2021) and Learning to See
from 3D Data (ICCV 17). He has also taught a related course Learning 3D
Functionality Representations at SIGGRAPH Asia 2020, and co-authored and
presented a STAR on Functionality Representations and Applications for Shape
Analysis at EuroGraphics 2018.

Hao (Richard) Zhang is a professor in the School of Computing Science at Simon
Fraser University, Canada, and an Amazon Scholar. He obtained his Ph.D. from
the Dynamic Graphics Project (DGP), University of Toronto, and M.Math. and
B.Math degrees from the University of Waterloo, all in computer science.
Richard’s research is in computer graphics with special interests in geometric
modeling, analysis and synthesis of 3D contents (e.g., shapes and indoor
scenes), geometric deep learning, as well as computational design and
fabrication. He has published more than 170 papers on these topics. Most
relevant to this survey, Richard was one of the co-authors of the Eurographics
STARs on Structure-Aware Shape Processing, Learning Generative Models of 3D
Structures, and taught SIGGRAPH courses on closely related topics such as
"modeling and remodeling 3D worlds." With his collaborators, he has made
original and impactful contributions to structural analysis and synthesis of
3D shapes and environments including co-analysis, hierarchical modeling, semi-
supervised learning, topology-varying shape correspondence and modeling, and
deep generative models.

## References

  * [ADD∗19] Avetisyan A., Dahnert M., Dai A., Savva M., Chang A. X., Nießner M.:  Scan2cad: Learning cad model alignment in rgb-d scans.  In _Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition_ (2019), pp. 2614–2623.
  * [ADN19] Avetisyan A., Dai A., Nießner M.:  End-to-end cad model retrieval and 9dof alignment in 3d scans.  In _Proceedings of the IEEE/CVF International Conference on computer vision_ (2019), pp. 2551–2560.
  * [AGSK20] Aggarwal M., Gupta H., Sarkar M., Krishnamurthy B.:  Form2seq: A framework for higher-order form structure extraction.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ (2020), pp. 3830–3840.
  * [AKC∗20] Avetisyan A., Khanova T., Choy C., Dash D., Dai A., Nießner M.:  Scenecad: Predicting object alignments and layouts in rgb-d scans.  In _European Conference on Computer Vision_ (2020), Springer, pp. 596–612.
  * [AW18] Alhashim I., Wonka P.:  High quality monocular depth estimation via transfer learning.  _arXiv preprint arXiv:1812.11941_ (2018).
  * [BBC21] Bae G., Budvytis I., Cipolla R.:  Estimating and exploiting the aleatoric uncertainty in surface normal estimation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 13137–13146.
  * [BCC∗20] Batra D., Chang A. X., Chernova S., Davison A. J., Deng J., Koltun V., Levine S., Malik J., Mordatch I., Mottaghi R., et al.:  Rearrangement: A challenge for embodied ai.  _arXiv preprint arXiv:2011.01975_ (2020).
  * [CDF∗17] Chang A., Dai A., Funkhouser T., Halber M., Niessner M., Savva M., Song S., Zeng A., Zhang Y.:  Matterport3d: Learning from rgb-d data in indoor environments.  _arXiv preprint arXiv:1709.06158_ (2017).
  * [CFG∗15] Chang A. X., Funkhouser T., Guibas L., Hanrahan P., Huang Q., Li Z., Savarese S., Savva M., Song S., Su H., et al.:  Shapenet: An information-rich 3d model repository.  _arXiv preprint arXiv:1512.03012_ (2015).
  * [CHXY21] Cheng M., Hui L., Xie J., Yang J.:  Sspc-net: Semi-supervised semantic 3d point cloud segmentation network.  In _Thirty-Fifth AAAI Conference on Artificial Intelligence_ (2021), pp. 1140–1147.
  * [CRS] Crs4 visual computing dataset.  http://vic.crs4.it/download/datasets/.  Accessed: 23-June-2022.
  * [CRW∗20] Chaudhuri S., Ritchie D., Wu J., Xu K., Zhang H.:  Learning generative models of 3d structures.  In _Computer Graphics Forum_ (2020), vol. 39, Wiley Online Library, pp. 643–666.
  * [CSM14] Chang A., Savva M., Manning C. D.:  Learning spatial knowledge for text to 3d scene generation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ (2014), pp. 2028–2038.
  * [CXY∗15] Chen K., Xu K., Yu Y., Wang T.-Y., Hu S.-M.:  Magic decorator: automatic material suggestion for indoor digital scenes.  _ACM Transactions on graphics (TOG) 34_ , 6 (2015), 1–11.
  * [DBS∗21] DeVries T., Bautista M. A., Srivastava N., Taylor G. W., Susskind J. M.:  Unconstrained scene generation with locally conditioned radiance fields.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 14304–14313.
  * [DCLT18] Devlin J., Chang M.-W., Lee K., Toutanova K.:  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ (2018).
  * [DCS∗17] Dai A., Chang A. X., Savva M., Halber M., Funkhouser T., Nießner M.:  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2017), pp. 5828–5839.
  * [DFCS16] Dasgupta S., Fang K., Chen K., Savarese S.:  Delay: Robust spatial layout estimation for cluttered indoor scenes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2016), pp. 616–624.
  * [DN18] Dai A., Nießner M.:  3dmv: Joint 3d-multi-view prediction for 3d semantic scene segmentation.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ (2018), pp. 452–468.
  * [DT20] Denninger M., Triebel R.:  3d scene reconstruction from a single viewport.  In _European Conference on Computer Vision_ (2020), Springer, pp. 51–67.
  * [DZL∗22] Duan Y., Zhu C., Lan Y., Yi R., Liu X., Xu K.:  Disarm: Displacement aware relation module for 3d detection.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2022), IEEE, pp. 16959–16968.
  * [ETH] Eth zurich 3d dataset.  https://www.eth3d.net/datasets.  Accessed: 22-June-2022.
  * [FCG∗21] Fu H., Cai B., Gao L., Zhang L.-X., Wang J., Li C., Zeng Q., Sun C., Jia R., Zhao B., et al.:  3D-FRONT: 3d furnished rooms with layouts and semantics.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 10933–10942.
  * [FGW∗21] Feng M., Gilani S. Z., Wang Y., Zhang L., Mian A.:  Relation graph network for 3d object detection in point clouds.  _IEEE Trans. Image Process. 30_ (2021), 92–107.
  * [FJG∗21] Fu H., Jia R., Gao L., Gong M., Zhao B., Maybank S., Tao D.:  3d-future: 3d furniture shape with texture.  _International Journal of Computer Vision 129_ , 12 (2021), 3313–3337.
  * [FRS∗12] Fisher M., Ritchie D., Savva M., Funkhouser T., Hanrahan P.:  Example-based synthesis of 3d object arrangements.  _ACM Transactions on Graphics (TOG) 31_ , 6 (2012), 1–11.
  * [FSH11] Fisher M., Savva M., Hanrahan P.:  Characterizing structural relationships in scenes using graph kernels.  In _ACM SIGGRAPH 2011 papers_. 2011, pp. 1–12.
  * [FSL∗15] Fisher M., Savva M., Li Y., Hanrahan P., Nießner M.:  Activity-centric scene synthesis for functional 3d scene modeling.  _ACM Transactions on Graphics (TOG) 34_ , 6 (2015), 1–13.
  * [GCS∗20] Genova K., Cole F., Sud A., Sarna A., Funkhouser T.:  Local deep implicit functions for 3d shape.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2020), pp. 4857–4866.
  * [GDN22] Gümeli C., Dai A., Nießner M.:  Roca: Robust cad model retrieval and alignment from a single image.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2022), pp. 4022–4031.
  * [GFK∗18] Groueix T., Fisher M., Kim V. G., Russell B. C., Aubry M.:  A papier-mâché approach to learning 3d surface generation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2018), pp. 216–224.
  * [GLSU13] Geiger A., Lenz P., Stiller C., Urtasun R.:  Vision meets robotics: The kitti dataset.  _The International Journal of Robotics Research 32_ , 11 (2013), 1231–1237.
  * [GMJ19] Gkioxari G., Malik J., Johnson J.:  Mesh r-cnn.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2019), pp. 9785–9795.
  * [GRJ22] Gkioxari G., Ravi N., Johnson J.:  Learning 3d object shape and layout without 3d supervision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ (June 2022), pp. 1695–1704.
  * [GSW∗22] Gao J., Shen T., Wang Z., Chen W., Yin K., Li D., Litany O., Gojcic Z., Fidler S.:  Get3d: A generative model of high quality 3d textured shapes learned from images.  In _Advances In Neural Information Processing Systems_ (2022).
  * [GWB∗22] Grauman K., Westbury A., Byrne E., Chavis Z., Furnari A., Girdhar R., Hamburger J., Jiang H., Liu M., Liu X., et al.:  Ego4d: Around the world in 3,000 hours of egocentric video.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2022), pp. 18995–19012.
  * [HDN19] Hou J., Dai A., Nießner M.:  3d-sis: 3d semantic instance segmentation of rgb-d scans.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ (2019), pp. 4421–4430.
  * [HHF] Hedau V., Hoiem D., Forsyth D.:  Recovering the spatial layout of cluttered rooms.  In _2009 IEEE 12th international conference on computer vision_ , IEEE, pp. 1849–1856.
  * [HHT∗20] Hu R., Huang Z., Tang Y., Van Kaick O., Zhang H., Huang H.:  Graph2plan: Learning floorplan generation from layout graphs.  _ACM Transactions on Graphics (TOG) 39_ , 4 (2020), 118–1.
  * [HJA20] Ho J., Jain A., Abbeel P.:  Denoising diffusion probabilistic models.  _Advances in Neural Information Processing Systems 33_ (2020), 6840–6851.
  * [HLVK∗17] Hu R., Li W., Van Kaick O., Shamir A., Zhang H., Huang H.:  Learning to predict part mobility from a single static snapshot.  _ACM Transactions on Graphics (TOG) 36_ , 6 (2017), 1–13.
  * [HPB∗16] Handa A., Patraucean V., Badrinarayanan V., Stent S., Cipolla R.:  Understanding real world indoor scenes with synthetic data.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2016), pp. 4077–4085.
  * [HPN∗16] Hua B.-S., Pham Q.-H., Nguyen D. T., Tran M.-K., Yu L.-F., Yeung S.-K.:  Scenenn: A scene meshes dataset with annotations.  In _2016 fourth international conference on 3D vision (3DV)_ (2016), Ieee, pp. 92–101.  http://hkust-vgd.ust.hk/scenenn/home/, Accessed: 24-June-2022.
  * [HQX∗18] Huang S., Qi S., Xiao Y., Zhu Y., Wu Y. N., Zhu S.-C.:  Cooperative holistic scene understanding: Unifying 3d object, layout, and camera pose estimation.  In _NeurIPS_ (2018).
  * [HQZ∗18] Huang S., Qi S., Zhu Y., Xiao Y., Xu Y., Zhu S.-C.:  Holistic 3d scene parsing and reconstruction from a single rgb image.  In _Proceedings of the European conference on computer vision (ECCV)_ (2018), pp. 187–203.
  * [HvKW∗16] Hu R., van Kaick O., Wu B., Huang H., Shamir A., Zhang H.:  Learning how objects function via co-analysis of interactions.  _ACM Transactions on Graphics (TOG) 35_ , 4 (2016), 1–13.
  * [HYZ∗20] Hu R., Yan Z., Zhang J., Van Kaick O., Shamir A., Zhang H., Huang H.:  Predictive and generative neural networks for object functionality.  _arXiv preprint arXiv:2006.15520_ (2020).
  * [HZvK∗15] Hu R., Zhu C., van Kaick O., Liu L., Shamir A., Zhang H.:  Interaction context (icon) towards a geometric functionality descriptor.  _ACM Transactions on Graphics (TOG) 34_ , 4 (2015), 1–12.
  * [ISS17] Izadinia H., Shan Q., Seitz S. M.:  Im2cad.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ (2017), pp. 5134–5143.
  * [JLS12] Jiang Y., Lim M., Saxena A.:  Learning object arrangements in 3d scenes using human context.  _arXiv preprint arXiv:1206.6462_ (2012).
  * [JTRS12] Jain A., Thormählen T., Ritschel T., Seidel H.-P.:  Material memex: Automatic material suggestions for 3d objects.  _ACM Transactions on Graphics (TOG) 31_ , 6 (2012), 1–8.
  * [JW19] Johanna Wald Armen Avetisyan N. N. F. T. M. N.:  Rio: 3d object instance re-localization in changing indoor environments.
  * [KALD20] Kuo W., Angelova A., Lin T.-Y., Dai A.:  Mask2cad: 3d shape prediction by learning to segment and retrieve.  In _European Conference on Computer Vision_ (2020), Springer, pp. 260–277.
  * [KALD21] Kuo W., Angelova A., Lin T.-Y., Dai A.:  Patch2cad: Patchwise embedding learning for in-the-wild shape retrieval from a single image.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 12589–12599.
  * [KYH∗19] Kalervo A., Ylioinas J., Häikiö M., Karhu A., Kannala J.:  Cubicasa5k: A dataset and an improved multi-task model for floorplan image analysis.  In _Scandinavian Conference on Image Analysis_ (2019), Springer, pp. 28–40.
  * [LAK∗18] Lin H., Averkiou M., Kalogerakis E., Kovacs B., Ranade S., Kim V., Chaudhuri S., Bala K.:  Learning material-aware local descriptors for 3d shapes.  In _2018 International Conference on 3D Vision (3DV)_ (2018), IEEE, pp. 150–159.
  * [LBMR17] Lee C.-Y., Badrinarayanan V., Malisiewicz T., Rabinovich A.:  Roomnet: End-to-end room layout estimation.  In _Proceedings of the IEEE international conference on computer vision_ (2017), pp. 4865–4874.
  * [LBS∗18] Li Y., Bu R., Sun M., Wu W., Di X., Chen B.:  Pointcnn: Convolution on x-transformed points.  In _Advances in Neural Information Processing Systems_ (2018), pp. 828–838.
  * [LCK∗14] Liu T., Chaudhuri S., Kim V. G., Huang Q., Mitra N. J., Funkhouser T.:  Creating consistent scene graphs using a probabilistic grammar.  _ACM Transactions on Graphics (TOG) 33_ , 6 (2014), 1–12.
  * [LFU13] Lin D., Fidler S., Urtasun R.:  Holistic scene understanding for 3d object detection with RGBD cameras.  In _IEEE International Conference on Computer Vision_ (2013), pp. 1417–1424.
  * [LGD∗19] Li Y., Gu C., Dullien T., Vinyals O., Kohli P.:  Graph matching networks for learning the similarity of graph structured objects.  In _International conference on machine learning_ (2019), PMLR, pp. 3835–3845.
  * [LHAZ] Li H., Hu R., Alhashim I., Zhang H.:  Foldabilizing furniture.
  * [LHLY21] Li C., Huang H., Lien J.-M., Yu L.-F.:  Synthesizing scene-aware virtual reality teleport graphs.  _ACM Transactions on Graphics (TOG) 40_ , 6 (2021), 1–15.
  * [LMTG19] Li G., Muller M., Thabet A., Ghanem B.:  Deepgcns: Can gcns go as deep as cnns?  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2019), pp. 9267–9276.
  * [LPX∗19] Li M., Patil A. G., Xu K., Chaudhuri S., Khan O., Shamir A., Tu C., Chen B., Cohen-Or D., Zhang H.:  Grains: Generative recursive autoencoders for indoor scenes.  _ACM Transactions on Graphics (TOG) 38_ , 2 (2019), 1–16.
  * [LSD15] Long J., Shelhamer E., Darrell T.:  Fully convolutional networks for semantic segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2015), pp. 3431–3440.
  * [LSM∗18] Li W., Saeedi S., McCormac J., Clark R., Tzoumanikas D., Ye Q., Huang Y., Tang R., Leutenegger S.:  Interiornet: Mega-scale multi-sensor photo-realistic indoor scenes dataset.  _arXiv preprint arXiv:1809.00716_ (2018).
  * [LTJ∗21] Liu A., Tucker R., Jampani V., Makadia A., Snavely N., Kanazawa A.:  Infinite nature: Perpetual view generation of natural scenes from a single image.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 14458–14467.
  * [LTJ22] Lei J., Tang J., Jia K.:  Generative scene synthesis via incremental view inpainting using rgbd diffusion models.  _arXiv preprint arXiv:2212.05993_ (2022).
  * [LTLH19] Liu Z., Tang H., Lin Y., Han S.:  Point-voxel cnn for efficient 3d deep learning.  _Advances in Neural Information Processing Systems 32_ (2019).
  * [LVC∗19] Lang A. H., Vora S., Caesar H., Zhou L., Yang J., Beijbom O.:  Pointpillars: Fast encoders for object detection from point clouds.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ (2019), pp. 12697–12705.
  * [LXJ∗23] Liu J., Xiong W., Jones I., Nie Y., Gupta A., Oğuz B.:  Clip-layout: Style-consistent indoor scene synthesis with semantic furniture embedding.  _arXiv preprint arXiv:2303.03565_ (2023).
  * [LYJ∗20] Lee H.-Y., Yang W., Jiang L., Le M., Essa I., Gong H., Yang M.-H.:  Neural design network: Graphic layout generation with constraints.  _ECCV. Springer, Heidelberg_ (2020).
  * [LYS∗21] Li Z., Yu T.-W., Sang S., Wang S., Song M., Liu Y., Yeh Y.-Y., Zhu R., Gundavarapu N., Shi J., et al.:  Openrooms: An open framework for photorealistic indoor scene datasets.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2021), pp. 7190–7199.
  * [LZC∗21] Liu Z., Zhang Z., Cao Y., Hu H., Tong X.:  Group-free 3d object detection via transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021).
  * [ML15] Mallya A., Lazebnik S.:  Learning informative edge maps for indoor scene layout prediction.  In _Proceedings of the IEEE international conference on computer vision_ (2015), pp. 936–944.
  * [MLZ∗16] Ma R., Li H., Zou C., Liao Z., Tong X., Zhang H.:  Action-driven 3d indoor scene evolution.  _ACM Trans. Graph. 35_ , 6 (2016), 173–1.
  * [MPF∗18] Ma R., Patil A. G., Fisher M., Li M., Pirk S., Hua B.-S., Yeung S.-K., Tong X., Guibas L., Zhang H.:  Language-driven synthesis of 3d scenes from scene databases.  _ACM Transactions on Graphics (TOG) 37_ , 6 (2018), 1–16.
  * [MPNF22] Maninis K.-K., Popov S., Niesser M., Ferrari V.:  Vid2cad: Cad model alignment using multi-view constraints from videos.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2022).
  * [MRC20] Manandhar D., Ruta D., Collomosse J.:  Learning structural similarity of user interface layouts using graph networks.  In _European Conference on Computer Vision_ (2020), Springer, pp. 730–746.
  * [MSL∗11] Merrell P., Schkufza E., Li Z., Agrawala M., Koltun V.:  Interactive furniture layout using interior design guidelines.  _ACM transactions on graphics (TOG) 30_ , 4 (2011), 1–10.
  * [MST∗21] Mildenhall B., Srinivasan P. P., Tancik M., Barron J. T., Ramamoorthi R., Ng R.:  Nerf: Representing scenes as neural radiance fields for view synthesis.  _Communications of the ACM 65_ , 1 (2021), 99–106.
  * [MvAB∗20] Murez Z., van As T., Bartolozzi J., Sinha A., Badrinarayanan V., Rabinovich A.:  Atlas: End-to-end 3d scene reconstruction from posed images.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part VII 16_ (2020), Springer, pp. 414–431.
  * [NHG∗20] Nie Y., Han X., Guo S., Zheng Y., Chang J., Zhang J. J.:  Total3dunderstanding: Joint layout, object pose and mesh reconstruction for indoor scenes from a single image.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2020), pp. 55–64.
  * [NSF12] Nathan Silberman Derek Hoiem P. K., Fergus R.:  Indoor segmentation and support inference from rgbd images.  In _ECCV_ (2012).
  * [PBEPAE20] Patil A. G., Ben-Eliezer O., Perel O., Averbuch-Elor H.:  READ: Recursive autoencoders for document layout generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ (2020), pp. 544–545.
  * [PCS23] Patil S. G., Chang A. X., Savva M.:  Evaluating 3d shape analysis methods for robustness to rotation invariance.
  * [PJBM22] Poole B., Jain A., Barron J. T., Mildenhall B.:  Dreamfusion: Text-to-3d using 2d diffusion.  _arXiv preprint arXiv:2209.14988_ (2022).
  * [PKS∗21] Paschalidou D., Kar A., Shugrina M., Kreis K., Geiger A., Fidler S.:  Atiss: Autoregressive transformers for indoor scene synthesis.  In _Thirty-Fifth Conference on Neural Information Processing Systems_ (2021).
  * [PLF∗21] Patil A. G., Li M., Fisher M., Savva M., Zhang H.:  LayoutGMN: Neural graph matching for structural layout similarity.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2021), pp. 11048–11057.
  * [PMG∗20] Pintore G., Mura C., Ganovelli F., Fuentes-Perez L., Pajarola R., Gobbetti E.:  State-of-the-art in automatic 3d reconstruction of structured indoor environments.  In _Computer Graphics Forum_ (2020), vol. 39, Wiley Online Library, pp. 667–699.
  * [PNI∗18] Peters M. E., Neumann M., Iyyer M., Gardner M., Clark C., Lee K., Zettlemoyer L.:  Deep contextualized word representations.  In _Proceedings of NAACL-HLT_ (2018), pp. 2227–2237.
  * [PSM14] Pennington J., Socher R., Manning C. D.:  Glove: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ (2014), pp. 1532–1543.
  * [QCLG20] Qi C. R., Chen X., Litany O., Guibas L. J.:  Imvotenet: Boosting 3d object detection in point clouds with image votes.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ (2020), pp. 4404–4413.
  * [QLHG19] Qi C. R., Litany O., He K., Guibas L. J.:  Deep hough voting for 3d object detection in point clouds.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2019), pp. 9277–9286.
  * [QSMG17] Qi C. R., Su H., Mo K., Guibas L. J.:  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2017), pp. 652–660.
  * [QYSG17] Qi C. R., Yi L., Su H., Guibas L. J.:  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  _arXiv preprint arXiv:1706.02413_ (2017).
  * [RDN∗22] Ramesh A., Dhariwal P., Nichol A., Chu C., Chen M.:  Hierarchical text-conditional image generation with clip latents.  _arXiv preprint arXiv:2204.06125_ (2022).
  * [RHGS15] Ren S., He K., Girshick R., Sun J.:  Faster r-cnn: Towards real-time object detection with region proposal networks.  _Advances in neural information processing systems 28_ (2015), 91–99.
  * [RKH∗21] Radford A., Kim J. W., Hallacy C., Ramesh A., Goh G., Agarwal S., Sastry G., Askell A., Mishkin P., Clark J., et al.:  Learning transferable visual models from natural language supervision.  In _International conference on machine learning_ (2021), PMLR, pp. 8748–8763.
  * [RRR∗21] Roberts M., Ramapuram J., Ranjan A., Kumar A., Bautista M. A., Paczan N., Webb R., Susskind J. M.:  Hypersim: A photorealistic synthetic dataset for holistic indoor scene understanding.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 10912–10922.
  * [RS16] Ren Z., Sudderth E. B.:  Three-dimensional object detection and layout prediction using clouds of oriented gradients.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ (2016), pp. 1525–1533.
  * [RSH∗21] Reizenstein J., Shapovalov R., Henzler P., Sbordone L., Labatut P., Novotny D.:  Common objects in 3d: Large-scale learning and evaluation of real-life 3d category reconstruction.  In _International Conference on Computer Vision_ (2021).
  * [SCH∗16] Savva M., Chang A. X., Hanrahan P., Fisher M., Nießner M.:  Pigraphs: learning interaction snapshots from observations.  _ACM Transactions on Graphics (TOG) 35_ , 4 (2016), 1–12.
  * [SCL∗22] Sanghi A., Chu H., Lambourne J. G., Wang Y., Cheng C.-Y., Fumero M., Malekshan K. R.:  Clip-forge: Towards zero-shot text-to-shape generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2022), pp. 18603–18613.
  * [SCS∗22] Saharia C., Chan W., Saxena S., Li L., Whang J., Denton E., Ghasemipour S. K. S., Ayan B. K., Mahdavi S. S., Lopes R. G., et al.:  Photorealistic text-to-image diffusion models with deep language understanding.  _arXiv preprint arXiv:2205.11487_ (2022).
  * [SDWMG15] Sohl-Dickstein J., Weiss E., Maheswaranathan N., Ganguli S.:  Deep unsupervised learning using nonequilibrium thermodynamics.  In _International Conference on Machine Learning_ (2015), PMLR, pp. 2256–2265.
  * [SEE∗12] Sturm J., Engelhard N., Endres F., Burgard W., Cremers D.:  A benchmark for the evaluation of rgb-d slam systems.  In _2012 IEEE/RSJ international conference on intelligent robots and systems_ (2012), IEEE, pp. 573–580.
  * [SF16] Schonberger J. L., Frahm J.-M.:  Structure-from-motion revisited.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2016), pp. 4104–4113.
  * [SFL∗22] Sanghi A., Fu R., Liu V., Willis K., Shayani H., Khasahmadi A. H., Sridhar S., Ritchie D.:  Textcraft: Zero-shot generation of high-fidelity and diverse shapes from text.  _arXiv preprint arXiv:2211.01427_ (2022).
  * [SFZ∗22] Sun J., Fang H., Zhu X., Li J., Lu C.:  Correlation field for boosting 3d object detection in structured scenes.  In _Thirty-Sixth AAAI Conference on Artificial Intelligence_ (2022), pp. 2298–2306.
  * [SHKF12] Silberman N., Hoiem D., Kohli P., Fergus R.:  Indoor segmentation and support inference from rgbd images.  In _European conference on computer vision_ (2012), Springer, pp. 746–760.
  * [SHL∗14] Sharf A., Huang H., Liang C., Zhang J., Chen B., Gong M.:  Mobility-trees for indoor scenes manipulation.  In _Computer Graphics Forum_ (2014), vol. 33, Wiley Online Library, pp. 2–14.
  * [SHS∗22] Solah M., Huang H., Sheng J., Feng T., Pomplun M., Yu L.-F.:  Mood-driven colorization of virtual indoor scenes.  _IEEE Transactions on Visualization and Computer Graphics 28_ , 5 (2022), 2058–2068.
  * [SLX15] Song S., Lichtenberg S. P., Xiao J.:  Sun rgb-d: A rgb-d scene understanding benchmark suite.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2015), pp. 567–576.
  * [SWL19] Shi S., Wang X., Li H.:  Pointrcnn: 3d object proposal generation and detection from point cloud.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ (2019), pp. 770–779.
  * [SWM∗19] Straub J., Whelan T., Ma L., Chen Y., Wijmans E., Green S., Engel J. J., Mur-Artal R., Ren C., Verma S., Clarkson A., Yan M., Budge B., Yan Y., Pan X., Yon J., Zou Y., Leon K., Carter N., Briales J., Gillingham T., Mueggler E., Pesqueira L., Savva M., Batra D., Strasdat H. M., Nardi R. D., Goesele M., Lovegrove S., Newcombe R.:  The Replica dataset: A digital replica of indoor spaces.  _arXiv preprint arXiv:1906.05797_ (2019).
  * [SX14] Song S., Xiao J.:  Sliding shapes for 3d object detection in depth images.  In _European conference on computer vision_ (2014), Springer, pp. 634–651.
  * [SX16] Song S., Xiao J.:  Deep sliding shapes for amodal 3d object detection in rgb-d images.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2016), pp. 808–816.
  * [SYZ∗17] Song S., Yu F., Zeng A., Chang A. X., Savva M., Funkhouser T.:  Semantic scene completion from a single depth image.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ (2017), pp. 1746–1754.
  * [SZAB17] Sedaghat N., Zolfaghari M., Amiri E., Brox T.:  Orientation-boosted voxel nets for 3d object recognition.  In _Proceedings of the British Machine Vision Conference_ (2017).
  * [TQD∗19] Thomas H., Qi C. R., Deschaud J.-E., Marcotegui B., Goulette F., Guibas L. J.:  Kpconv: Flexible and deformable convolution for point clouds.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2019), pp. 6411–6420.
  * [UZH] University of zurich dataset.  https://www.ifi.uzh.ch/en/vmml/research/datasets.html.  Accessed: 22-June-2022.
  * [VSP∗17] Vaswani A., Shazeer N., Parmar N., Uszkoreit J., Jones L., Gomez A. N., Kaiser Ł., Polosukhin I.:  Attention is all you need.  In _Advances in neural information processing systems_ (2017), pp. 5998–6008.
  * [WDNT20] Wald J., Dhamo H., Navab N., Tombari F.:  Learning 3d semantic scene graphs from 3d indoor reconstructions.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2020), pp. 3961–3970.
  * [WDP∗23] Wei Q. A., Ding S., Park J. J., Sajnani R., Poulenard A., Sridhar S., Guibas L.:  Lego-net: Learning regular rearrangements of objects in rooms.  _arXiv preprint arXiv:2301.09629_ (2023).
  * [WFT∗19] Wu W., Fu X.-M., Tang R., Wang Y., Qi Y.-H., Liu L.:  Data-driven interior plan generation for residential buildings.  _ACM Transactions on Graphics (TOG) 38_ , 6 (2019), 1–12.
  * [WLJ∗22] Wang Y., Li Z., Jiang Y., Zhou K., Cao T., Fu Y., Xiao C.:  Neuralroom: Geometry-constrained neural implicit surfaces for indoor scene reconstruction.  _arXiv preprint arXiv:2210.06853_ (2022).
  * [WLW∗19] Wang K., Lin Y.-A., Weissmann B., Savva M., Chang A. X., Ritchie D.:  Planit: Planning and instantiating indoor scenes with relation graph and spatial prior networks.  _ACM Transactions on Graphics (TOG) 38_ , 4 (2019), 1–15.
  * [WLY20] Wang H., Liang W., Yu L.-F.:  Scene mover: automatic move planning for scene arrangement by deep reinforcement learning.  _ACM Transactions on Graphics (TOG) 39_ , 6 (2020), 1–15.
  * [WSCR18] Wang K., Savva M., Chang A. X., Ritchie D.:  Deep convolutional priors for indoor scene synthesis.  _ACM Transactions on Graphics (TOG) 37_ , 4 (2018), 1–14.
  * [WSL∗19] Wang Y., Sun Y., Liu Z., Sarma S. E., Bronstein M. M., Solomon J. M.:  Dynamic graph cnn for learning on point clouds.  _Acm Transactions On Graphics (tog) 38_ , 5 (2019), 1–12.
  * [WYN20] Wang X., Yeshwanth C., Nießner M.:  Sceneformer: Indoor scene generation with transformers.  _arXiv preprint arXiv:2012.09793_ (2020).
  * [XLW∗20] Xie Q., Lai Y.-K., Wu J., Wang Z., Zhang Y., Xu K., Wang J.:  Mlcvnet: Multi-level context votenet for 3d object detection.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ (2020), pp. 10447–10456.
  * [XMZ∗14] Xu K., Ma R., Zhang H., Zhu C., Shamir A., Cohen-Or D., Huang H.:  Organizing heterogeneous scene collections through contextual focal points.  _ACM Transactions on Graphics (TOG) 33_ , 4 (2014), 1–12.
  * [XOT13] Xiao J., Owens A., Torralba A.:  Sun3d: A database of big spaces reconstructed using sfm and object labels.  In _Proceedings of the IEEE international conference on computer vision_ (2013), pp. 1625–1632.
  * [XTS∗22] Xie Y., Takikawa T., Saito S., Litany O., Yan S., Khan N., Tombari F., Tompkin J., Sitzmann V., Sridhar S.:  Neural fields in visual computing and beyond.  In _Computer Graphics Forum_ (2022), vol. 41, Wiley Online Library, pp. 641–676.
  * [YGZT21] Yang M.-J., Guo Y.-X., Zhou B., Tong X.:  Indoor scene generation from a collection of semantic-segmented depth images.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 15203–15212.
  * [YSZ∗15] Yu F., Seff A., Zhang Y., Song S., Funkhouser T., Xiao J.:  Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop.  _arXiv preprint arXiv:1506.03365_ (2015).
  * [YWP∗19] Yang S.-T., Wang F.-E., Peng C.-H., Wonka P., Sun M., Chu H.-K.:  Dula-net: A dual-projection network for estimating room layouts from a single rgb panorama.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2019), pp. 3363–3372.
  * [YWY22] Yu H.-X., Wu J., Yi L.:  Rotationally equivariant 3d object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2022), pp. 1456–1464.
  * [YYT∗11] Yu L. F., Yeung S. K., Tang C. K., Terzopoulos D., Chan T. F., Osher S. J.:  Make it home: automatic optimization of furniture arrangement.  _ACM Transactions on Graphics (TOG)-Proceedings of ACM SIGGRAPH 2011, v. 30,(4), July 2011, article no. 86 30_ , 4 (2011).
  * [YYT15] Yu L.-F., Yeung S.-K., Terzopoulos D.:  The clutterpalette: An interactive tool for detailing indoor scenes.  _IEEE transactions on visualization and computer graphics 22_ , 2 (2015), 1138–1148.
  * [YZD∗21] Yang C., Zheng J., Dai X., Tang R., Ma Y., Yuan X.:  Learning to reconstruct 3d non-cuboid room layout from a single rgb image.  _arXiv preprint arXiv:2104.07986_ (2021).
  * [YZK21] Yin T., Zhou X., Krahenbuhl P.:  Center-based 3d object detection and tracking.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ (2021), pp. 11784–11793.
  * [ZBK∗] Zhang Y., Bai M., Kohli P., Izadi S., Xiao J.:  Deepcontext: Context-encoding neural pathways for 3d holistic scene understanding.  In _IEEE International Conference on Computer Vision_ , pp. 1201–1210.
  * [ZCSH18] Zou C., Colburn A., Shan Q., Hoiem D.:  Layoutnet: Reconstructing the 3d room layout from a single rgb image.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ (2018), pp. 2051–2059.
  * [ZCZ∗21] Zhang C., Cui Z., Zhang Y., Zeng B., Pollefeys M., Liu S.:  Holistic 3d scene understanding from a single image with implicit representation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ (2021), pp. 8833–8842.
  * [ZFF∗21] Zhou H., Feng Y., Fang M., Wei M., Qin J., Lu T.:  Adaptive graph convolution for point cloud analysis.  In _2021 IEEE/CVF International Conference on Computer Vision_ (2021), pp. 4945–4954.
  * [ZHG∗16] Zhao X., Hu R., Guerrero P., Mitra N., Komura T.:  Relationship templates for creating scene variations.  _ACM Transactions on Graphics (TOG) 35_ , 6 (2016), 1–13.
  * [ZHPY21] Zhang Y., Huang H., Plaku E., Yu L.-F.:  Joint computational design of workspaces and workplans.  _ACM Transactions on Graphics (TOG) 40_ , 6 (2021), 1–16.
  * [ZJFJ19] Zhao H., Jiang L., Fu C., Jia J.:  Pointweb: Enhancing local neighborhood features for point cloud processing.  In _IEEE Conference on Computer Vision and Pattern Recognition_ (2019), pp. 5565–5573.
  * [ZJJ∗21] Zhao H., Jiang L., Jia J., Torr P. H., Koltun V.:  Point transformer.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ (2021), pp. 16259–16268.
  * [ZSYH20] Zhang Z., Sun B., Yang H., Huang Q.:  H3dnet: 3d object detection using hybrid geometric primitives.  In _European Conference on Computer Vision_ (2020), Springer, pp. 311–329.
  * [ZTF∗18] Zhou T., Tucker R., Flynn J., Fyffe G., Snavely N.:  Stereo magnification: Learning view synthesis using multiplane images.  _arXiv preprint arXiv:1805.09817_ (2018).
  * [ZWK14] Zhao X., Wang H., Komura T.:  Indexing 3d scenes using the interaction bisector surface.  _ACM Transactions on Graphics (TOG) 33_ , 3 (2014), 1–14.
  * [ZYM∗20] Zhang Z., Yang Z., Ma C., Luo L., Huth A., Vouga E., Huang Q.:  Deep generative modeling for scene synthesis via hybrid representations.  _ACM Transactions on Graphics (TOG) 39_ , 2 (2020), 1–21.
  * [ZZL∗20] Zheng J., Zhang J., Li J., Tang R., Gao S., Zhou Z.:  Structured3d: A large photo-realistic dataset for structured 3d modeling.  In _European Conference on Computer Vision_ (2020), Springer, pp. 519–535.