# Global Rigidity of Line Constrained Frameworks

James Cruickshank  Fatemeh Mohammadi  Harshit J. Motwani  Anthony Nixon  Shin-
ichi Tanigawa

Abstract. We consider the global rigidity problem for bar-joint frameworks
where each vertex is constrained to lie on a particular line in
$\mathbb{R}^{d}$. In our setting we allow multiple vertices to be constrained
to the same line. We give a combinatorial characterisation of generic rigidity
in this setting for arbitrary line sets. Further, under a mild assumption on
the given set of lines, we give a complete combinatorial characterisation of
graphs that are generically globally rigid. This gives a $d$-dimensional
extension of the well-known combinatorial characterisation of 2-dimensional
global rigidity. In particular, our results imply that global rigidity is a
generic property in this setting.

2020 Mathematics Subject Classification: 52C25, 05C10
Key words and phrases: bar-joint framework, global rigidity, line constrained
framework

##  1 Introduction

Consider a discrete geometric structure consisting of a collection of points
subject to a system of constraints specifying the distances between points.
Such structures are often modelled by graphs with vertices corresponding to
points and edges to fixed length line segments. A natural question is to what
extent the given structure is unique given the topology of the underlying
graph and the specified lengths. The structures are usually referred to as
bar-joint frameworks and the question is then the well studied global rigidity
problem (see, e.g., [16]).

In particular, while determining global rigidity of a given framework even on
the line is NP-hard [20], a folklore result says that, generically, global
rigidity on the line is equivalent to the graph being 2-connected. We will
extend this result to higher dimensions giving one of a very small number of
combinatorial results for generic global rigidity in arbitrary dimension (see
[4, 6, 15] for the others). The general $d$-dimensional case is known to
depend only on the underlying graph [7] and the case when $d=2$ was resolved
in [11] but, in general, giving a graph theoretic characterisation is a
central challenge in rigidity theory.

Initially, the global rigidity problem arose from attempts to understand
configurations of molecules [10]. More recently global rigidity has found a
broader range of applications, for example in localizing networks from partial
observations of inter-point distances, see, e.g. [13]. In such applications,
it is natural to assume that some points have a fixed location, or perhaps are
fixed to move on the ground, or a given wall. Such external boundary
conditions can be incorporated into the constraints for a bar-joint framework
as additional linear constraints (restriction to move on a fixed hyperplane)
on the points [5, 9, 14, 17, 23]. In this linearly constrained context, global
rigidity has been characterised generically in the plane [9] in purely
combinatorial terms. However, little is known combinatorially in dimension
greater than 2 with, or without, linear constraints.

In this paper we address the global rigidity problem of bar-joint frameworks
whose points are constrained to move on lines. Our research generalises that
of [9] in two directions. Firstly we will work in arbitrary dimensions and
consider bar-joint frameworks constrained to a fixed system of lines. Secondly
we will substantially weaken the genericity hypothesis by imposing no
restriction on how many points are constrained to any given line. This
generalization gives us a $d$-dimensional extension of the aforementioned
combinatorial characterisation of $1$-dimensional global rigidity.

The paper is organized as follows. In Section 2, we will formally introduce
our line constrained rigidity setting and give a characterisation of generic
rigidity in this context in Section 3. (Rigidity, while fundamental, is a
weaker property than global rigidity where uniqueness is only required in a
neighbourhood of the given framework.) This characterisation extends, to the
general case, a result obtained for line constrained frameworks in [5] since
there only 2 points were allowed to lie on each line. We then prove exact
necessary conditions for a generic line constrained framework to be globally
rigid in Section 4; these results are analogous to the well known Hendrickson
conditions for global rigidity of a bar-joint framework [10]. The remainder of
the paper is devoted to showing these necessary conditions are also
sufficient, and thereby giving a full combinatorial description of global
rigidity. We achieve this by an inductive proof strategy, the geometric aspect
of which is to prove that particular graph operations preserve generic global
rigidity; this is the content of Section 5. In Section 6, we then establish
global rigidity for small graphs of three fundamental topological types. These
results can then be combined with a combinatorial reduction step, in Section
7, to complete the proof of our characterisation.

##  2 Preliminaries

###  2.1 Line constrained frameworks

Any line in $\mathbb{R}^{d}$ has a unique standard equation of the form $Ax=b$
where $(A,b)$ is a $(d-1)\times(d+1)$ matrix in reduced row echelon form.
Throughout the rest of the paper, $k$ is some positive integer and
$\mathcal{L}=\\{L_{i}:1\leq i\leq k\\}$ will be a set of lines in
$\mathbb{R}^{d}$. Suppose that $A_{i}x=b_{i}$ is the standard representation
of the line $L_{i}$ as above. We say that $\mathcal{L}$ is parallel if
$A_{i}=A_{j}$ for all $1\leq i,j\leq k$ and non-parallel otherwise. Let $X$ be
the union of the sets of entries of $(A_{i},b_{i})$ for $1\leq i\leq k$ and
define $\mathbb{Q}(\mathcal{L})$ to be the smallest subfield of $\mathbb{R}$
containing $X$.

A partitioned graph is a finite graph $G=(\mathcal{V},\mathcal{E})$ together
with a partition of the vertex set $\mathcal{V}=\cup_{i=1}^{k}V_{i}$. Note
that we allow $V_{i}$ to be empty here. Also in contrast to a multipartite
graph, the induced edge set on $V_{i}$ can be non-empty. We say that a subset
$W\subset\mathcal{V}$ is crossing if $W\cap V_{i}$ is non-empty for at least
two distinct values of $i$. We say that a graph or an edge is crossing if its
set of vertices is crossing.

Given a line set $\mathcal{L}$ in $\mathbb{R}^{d}$, an
$\mathcal{L}$-constrained framework is a pair $(G,p)$ where $G$ is a
partitioned graph and $p:\mathcal{V}\rightarrow\mathbb{R}^{d}$ satisfies
$p(V_{i})\subset L_{i}$ for $1\leq i\leq k$. In this situation, if $u\in
V_{i}$ then define $L_{u}$ to be $L_{i}$. Let $Y$ be the set of real numbers
that appear as a coordinate in some $p(v)$ and define
$\mathbb{Q}(\mathcal{L},p)$ to be the smallest subfield of $\mathbb{R}$ that
contains both $\mathbb{Q}(\mathcal{L})$ and $Y$. We say that $(G,p)$ (or $p$)
is $\mathcal{L}$-generic if
$\mathrm{td}(\mathbb{Q}(\mathcal{L},p):\mathbb{Q}(\mathcal{L}))=|\mathcal{V}|$.

###  2.2 Isometries on lines

In the context of framework rigidity, the group of isometries of the ambient
space is important since such isometries induce trivial flexes of a framework.
In this subsection we show basic properties of the isometry group on lines.

Let $\mathcal{L}$ be a set of lines in $\mathbb{R}^{d}$. An isometry of
$\mathcal{L}$ is a map
$\theta:\cup_{L\in\mathcal{L}}L\rightarrow\cup_{L\in\mathcal{L}}L$, such that
$|\theta(x)-\theta(y)|=|x-y|$ for all $x,y\in\cup_{L\in\mathcal{L}}L$ and such
that $\theta(L)=L$ for all $L\in\mathcal{L}$. In other words it is an isometry
of the underlying induced metric on $\cup_{L\in\mathcal{L}}L$ that induces the
identity permutation on the set of lines in $\mathcal{L}$. Let
$\mathrm{Isom}(\mathcal{L})$ be the group of isometries of $\mathcal{L}$. The
following elementary observations will be used repeatedly in the sequel.

######  Lemma 2.1.

Suppose that $\mathcal{L}=\\{L_{1},L_{2}\\}$ is a set of two lines in
$\mathbb{R}^{d}$, where $L_{1},L_{2}$ are neither parallel nor perpendicular.

  1. (1)

There is a unique pair $(x_{1},x_{2})$ of points $x_{i}\in L_{i}\ (i=1,2)$
such that $x_{i}$ is the closest point in $L_{i}$ to $L_{3-i}$. Moreover, the
coordinates of the point $x_{i}$ lie in $\mathbb{Q}(\mathcal{L})$.

  2. (2)

If $\theta\in\mathrm{Isom}(\mathcal{L})$ is a non-identity element then for
$i=1,2$, $\theta|_{L_{i}}$ is a reflection in $x_{i}$.

  3. (3)

$\mathrm{Isom}(\mathcal{L})$ is cyclic of order $2$.

###### Proof.

Consider the quadratic polynomial $f:L_{1}\times
L_{2}\rightarrow\mathbb{R},f(y_{1},y_{2})=\|y_{1}-y_{2}\|^{2}$. Since
$L_{1},L_{2}$ are not parallel, $f$ is a strictly convex quadratic function
and hence has a unique minimiser $(y_{1},y_{2})=(x_{1},x_{2})$. Therefore
$(x_{1},x_{2})$ is the unique solution to a linear system of equations with
coefficients in $\mathbb{Q}(\mathcal{L})$ and statement ${\rm(1)}$ follows
from Cramer’s rule.

The strict minimality of $f$ implies that any element $\gamma$ of
$\mathrm{Isom}(\mathcal{L})$ must fix $x_{1},x_{2}$. Hence, $\gamma$
restricted to each $L_{i}$ must be either the identity or the reflection about
$x_{i}$. The half-turn rotation of $\mathbb{R}^{d}$ about an axis through
$x_{1}$ and $x_{2}$ gives a non-identity element $\gamma$ of
$\mathrm{Isom}(\mathcal{L})$ by restriction. Also if any element $\gamma$ of
$\mathrm{Isom}(\mathcal{L})$ restricted to $L_{i}$ is the identity, it must
also be the identity on $L_{3-i}$ since $L_{1}$ and $L_{2}$ are not
perpendicular. These imply (2) and (3). ∎

We note also that if $\mathcal{L}$ is parallel then
$\mathrm{Isom}(\mathcal{L})$ is isomorphic to the Euclidean group of
isometries of $\mathbb{R}$. If $L_{1},L_{2}$ are perpendicular then
$\mathrm{Isom}(\\{L_{1},L_{2}\\})\cong\mathbb{Z}/2\times\mathbb{Z}/2$. In
particular, if $\mathcal{L}$ is not parallel then $\mathrm{Isom}(\mathcal{L})$
is finite.

The situation is more straightforward if the set of lines are non-degenerate
in a sense that we now define. Three (non-parallel) lines $L_{1},L_{2},L_{3}$
in $\mathbb{R}^{d}$ are weakly concurrent if the closest point in $L_{1}$ to
$L_{2}$ coincides with the closest point in $L_{1}$ to $L_{3}$. Note that when
$d=2$, $L_{1},L_{2},L_{3}$ are weakly concurrent if and only if they are
concurrent. We say that a set $\mathcal{L}$ of lines is in general position if

  * •

no two lines in $\mathcal{L}$ are parallel,

  * •

no two lines in $\mathcal{L}$ are perpendicular, and

  * •

no three lines in $\mathcal{L}$ are weakly concurrent.

######  Lemma 2.2.

Suppose that $\mathcal{L}$ is in general position. If $|\mathcal{L}|=1$, then
$\mathrm{Isom}(\mathcal{L})$ is isomorphic to the $1$-dimensional Euclidean
group. If $|\mathcal{L}|=2$ then $\mathrm{Isom}(\mathcal{L})$ is cyclic of
order two and the non-trivial element is a rotation about a common
perpendicular of the two lines. If $|\mathcal{L}|\geq 3$, then
$\mathrm{Isom}(\mathcal{L})$ is trivial.

###### Proof.

The cases $|\mathcal{L}|=1,2$ follow immediately from Lemma 2.1. Suppose that
$|\mathcal{L}|\geq 3$ and, for a contradiction, suppose that
$\theta\in\mathrm{Isom}(\mathcal{L})$ is non-trivial. So there is some
$L_{1}\in\mathcal{L}$ such that $\theta|_{L_{1}}$ is not the identity. Choose
$L_{2},L_{3}\in\mathcal{L}$ such that $L_{1},L_{2},L_{3}$ are pairwise
distinct. Let $x\in L_{1}$ be the closest point to $L_{2}$. By Lemma 2.1, $x$
is also the closest point to $L_{3}$. However this contradicts the fact that
$\mathcal{L}$ is in general position. ∎

We next state, in a form suitable for our purposes, one of the fundamental
theorems of real algebraic geometry. Suppose that $\mathbb{F}$ is a subfield
of $\mathbb{R}$. Let $X$ be a semi-algebraic subset of $\mathbb{R}^{d}$. We
say that $X$ is defined over $\mathbb{F}$ if there is a set of defining
polynomial equations and inequalities for $X$ that have coefficients in
$\mathbb{F}$.

######  Theorem 2.3 (Tarski [24], Seidenberg [21]).

Suppose that $\mathbb{F}$ is a subfield of $\mathbb{R}$ and that
$X\subset\mathbb{R}^{d}$ is a semi-algebraic set defined over $\mathbb{F}$.
Suppose that $f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{c}$ is a polynomial map
with coefficients in $\mathbb{F}$. Then $f(X)$ is a semi-algebraic set defined
over $\mathbb{F}$.

See [2, Theorem 2.76] for a proof of this result.

###  2.3 Rigidity of line constrained frameworks

Given a partitioned graph $G$ and a line set $\mathcal{L}$ indexed by $J$ as
above, let

$\mathcal{L}^{\mathcal{V}}=\\{p:\mathcal{V}\rightarrow\mathbb{R}^{d}\text{
such that }p(V_{i})\subset L_{i}\text{ for }i\in J\\}.$

Observe that $\mathcal{L}^{\mathcal{V}}$ is a $|\mathcal{V}|$-dimensional
linear subspace of $\mathbb{R}^{d|\mathcal{V}|}$ that is defined by equations
with coefficients in $\mathbb{Q}(\mathcal{L})$. Define the measurement map
$M_{G}:\mathcal{L}^{\mathcal{V}}\rightarrow\mathbb{R}^{\mathcal{E}}$ by
$M_{G}(p)=(\|p(u)-p(v)\|^{2})_{uv\in\mathcal{E}}$. For any subgraph $H$ of
$G$, denote $\mathcal{L}[H]=\\{L_{i}\in\mathcal{L}:V_{i}\cap
V(H)\neq\emptyset\\}$.

We say that $(G,p)$ is globally $\mathcal{L}$-rigid if $M_{G}(q)=M_{G}(p)$
implies that $q=\theta\circ p$ for some
$\theta\in\mathrm{Isom}(\mathcal{L}[G])$, and it is $\mathcal{L}$-rigid if,
for any $q$ in a neighbourhood of $p$ in $\mathcal{L}^{\mathcal{V}}$,
$M_{G}(q)=M_{G}(p)$ implies that $q=\theta\circ p$ for some
$\theta\in\mathrm{Isom}(\mathcal{L}[G])$. See Figures 1 and 2 for examples.

Figure 1: On the left a non-rigid $\mathcal{L}$-constrained framework and on
the right an $\mathcal{L}$-rigid framework which is not globally
$\mathcal{L}$-rigid.

We say that a graph $G$ is generically globally $\mathcal{L}$-rigid if for any
$\mathcal{L}$-generic $p\in\mathcal{L}^{\mathcal{V}}$, the framework $(G,p)$
is globally $\mathcal{L}$-rigid. Our main goal is to give a combinatorial
characterisation of partitioned graphs $G$ that are globally
$\mathcal{L}$-rigid in the case when $\mathcal{L}$ is in general position. In
particular we shall see that this characterisation is independent of
$\mathcal{L}$, as long as $\mathcal{L}$ is in general position. Moreover, as a
consequence of our characterisation, we will also be able to deduce that the
property of global $\mathcal{L}$-rigidity is a generic property of partitioned
graphs.

For rigidity analysis, it is a common strategy to consider a linearised
version known as infinitesimal rigidity. Suppose that $(G,p)$ is an
$\mathcal{L}$-constrained framework. An infinitesimal flex of $(G,p)$ is a
function $f:\mathcal{V}\rightarrow\mathbb{R}^{d}$ satisfying

$(p(u)-p(v))\cdot(f(u)-f(v))=0\text{ for all $uv\in\mathcal{E}$ and}$ (1)
$A_{i}f(v)=0\text{ for $1\leq i\leq k,v\in V_{i}$\ ,}$ (2)

where $A_{i}x=b_{i}$ is the standard equation of the line $L_{i}$. The
coefficient matrix of the linear system defined by (1) and (2), denoted
$R(G,p,\mathcal{L})$, is called the _$\mathcal{L}$ -rigidity matrix_ of
$(G,p)$. Thus an infinitesimal flex is an element of
$\ker(R(G,p,\mathcal{L}))$.

We say that $(G,p)$ is infinitesimally $\mathcal{L}$-rigid if

$\dim(\ker(R(G,p,\mathcal{L})))=\begin{cases}1&(\text{if all lines in
$\mathcal{L}[G]$ are parallel})\\\ 0&(\text{otherwise}).\end{cases}$ (3)

As observed earlier, the right hand side of (3) is equal to the dimension of
$\mathrm{Isom}(\mathcal{L}[G])$, validating our definition of infinitesimal
rigidity.

In general an $\mathcal{L}$-rigid framework need not be infinitesimally
$\mathcal{L}$-rigid. However we will show that for $\mathcal{L}$-generic
frameworks rigidity and infinitesimal rigidity are equivalent. The arguments
use a well known technique due to Asimow and Roth in the case of bar-joint
frameworks [1] and so we only sketch the proofs.

######  Lemma 2.4.

Suppose that $(G,p)$ is $\mathcal{L}$-generic and let $k=\dim\ker
R(G,p,\mathcal{L})$. Then $M_{G}^{-1}(M_{G}(p))$ is an algebraic set of
dimension $k$. Moreover $p$ has a open neighbourhood $U$ in
$\mathcal{L}^{\mathcal{V}}$ such that $M_{G}^{-1}(M_{G}(p))\cap U$ is a
smoothly embedded submanifold of $U$ of dimension $k$.

###### Sketch of proof..

First observe that we can view the submatrix of $R(G,p,\mathcal{L})$ induced
by the rows corresponding to (1) as the Jacobian matrix at $p$ of the
polynomial function $M_{G}$. The fact that $p$ is $\mathcal{L}$-generic
ensures that the rank of $R(G,p,\mathcal{L})$ is maximal over all points in
$\mathcal{L}^{\mathcal{V}}$ which implies the first conclusion. Moreover this
rank is constant in an open neighbourhood of $p$. Now the constant rank
theorem [22, Theorem 9] implies the second conclusion. ∎

######  Proposition 2.5.

Let $(G,p)$ be a generic $\mathcal{L}$-constrained framework. Then, $(G,p)$ is
rigid if and only if it is infinitesimally rigid. ∎

###### Sketch of proof.

The case when $G[\mathcal{L}]$ is parallel can be deduced from the standard
Asimow-Roth theorem for bar-joint frameworks in one dimension [1]. If
$G[\mathcal{L}]$ is not parallel then $(G,p)$ is $\mathcal{L}$-rigid if and
only if there is some neighbourhood $U$ of $p$ in $\mathcal{L}^{\mathcal{V}}$
such that $U\cap M_{G}^{-1}(M_{G}(p))=\\{p\\}$. Now the required conclusion
follows from Lemma 2.4. ∎

In view of this, we say that $G$ is $\mathcal{L}$-rigid if $(G,p)$ is
infinitesimally $\mathcal{L}$-rigid for all $\mathcal{L}$-generic
$p\in\mathcal{L}^{\mathcal{V}}$. Note that the rank of $R(G,p,\mathcal{L})$ is
determined by the set of vanishing minors of $R(G,p,\mathcal{L})$ and it
follows that the maximum rank of $R(G,p,\mathcal{L})$ is attained at all
$\mathcal{L}$-generic $p\in\mathcal{L}^{\mathcal{V}}$. It follows that $(G,p)$
is infinitesimally $\mathcal{L}$-rigid for some $p$ if and only if $G$ is
$\mathcal{L}$-rigid.

We conclude this section by deriving another useful property of generic
infinitesimally $\mathcal{L}$-rigid frameworks based on Lemma 2.4.

######  Lemma 2.6.

Suppose that $G[\mathcal{L}]$ is not parallel and that $(G,p)$ is
$\mathcal{L}$-generic and infinitesimally $\mathcal{L}$-rigid. Then

  1. (1)

$M_{G}^{-1}(M_{G}(p))$ is finite, and

  2. (2)

if $q\in M_{G}^{-1}(M_{G}(p))$ and $x$ is a coordinate of $q(v)$ for some
$v\in\mathcal{V}$, then $x$ is algebraic over $\mathbb{Q}(\mathcal{L},p)$.

###### Proof.

Since $G[\mathcal{L}]$ is not parallel and $(G,p)$ is infinitesimally
$\mathcal{L}$-rigid, it follows that $\dim(\ker(R(G,p,\mathcal{L})))=0$. The
first conclusion now follows from Lemma 2.4.

To prove the second conclusion, observe that since $M_{G}^{-1}(M_{G}(p))$ is a
finite semi-algebraic set defined over $\mathbb{Q}(\mathcal{L},p)$, Theorem
2.3 implies that, for any $1\leq i\leq d$, the set of $i$-th coordinates of
points in $M_{G}^{-1}(M_{G}(p))$ is again a semi-algebraic subset of
$\mathbb{R}$ defined over $\mathbb{Q}(\mathcal{L},p)$. Moreover, since this
set is finite, it is a subset of the set of solutions of a nontrivial
polynomial equation with coefficients in $\mathbb{Q}(\mathcal{L},p)$. ∎

##  3 Characterising Generic $\mathcal{L}$-rigidity

In [5, Theorem 4.3] a combinatorial characterisation of infinitesimal rigidity
for line constrained frameworks was given in the case of arbitrary line
constraints, but for generic point configurations. In [5], the genericity
assumption for point configurations is defined with respect to the ambient
Euclidean space $\mathbb{R}^{d}$, and it is not difficult to see that the
result in [5] leads to a characterisation for line constrained frameworks in
our sense, but only in the case that at most two vertices lie on one line as a
consequence of their genericity assumption.

Our goal in this section is to extend this to a characterisation of
$\mathcal{L}$-rigidity for arbitrary line sets $\mathcal{L}$ with no
restrictions on the vertex partition. This can be accomplished by directly
analyzing the rank of the rigidity matrix $R(G,p,\mathcal{L})$ of an
$\mathcal{L}$-constrained framework $(G,p)$ of a given graph $G$, unlike the
proof in [5], which is based on an inductive construction.

Let $v_{i}$ be an unit direction vector of the line $L_{i}$. Then any
infinitesimal flex $f$ of $(G,p)$ is written as $f(u)=t_{u}v_{i}$ for some
scalar $t_{u}$ for each $u\in V_{i}$. Let $\theta_{u,v}$ be the angle between
the vector $v_{i}$ and $p(v)-p(u)$ for each edge $uv\in\mathcal{E}$ with $u\in
V_{i}$. Then the linear system (1) and (2) may be rewritten as

$t_{u}\cos\theta_{u,v}+t_{v}\cos\theta_{v,u}=0\quad\text{(for
$uv\in\mathcal{E}$)}.$ (4)

The matrix $R^{\prime}(G,p,L)$ representing (4) with variables $t_{u}\
(u\in\mathcal{V})$ has size $|\mathcal{E}|\times|\mathcal{V}|$, and each
column is associated with a vertex and each row is associated with an edge.
Its zero-nonzero pattern is the same as that of the incidence matrix of $G$,
and each nonzero entry has the form $\cos\theta_{u,v}$. Since $\ker
R^{\prime}(G,p,\mathcal{L})=\ker R(G,p,\mathcal{L})$, it suffices to analyze
the rank of $R^{\prime}(G,p,\mathcal{L})$.

######  Theorem 3.1.

Let $G$ be a partitioned graph.

  * (1)

If $\mathcal{L}[G]$ is parallel then $G$ is $\mathcal{L}$-rigid if and only if
it is connected.

  * (2)

If $\mathcal{L}[G]$ is not parallel then $G$ is $\mathcal{L}$-rigid if and
only if every component of $G$ contains a cycle that contains an edge $uv$
associated with non-parallel lines $L_{u}$ and $L_{v}$.

###### Proof.

For simplicity, let $\mathcal{L}=\mathcal{L}[G]$. Let $(G,p,\mathcal{L})$ be
an $\mathcal{L}$-constrained framework. We analyse the rank of
$R^{\prime}(G,p,\mathcal{L})$.

Suppose first that $\mathcal{L}$ is parallel, i.e., $v_{i}=v_{j}$ for every
$L_{i}$ and $L_{j}$ in $\mathcal{L}$. Then, for each $uv\in\mathcal{E}$,
$\cos\theta_{u,v}=-\cos\theta_{u,v}$. Also, if $p$ is $\mathcal{L}$-generic,
$\cos\theta_{u,v}\neq 0$. Hence, by dividing each row of $R(G,p,\mathcal{L})$
associated with $uv$ by $\cos\theta_{u,v}$, $R^{\prime}(G,p,\mathcal{L})$ is
converted to the incidence matrix of an edge-oriented digraph of $G$. So the
row matroid of $R^{\prime}(G,p,\mathcal{L})$ is the graphic matroid of $G$,
and hence the statement follows in the case when $\mathcal{L}[G]$ is parallel.

Suppose next that $\mathcal{L}$ is not parallel. Our goal is to show that
$R^{\prime}(G,p,\mathcal{L})$ is non-singular if and only if every component
of $G$ contains a cycle that contains an edge $uv$ such that $L_{u}$ and
$L_{v}$ are not parallel. If $G$ is not connected, then
$R^{\prime}(G,p,\mathcal{L})$ is the direct product of the corresponding
matrices of the connected components of $G$. Hence, it suffices to consider
the case when $G$ is connected.

For $R^{\prime}(G,p,\mathcal{L})$ to be non-singular, it is necessary that
$|\mathcal{E}|=|\mathcal{V}|$. Since $G$ is connected,
$|\mathcal{E}|=|\mathcal{V}|$ implies that $G$ contains exactly one cycle $C$.
Then, we can orient each edge $e$ such that each vertex has in-degree one in
the resulting directed graph. Let $h(e)$ and $t(e)$ be the head and the tail
of an edge $e$ in this orientation. Then, from the fact that the zero-nonzero
pattern of $R^{\prime}(G,p,\mathcal{L})$ is the same as that of the incidence
matrix of $G$, the determinant of $R^{\prime}(G,p,\mathcal{L})$ can be
expanded as follows:

$\det R^{\prime}(G,p,\mathcal{L})=\prod_{e\in\mathcal{E}\setminus
E(C)}\cos\theta_{h(e),t(e)}\left(\prod_{e\in
E(C)}\cos\theta_{h(e),t(e)}+(-1)^{|E(C)|-1}\prod_{e\in
E(C)}\cos\theta_{t(e),h(e)}\right).$

If $\mathcal{L}[C]$ is parallel, then
$\cos\theta_{h(e),t(e)}=-\cos\theta_{t(e),h(e)}$ for any edge $e$ in $C$, and
hence the two terms in the parentheses cancel, i.e., $\det
R^{\prime}(G,p,\mathcal{L})=0$.

If $C$ contains an edge $e=uv$ such that $L_{u}$ and $L_{v}$ are not parallel,
then we consider a point configuration $p$ as follows. We first put $p(w)$ for
all $w\in\mathcal{L}\setminus\\{u\\}$ generically on each associated line, and
put $p(u)$ such that $p(v)-p(u)$ is orthogonal to $L_{u}$. Then
$\cos\theta_{u,v}=0$. Moreover, since $L_{u}$ is not parallel to $L_{v}$ and
the points are located generically except for $p(u)$, $\cos\theta_{v,u}\neq 0$
and $\cos\theta_{u^{\prime},v^{\prime}}\neq 0$ for any other edge
$u^{\prime}v^{\prime}$. Thus, among the two terms in the expansion of $\det
R^{\prime}(G,p,\mathcal{L})$, exactly one term is nonzero. Hence $\det
R^{\prime}(G,p,\mathcal{L})$ is non-singular.

Therefore, if $G$ is connected, then $\dim\ker R^{\prime}(G,p,\mathcal{L})=0$
if and only if $G$ contains a cycle that has an edge $uv$ associated with non-
parallel lines $L_{u}$ and $L_{v}$. ∎

##  4 Necessary Conditions for Global $\mathcal{L}$-rigidity

The rest of the paper is devoted to the line constrained global rigidity
problem. In that setting the full isometry group of any finite subset of
$\mathcal{L}$ can play a role, so from now on we assume that

$\mathcal{L}$ is in general position.

When $d=2$, this is equivalent to the assumption that no two lines are
parallel and perpendicular and no three lines are concurrent.

The case in which $G$ is not crossing corresponds to the classical and well
understood generic global rigidity problem for frameworks in $\mathbb{R}^{1}$.
Thus we shall also assume from now on that

$G$ is a crossing graph,

i.e. at least two $V_{i}$ are non-empty. These assumptions will always be in
force. However, we will restate them explicitly in the statements of the main
results.

We now collect necessary conditions for global $\mathcal{L}$-rigidity. We
begin with two necessary connectivity conditions. We say that a connected
component of a graph is proper if it is a proper subgraph.

######  Lemma 4.1.

Let $(G,p)$ be a $\mathcal{L}$-generic $\mathcal{L}$-constrained framework in
$\mathbb{R}^{d}$. Suppose that $(G,p)$ is globally $\mathcal{L}$-rigid. Then,
every proper connected component $H$ of $G$ satisfies $|\mathcal{L}[H]|\geq
3$.

###### Proof.

Suppose there is a proper connected component $H$ of $G$ with
$|\mathcal{L}[H]|\leq 2$. By Lemma 2.2, there exists a non-identity element
$\gamma\in\mathrm{Isom}(\mathcal{L}[H])$. Define $q$ such that $q(v)=\gamma
p(v)$ for each vertex $v$ in $H$ and $q(v)=p(v)$ for the remaining vertices
$v$ of $G$. Then $M_{G}(p)=M_{G}(q)$ holds. However, since $H$ is a proper
subgraph of $G$ and $p$ is $\mathcal{L}$-generic, $q\neq\theta\circ p$ for any
$\theta\in\mathrm{Isom}(\mathcal{L}[G])$. This contradicts the global
$\mathcal{L}$-rigidity of $(G,p)$. ∎

######  Lemma 4.2.

Let $(G,p)$ be a $\mathcal{L}$-generic $\mathcal{L}$-constrained framework in
$\mathbb{R}^{d}$. Suppose that $(G,p)$ is globally $\mathcal{L}$-rigid. Then,
for every $v\in\mathcal{V}$, every connected component $H$ of $G-v$ satisfies
$|\mathcal{L}[H]|\geq 2$.

###### Proof.

Let $H$ be a component of $G-v$. Suppose, for a contradiction, that
$V(H)\subseteq V_{i}$ for some $V_{i}$ in the vertex partition of $G$. Let
$\gamma$ be the reflection in the hyperplane containing $p(v)$ that is
perpendicular to $L_{i}$. Since $\mathcal{L}$ is in general position and $p$
is $\mathcal{L}$-generic, the restriction of $\gamma$ to $\bigcup_{i}L_{i}$ is
not in $\mathrm{Isom}(\mathcal{L}[G])$.

Let $q(y)=p(y)$ for all $y\in V(G)\setminus V(H)$ and $q(y)=\gamma p(y)$ for
$y\in V(H)$. Then $M_{G}(q)=M_{G}(p)$ holds. Hence, by the global
$\mathcal{L}$-rigidity of $(G,p)$, $q=\theta p$ for some
$\theta\in\mathrm{Isom}(\mathcal{L}[G])$. Now $p(v)=q(v)$ and since $p$ is
$\mathcal{L}$-generic it follows from Lemma 2.1 that $\theta=\mathrm{Id}$.
Therefore $q=p$ and it follows that $\gamma p(y)=p(y)$ for all $y\in V(H)$
contradicting the fact that $p$ is $\mathcal{L}$-generic since $\gamma$ is a
reflection on $L_{i}$. ∎

Next we prove a line constrained version of a well known result of Hendrickson
[10]. The standard, and essentially only, known proof of Hendrickson’s result
for bar-joint frameworks uses Sard’s theorem. Our approach is similar but
avoids applying Sard’s theorem. Our new technique also works for bar-joint
frameworks and we believe it will be useful for rigidity problems in other
settings. The following lemma is a key ingredient in our proof. Recall that a
graph is said to be even if every vertex has even degree.

######  Lemma 4.3.

If $X$ is a bounded real algebraic curve then it is homeomorphic to the
geometric realisation of an even graph whose vertices are the singular points
of $X$.

###### Proof.

Note that $X$ is compact in the usual Euclidean topology, as it is both
bounded and closed. Therefore, we have a finite covering
$\\{N_{\epsilon}(p_{i})\\}_{i=1,\dots,n}$ of $X$ where $p_{i}\in X$ and
$N_{\epsilon}(p_{i})$ is the $\epsilon$-neighbourhood of $p_{i}$ for
sufficiently small $\epsilon>0$. As real algebraic curves have finitely many
singular points [3, Proposition 3.3.14], we can chose a finite covering such
that it contains all $\epsilon$-neighbourhoods of singular points. Now using
[3, Theorem 9.5.7], for every $N_{\epsilon}(p_{i})$ we have an even number of
half-branches centered at $p_{i}$. From this we can construct a graph $G$ with
vertices corresponding to $p_{i}$ and edges corresponding to the half-
branches. Without loss of generality we can assume that we are in a connected
component of $X$, which implies that $G$ is connected. Now let $H$ be the
graph obtained from $G$ by smoothing out all the vertices of $G$ which are
regular points of $X$ so that the vertices of $H$ precisely correspond to the
singular points of $X$. In other words, $H$ is a geometric realisation of an
even graph with vertices corresponding to the singular points of $X$. ∎

######  Theorem 4.4.

Suppose that $p\in\mathcal{L}^{\mathcal{V}}$ is $\mathcal{L}$-generic and that
$(G,p)$ is globally $\mathcal{L}$-rigid. Then $(G-uv,p)$ is infinitesimally
$\mathcal{L}$-rigid for any edge $uv\in\mathcal{E}$.

###### Proof.

First observe that $(G,p)$ is infinitesimally rigid by Proposition 2.5. Hence,
Lemma 2.6 implies that $\dim(\ker(R(G,p,\mathcal{L})))=0$. Similarly, by Lemma
2.4, $X=M_{G-uv}^{-1}(M_{G-uv}(p))$ is an algebraic subset of
$\mathcal{L}^{\mathcal{V}}$ and
$\dim(X)=\dim(\ker(R(G-uv,p,\mathcal{L})))\leq\dim(\ker(R(G,p,\mathcal{L})))+1=1$.
If $\dim(X)=0$ then $(G-uv,p)$ is infinitesimally $\mathcal{L}$-rigid. So we
may assume that $\dim(X)=1$ and so $X$ is an algebraic curve defined over
$\mathbb{Q}(\mathcal{L},p)$.

######  Claim 4.5.

$X$ is a bounded subset of $\mathcal{L}^{\mathcal{V}}$.

###### Proof.

First we make a general observation. Suppose that $H$ is a connected crossing
graph and that $r\in\mathcal{L}^{V(H)}$. For any $w\in V(H)$ there is some
$z\in V(H)$ such that $L_{w}$ and $L_{z}$ are not parallel. Since there is a
path $w=u_{1},u_{2},\dots,u_{k}=z$ in $H$, we see that for any $q\in
M_{H}^{-1}(M_{H}(r))$,
$\|q(w)-q(z)\|\leq\sum_{i=1}^{k-1}\|q(u_{i})-q(u_{i+1})\|=\sum_{i=1}^{k-1}\|r(u_{i})-r(u_{i+1})\|$.
Since $L_{w}$ and $L_{z}$ are not parallel, it follows that $q(w)$ lies in
bounded subset of $L_{w}$ and so $M_{H}^{-1}(M_{H}(r))$ is bounded.

Now suppose that $G^{\prime}$ is the component of $G$ that contains $uv$ and
$G^{\prime\prime}=G-G^{\prime}$. Then $X=Y\times Z$ where
$Y=M_{G^{\prime}-uv}^{-1}(M_{G^{\prime}-uv}(p|_{V(G^{\prime})}))$ and
$Z=M_{G^{\prime\prime}}^{-1}(M_{G^{\prime\prime}}(p|_{V(G^{\prime\prime})}))$.
Since $(G,p)$ is globally $\mathcal{L}$-rigid, it follows from Lemma 4.1 that
every component of $G^{\prime\prime}$ is crossing and so $Z$ is bounded using
the general observation above. Thus $X$ is bounded if and only if $Y$ is
bounded and so we may as well assume from now that $G=G^{\prime}$ is a
connected graph. If $G-uv$ is a connected graph then since it is also a
crossing graph the conclusion follows from the general observation above.

Hence we can assume that $G-uv$ is not connected and (since $G$ is connected)
has two components $H$ and $K$. Suppose $H$ and $K$ contain the vertices $u$
and $v$ respectively. If $|\mathcal{L}[H]|=1$ then, since $p$ is generic (in
particular $p(u)-p(v)$ is not perpendicular to $L_{u}$), we can slide
$(H,p|_{V(H)})$ along $\mathcal{L}[H]$ to find $(H,p^{\prime})$ such that
$\|p^{\prime}(u)-p(v)\|=\|p(u)-p(v)\|$ and so that $p^{\prime}\neq p|_{V(H)}$,
contradicting the global rigidity of $(G,p)$. Thus $|\mathcal{L}[H]|\geq 2$,
and similarly $|\mathcal{L}[K]|\geq 2$. Let
$Y=\\{q\in\mathcal{L}^{V(H)}:M_{H}(q)=M_{H}(p|_{V(H)})\\}$ and
$Z=\\{q\in\mathcal{L}^{V(K)}:M_{K}(q)=M_{K}(p|_{V(K)})\\}$. Using the general
observation we see that both $Y$ and $Z$ are bounded. Now, $X\subset Y\times
Z$ and the claim follows. ∎

Thus $X$ is a bounded real algebraic curve, and so by Lemma 4.3, it is
homeomorphic to the geometric realisation of an even graph whose vertices are
singular points of $X$. Also $p$, being $\mathcal{L}$-generic, is a non-
singular point of $X$ by Lemma 2.4 and therefore lies in the interior of an
edge of $X$ (viewed as a graph).

In the case where $|\mathcal{L}[G]|\geq 3$, $\mathrm{Isom}(\mathcal{L}[G])$ is
trivial by Lemma 2.2. In the case where $|\mathcal{L}[G]|=2$, let $\theta$ be
the unique non-trivial element of $\mathrm{Isom}(\mathcal{L}[G])$. We show
that $\theta$ acts without fixed points on $X$. To see this, suppose $\theta$
fixes $q\in X$. Then by Lemma 2.1 $\theta|_{L_{i}}$ is the reflection around
$x_{i}$ for each $i=1,2$, where $x_{i}$ is the closest point in $L_{i}$ to
$L_{3-i}$. So $\theta q=q$ implies that each point of $q$ lies in $x_{1}$ or
$x_{2}$, and $\|q(w)-q(z)\|^{2}$ is equal to either $\|x_{1}-x_{2}\|^{2}$ or
$0$. However, since $x_{1}$ and $x_{2}$ are algebraic over
$\mathbb{Q}(\mathcal{L}[G])$, $\|p(w)-p(z)\|^{2}$ would be algebraic over
$\mathbb{Q}(\mathcal{L}[G])$. This contradicts the $\mathcal{L}$-genericity of
$p$. Therefore $\theta$ induces a fixed point free involution of $X$ in the
case $|\mathcal{L}[G]|=2$.

Thus, in all cases, $X/\mathrm{Isom}(\mathcal{L}[G])$ is homeomorphic to the
geometric realisation of an even graph. Let $\overline{p}$ be the image of $p$
in $X/\mathrm{Isom}(\mathcal{L}[G])$. Since $p$ is $\mathcal{L}$-generic,
Lemma 2.4 implies that a neighbourhood of $p$ in $X$ is homeomorphic to
$\mathbb{R}$ and thus a neighbourhood of $\overline{p}$ in
$X/\mathrm{Isom}(\mathcal{L}[G])$ is homeomorphic to $\mathbb{R}$. In
particular this implies that $\overline{p}$ is either an interior point of an
edge or a vertex of degree 2 in $X/\mathrm{Isom}(\mathcal{L}[G])$ (viewed as a
graph). Let $Y$ be the component of $X/\mathrm{Isom}(\mathcal{L}[G])$ that
contains $\overline{p}$. Since a connected even graph is 2-edge-connected it
follows that $Y-\overline{p}$ is connected. Now define
$f:Y\rightarrow\mathbb{R}$ by $f(\overline{q})=\|q(u)-q(u)\|^{2}$. Since
$(G,p)$ is rigid and $(G-uv,p)$ is not rigid, Proposition 2.5 implies that
$(G,p)$ is infinitesimally rigid and $(G-uv,p)$ is not. Hence
$f^{\prime}(p)\neq 0$. So there are points $q_{1},q_{2}\in Y$ such that
$f(\overline{q}_{1})<f(\overline{p})<f(\overline{q}_{2})$. Now, since
$Y-\overline{p}$ is connected $Y-\overline{p}$ has a path between
$\overline{q}_{1}$ and $\overline{q}_{2}$, and the path contains a point
$p^{\prime}\in X$ such that $\overline{p}^{\prime}\neq\overline{p}$ and
$f(\overline{p}^{\prime})=f(\overline{p})$ contradicting the fact that $(G,p)$
is globally $\mathcal{L}$-rigid. ∎

We say that a partitioned graph $G=(\mathcal{V},\mathcal{E})$ is P-connected
if every proper connected component $H$ of $G$ satisfies $|\mathcal{L}[H]|\geq
3$ and every connected component $H^{\prime}$ of $G-v$ satisfies
$|\mathcal{L}[H^{\prime}]|\geq 2$ for every $v\in\mathcal{V}$. See Figure 2
(left) for an example. Note that a P-connected graph is not necessarily
connected.

We say that $G$ is redundantly $\mathcal{L}$-rigid if $G-e$ is
$\mathcal{L}$-rigid for all $e\in\mathcal{E}$. Observe that in the case that
$\mathcal{L}$ is in general position and $G$ is crossing, Theorem 3.1 implies
that $G$ is redundantly rigid if and only if, for every $e\in\mathcal{E}$,
every component of $G-e$ contains a crossing cycle. See Figure 2 (right).
Lemma 4.1, Lemma 4.2 and Theorem 4.4 imply the following necessary conditions
for a partitioned graph to be generically globally $\mathcal{L}$-rigid.

Figure 2: Examples of $\mathcal{L}$-frameworks which are not globally
$\mathcal{L}$-rigid. On the left the underlying graph is redundantly
$\mathcal{L}$-rigid but not P-connected. On the right the underlying graph is
P-connected but not redundantly $\mathcal{L}$-rigid. In both cases, a global
flex is indicated with dashed bars.

######  Theorem 4.6.

Suppose that $\mathcal{L}$ is in general position and $G$ is a crossing
partitioned graph. If $G$ is generically globally $\mathcal{L}$-rigid then $G$
is P-connected and redundantly $\mathcal{L}$-rigid.

##  5 Inductive Properties

Our goal is to prove the converse of Theorem 4.6. The basic strategy will be
induction on the number of vertices of the graph and in this section we will
analyse the geometric properties of the relevant inductive operations. For a
graph $G$, a subdivision of an edge $uv$ replaces $uv$ with new edges $uw$ and
$wv$ by adding a new vertex $w$ of degree two. The inverse operation is called
smoothing at $w$. We will show that the subdivision operation preserves
generic global $\mathcal{L}$-rigidity. We begin with an elementary geometric
lemma.

######  Lemma 5.1.

Suppose that $L$ is a line in $\mathbb{R}^{d}$ with equation $Ax=b$ and that
$p_{1},p_{2}$ are distinct points in $\mathbb{R}^{d}$. Let $\mathbb{F}$ be the
smallest subfield of $\mathbb{R}$ that contains all the entries of
$A,b,p_{1},p_{2}$. Let $f:L\rightarrow\mathbb{R}^{2}$ be given by
$f(x)=(\|x-p_{1}\|^{2},\|x-p_{2}\|^{2})$. Then the following hold:

  1. (1)

If the line segment $[p_{1},p_{2}]$ is perpendicular to $L$ then $f(L)$ is a
half-line defined over $\mathbb{F}$.

  2. (2)

If $[p_{1},p_{2}]$ is not perpendicular to $L$ then $f(L)$ is a parabola that
is defined over $\mathbb{F}$. In particular $f(L)$ is an irreducible algebraic
set defined over $\mathbb{F}$ in this case.

###### Proof.

Let $\pi:\mathbb{R}^{d}\rightarrow L$ be the orthogonal projection. Then

$f(x)=(\|x-\pi(p_{1})\|^{2},\|x-\pi(p_{2})\|^{2})+(\|p_{1}-\pi(p_{1})\|^{2},\|p_{2}-\pi(p_{2})\|^{2}).$

Now if $\pi(p_{1})=\pi(p_{2})$ then
$\\{(\|x-\pi(p_{1})\|^{2},\|x-\pi(p_{2})\|^{2}),x\in L\\}=\\{(a,a):a\geq
0\\}$, whereas it is elementary to check that if $\pi(p_{1})\neq\pi(p_{2})$
then $\\{(\|x-\pi(p_{1})\|^{2},\|x-\pi(p_{2})\|^{2}),x\in L\\}$ is a
parameterisation of a parabola. ∎

######  Example 1.

In order to explain the intuition behind Lemma 5.1, we can work with $d=2$ and
choose local coordinates on a given line $L$ such that it is represented by
the $x$-axis i.e., $L=\\{(t,0):t\in\mathbb{R}\\}$. The two parts of the lemma
are explained as follows:

  1. 1.

If the line segment $[p_{1},p_{2}]$ is perpendicular to $L$, then $f(L)$ is a
half-line. Without loss of generality we can choose $p_{1}=(0,1)$ and
$p_{2}=(0,-1)$. Then $f(L)$ is given by
$\\{(t^{2}+1,t^{2}+1):t\in\mathbb{R}\\}$ which describes a half line in
$\mathbb{R}^{2}$ starting at $(1,1)$ with a slope of $1$ from $x$-axis, as
depicted in Figure 3 (left).

  2. 2.

If the line segment $[p_{1},p_{2}]$ is not perpendicular to $L$, then $f(L)$
is a parabola. Similar to the above case we can choose $p_{1}=(0,1)$ and
$p_{2}=(1,0)$, where $f(L)$ is given by
$\\{(t^{2}+1,t^{2}+1-2t):t\in\mathbb{R}\\}$. This is a parametric equation of
parabola whose major-axis is rotated from the reference axis. See Figure 3
(right).

Figure 3: Figures for Example 1.

We also remark the following elementary fact since it is used frequently in
the subsequent discussion.

######  Lemma 5.2.

Let $L_{1},L_{2}$ be lines in $\mathbb{R}^{d}$ in general position,
$\pi:\mathbb{R}^{d}\rightarrow L_{2}$ be the orthogonal projection to $L_{2}$,
and let $f:L_{1}\rightarrow\mathbb{R}$ be given by $f(x)=\|x-\pi(x)\|^{2}$.
Then $f$ is a strictly convex function, whose minimum is attained at the
closest point to $L_{2}$ and which is symmetric with respect to the closest
point.

Lemma 5.2 and Lemma 2.1 in particular imply that, if $x_{1}$ and $x_{2}$ are
two points on $L_{1}$ such that $\|x_{1}-\pi(x_{1})\|=\|x_{2}-\pi(x_{2})\|$,
then there is $\theta\in\mathrm{Isom}(\\{L_{1},L_{2}\\})$ such that
$x_{2}=\theta x_{1}$.

The following technical lemma is a key observation in the proof of Theorem
5.5.

######  Lemma 5.3.

Let $(G,p)$ be an $\mathcal{L}$-generic $\mathcal{L}$-constrained framework,
and let $u,v,w$ be distinct vertices of $G$ such that $uw$ and $vw$ are edges
of $G$. Suppose that $(G-w,p|_{\mathcal{V}-w})$ is infinitesimally
$\mathcal{L}$-rigid. Then, for each $q\in M_{G}^{-1}(M_{G}(p))$, we have
$\|p(u)-p(v)\|=\|q(u)-q(v)\|$. Moreover, at least one of the following holds:

  * •

$L_{u}=L_{w}$,

  * •

$L_{v}=L_{w}$, or

  * •

there exists $\gamma\in\mathrm{Isom}(\\{L_{u},L_{v},L_{w}\\})$ such that
$q(x)=\gamma p(x)$ for $x\in\\{u,v,w\\}$.

###### Proof.

Pick any $q\in M_{G}^{-1}(M_{G}(p))$, and define
$f:L_{w}\rightarrow\mathbb{R}^{2}$ by $f(x)=(\|x-p(u)\|^{2},\|x-p(v)\|^{2})$
and $g:L_{w}\rightarrow\mathbb{R}^{2}$ by
$g(x)=(\|x-q(u)\|^{2},\|x-q(v)\|^{2})$. Since $p$ is generic it follows from
Lemma 5.1 that $f(L_{w})$ is a non-linear irreducible algebraic curve defined
over $\mathbb{Q}(\mathcal{L},p|_{\mathcal{V}-w})$. On the other hand, by Lemma
5.1, $g(L_{w})$ is either an irreducible algebraic curve over
$\mathbb{Q}(\mathcal{L},q|_{\mathcal{V}-w})$ or is contained in a line in
$\mathbb{R}^{2}$ that is defined over
$\mathbb{Q}(\mathcal{L},q|_{\mathcal{V}-w})$. Moreover, by Lemma 2.6,
$\mathbb{Q}(\mathcal{L},q|_{\mathcal{V}-w})$ is contained in the algebraic
closure of $\mathbb{Q}(\mathcal{L},p|_{\mathcal{V}-w})$. Hence, $g(L_{w})$ is
also defined over $\mathbb{Q}(\mathcal{L},p|_{\mathcal{V}-w})$. Now observe
that $f(p(w))\in f(L_{w})\cap g(L_{w})$. Since at least one coordinate of
$p(w)$ is transcendental over $\mathbb{Q}(\mathcal{L},p|_{\mathcal{V}-w})$, at
least one coordinate of $f(p(w))$ is transcendental over
$\mathbb{Q}(\mathcal{L},p|_{\mathcal{V}-w})$. Since each point in
$f(L_{w})\cap g(L_{w})$ would be algebraic over
$\mathbb{Q}(\mathcal{L},p|_{\mathcal{V}-w})$ if it were 0-dimensional, it
follows that $f(L_{w})\cap g(L_{w})$ is not 0-dimensional. Since $f(L_{w})$ is
irreducible, it further implies that $f(L_{w})=g(L_{w})$.

Let $\pi:\mathbb{R}^{d}\rightarrow L_{w}$ be the orthogonal projection.

######  Claim 5.4.

It follows that

  1. (a)

$\|p(u)-\pi(p(u))\|=\|q(u)-\pi(q(u))\|$ and
$\|p(v)-\pi(p(v))\|=\|q(v)-\pi(q(v))\|$, and

  2. (b)

$\|\pi(p(u))-\pi(p(v))\|=\|\pi(q(u))-\pi(q(v))\|$.

###### Proof of claim..

Observe that

$\displaystyle\|p(u)-\pi(p(u))\|$ $\displaystyle=\min\\{\sqrt{x}:(x,y)\in
f(L_{w})\\}$ $\displaystyle=\min\\{\sqrt{x}:(x,y)\in
g(L_{w})\\}=\|q(u)-\pi(q(u))\|,$

where the second equation follows from $f(L_{w})=g(L_{w})$. This proves (a).
For (b), we have

$\displaystyle\|\pi(p(u))-\pi(p(v))\|$
$\displaystyle=\min\\{\sqrt{x-\|p(u)-\pi(p(u))\|^{2}}+\sqrt{y-\|p(v)-\pi(p(v))\|^{2}}:(x,y)\in
f(L_{w})\\},$ $\displaystyle\|\pi(q(u))-\pi(q(v))\|$
$\displaystyle=\min\\{\sqrt{x-\|q(u)-\pi(q(u))\|^{2}}+\sqrt{y-\|q(v)-\pi(q(v))\|^{2}}:(x,y)\in
g(L_{w})\\}.$

Using (a) and $f(L_{w})=g(L_{w})$, (b) follows. ∎

By Claim 5.4(a) and Lemma 5.2, at least one of the followings hold for vertex
$u$:

  * •

$L_{u}=L_{w}$,

  * •

$p(u)=q(u)$, or

  * •

$p(u)=\theta q(u)$, where $\theta$ is the nontrivial element in
$\mathrm{Isom}(\\{L_{u},L_{w}\\})$.

Indeed, if $L_{u}\neq L_{w}$ and $p(u)\neq q(u)$, then Claim 5.4(a) and Lemma
5.2 imply that $p(u)$ and $q(u)$ are symmetric with respect to the closest
point of $L_{u}$ to $L_{w}$, and hence $p(u)=\theta q(u)$ for the nontrivial
element $\theta$ in $\mathrm{Isom}(\\{L_{u},L_{w}\\})$. The corresponding
property also holds for vertex $v$.

Suppose $L_{u}=L_{w}$. By Claim 5.4, $\|p(v)-\pi(p(v))\|=\|q(v)-\pi(q(v))\|$
and $\|p(u)-\pi(p(v))\|=\|q(u)-\pi(q(v))\|$ hold, and by Pythagoras theorem we
get $\|p(u)-p(v)\|=\|q(u)-q(v)\|$ as required.

Symmetrically, the statement holds if $L_{v}=L_{w}$. Hence, in the subsequent
discussion, we assume $L_{u}\neq L_{w}\neq L_{v}$.

Suppose that $q(u)=p(u)$ and $q(v)=p(v)$. Then $\|p(u)-p(v)\|=\|q(u)-q(v)\|$
clearly holds, and it remains to show the existence of an isometry
$\gamma\in\mathrm{Isom}(\\{L_{u},L_{v},L_{w}\\})$ as in the statement. If
$q(w)=p(w)$ then this is true (by taking $\gamma=\mathrm{Id}$), so assume
$q(w)\neq p(w)$. Since $M_{G}(q)=M_{G}(p)$ it follows that $L_{w}$ is
perpendicular to the line through $p(u)$ and $p(v)$, which contradicts the
fact that $\mathcal{L}$ is in general position and that $p$ is
$\mathcal{L}$-generic.

Thus, without loss of generality, we can assume that $q(v)\neq p(v)$. Then,
$q(v)=\gamma p(v)$ holds for the non-trivial isometry $\gamma$ of
$\\{L_{v},L_{w}\\}$. In particular $y=(\pi(p(v))+\pi(q(v)))/2$ is the point on
$L_{w}$ that is closest to $L_{v}$. If $q(u)=p(u)$ then it follows from Claim
5.4(b) that $\pi(p(u))=y$, contradicting the fact that $p$ is
$\mathcal{L}$-generic. Therefore $q(u)\neq p(u)$, and hence $q(u)=\tau p(u)$
holds for the non-trivial isometry $\tau$ of $\\{L_{u},L_{w}\\}$. In
particular, $z=(\pi(p(u))+\pi(q(u)))/2$ is the closest point on $L_{w}$ to
$L_{u}$.

Now by Claim 5.4(b) we have $\pi(p(u))-\pi(p(v))=\pm(\pi(q(u))-\pi(q(v)))$. If
$\pi(p(u))-\pi(p(v))=\pi(q(u))-\pi(q(v))$ then

$\pi(p(u))-z=\frac{1}{2}(\pi(p(u))-\pi(q(u)))=\frac{1}{2}(\pi(p(v))-\pi(q(v)))=\pi(p(v))-y.$

However, this contradicts the fact that $p$ is $\mathcal{L}$-generic since the
points $y,z$ have coordinates that lie in $\mathbb{Q}(\mathcal{L})$.

Therefore $\pi(p(u))-\pi(p(v))=-(\pi(q(u))-\pi(q(v)))$ and so $y=z$. Since
$\mathcal{L}$ is in general position (in particular no three lines are weakly
concurrent), this implies that $L_{u}=L_{v}$ and so $\tau=\gamma$ is the non-
trivial isometry of $\\{L_{u},L_{v},L_{w}\\}$. Hence,
$\|p(u)-p(v)\|=\|q(u)-q(v)\|$ follows.

Now suppose that $q(w)\neq\gamma p(w)$. Then it follows that $L_{w}$ is
perpendicular to $L_{u}$ contradicting the fact that $\mathcal{L}$ is in
general position. Therefore $q(x)=\gamma p(x)$ for all $x\in\\{u,v,w\\}$. This
completes the proof. ∎

We are ready to show that global $\mathcal{L}$-rigidity is preserved by
subdivision.

######  Theorem 5.5.

Let $(G,p)$ be an $\mathcal{L}$-generic $\mathcal{L}$-constrained framework
and $w$ be a vertex of degree two. Let $G^{\prime}$ be the graph obtained from
$G$ by smoothing at $w$, and let
$p^{\prime}:\mathcal{V}-w\rightarrow\mathbb{R}^{d}$ be the restriction of $p$.
If $(G^{\prime},p^{\prime})$ is globally $\mathcal{L}$-rigid, then $(G,p)$ is
globally $\mathcal{L}$-rigid.

###### Proof.

Let $u,v$ be the neighbors of $w$ in $G$. By Theorem 4.6, $G$ is redundantly
$\mathcal{L}$-rigid. Since $w$ is degree two in $G$, $G-w$ is
$\mathcal{L}$-rigid and $(G-w,p^{\prime})$ is infinitesimally
$\mathcal{L}$-rigid.

Let $q\in M_{G}^{-1}(M_{G}(p))$. By Lemma 5.3, $\|p(u)-p(v)\|=\|q(u)-q(v)\|$.
Since $(G^{\prime},p^{\prime})$ is globally $\mathcal{L}$-rigid it follows
that $q^{\prime}=\theta p^{\prime}$ for some
$\theta\in\mathrm{Isom}(\mathcal{L}[G-w])$. We split the proof into two cases.

Suppose $\mathrm{Isom}(\mathcal{L}[G])=\mathrm{Isom}(\mathcal{L}[G-w])$. Then
$\theta\in\mathrm{Isom}(\mathcal{L}[G-w])=\mathrm{Isom}(\mathcal{L}[G])$. Now,
replacing $q$ by $\theta^{-1}q$ if necessary, we can assume that
$q^{\prime}=p^{\prime}$. Therefore, since $q\neq p$, $q(w)\neq p(w)$. Now
since $\|p(u)-p(w)\|=\|q(u)-q(w)\|=\|p(u)-q(w)\|$ and similarly
$\|p(v)-p(w)\|=\|p(v)-q(w)\|$, the line through $p(u)$ and $p(v)$ is
perpendicular to $L_{w}$. This contradicts the facts that $\mathcal{L}$ is in
general position and $p$ is $\mathcal{L}$-generic.

Next, suppose that
$\mathrm{Isom}(\mathcal{L}[G])\neq\mathrm{Isom}(\mathcal{L}[G-w])$. $G$ is
P-connected by Theorem 4.6, so $|\mathrm{Isom}(\mathcal{L}[G-w])|\geq 2$. By
Lemma 2.2, we have $|\mathrm{Isom}(\mathcal{L}[G-w])|=2$ and
$|\mathrm{Isom}(\mathcal{L}[G])|=3$. Hence $L_{u}\neq L_{w}\neq L_{v}$
follows. So by Lemma 5.3, there exists
$\gamma\in\mathrm{Isom}(\\{L_{u},L_{v},L_{w}\\})$ such that $q(x)=\gamma p(x)$
for $x\in\\{u,v,w\\}$. If $\theta$ is the identity, then $p(u)=q(u)$ follows,
and hence $\gamma$ is the identity as well. Then $p=q$ follows.

If $\theta$ is not the identity, then $\gamma$ is also not the identity.
Denote $\mathcal{L}[G-w]=\\{L_{1},L_{2}\\}$ and without loss of generality
suppose $L_{u}=L_{1}$. Then $\theta|_{L_{1}}$ is the reflection about the
closest point $y$ to $L_{2}$ while $\gamma|_{L_{1}}$ is the reflection about
the closest point $z$ to $L_{w}$. By $\gamma p(u)=q(u)=\theta p(u)$, $y=z$
follows, contradicting that $L_{1},L_{2},L_{w}$ are not weakly concurrent.
This completes the proof. ∎

Next we prove a gluing property for generic global $\mathcal{L}$-rigidity.

######  Theorem 5.6.

Suppose that $H,K$ are crossing partitioned graphs that are both globally
$\mathcal{L}$-rigid. If $V(H)\cap V(K)$ is non-empty or $|\mathcal{L}[H]|\geq
3$ and $|\mathcal{L}[K]|\geq 3$, then $H\cup K$ is generically globally
$\mathcal{L}$-rigid.

###### Proof.

Suppose $V(H)\cap V(K)$ is non-empty. Choose $u\in V(H)\cap V(K)$. Let
$p,q\in\mathcal{L}^{V(H)\cup V(K)}$ with $p$ $\mathcal{L}$-generic and
$M_{H\cup K}(q)=M_{H\cup K}(p)$. Since $H,K$ are generically globally
$\mathcal{L}$-rigid, it follows that there exist
$\theta\in\mathrm{Isom}(\mathcal{L}[H])$ and
$\gamma\in\mathrm{Isom}(\mathcal{L}[K])$ such that $q(v)=\theta p(v)$ for
$v\in V(H)$ and $q(w)=\gamma p(w)$ for $w\in V(K)$. If $\theta=\mathrm{Id}$
then since $u\in V(H)\cap V(K)$ we see that $\gamma p(u)=q(u)=\theta
p(u)=p(u)$ and since $p$ is generic it follows that $\gamma=\mathrm{Id}$ and
so $q=p$. Similarly if $\gamma=\mathrm{Id}$ then $q=p$. So we can assume that
$\theta,\gamma$ are both non-trivial isometries. Since $\theta p(u)=\gamma
p(u)$, Lemma 2.2 implies that $\mathcal{L}[H]=\mathcal{L}[K]=\mathcal{L}[H\cup
K]$ and that $\theta=\gamma\in\mathrm{Isom}(\mathcal{L}[H\cup K])$ and that
$q=\theta p$.

Suppose $V(H)\cap V(K)$ is empty. Then $|\mathcal{L}[H]|\geq 3$ and
$|\mathcal{L}[K]|\geq 3$ hold, and both $\mathrm{Isom}(\mathcal{L}[H])$ and
$\mathrm{Isom}(\mathcal{L}[K])$ are trivial by Lemma 2.2, and the global
rigidity of $H\cup K$ follows from that of $H$ and $K$. ∎

Note that the hypothesis that both $H$ and $K$ are crossing is required for
Theorem 5.6 to be valid.

##  6 Basic Globally Rigid Graphs

In this section we establish generic global rigidity for certain classes of
graphs which will be used as base cases in an inductive argument for our main
result in the next section. As usual $G$ is a partitioned graph and
$\mathcal{L}$ is in general position. We begin with the case when $G$ is a
triangle.

######  Lemma 6.1.

Suppose that $T=(\mathcal{V},\mathcal{E})$ is the partitioned graph where
$\mathcal{V}$ is the disjoint union of $V_{1}$ and $V_{2}$,
$V_{1}=\\{u,v\\},V_{2}=\\{w\\}$ and $\mathcal{E}=\\{uv,vw,wu\\}$. Let
$p,q\in\mathcal{L}^{\mathcal{V}}$ with $p$ $\mathcal{L}$-generic and suppose
that $M_{T}(q)=M_{T}(p)$. Then $q(w)=\theta p(w)$ for some
$\theta\in\mathrm{Isom}(\mathcal{L}[T])$.

###### Proof.

Let $\pi:\mathbb{R}^{d}\rightarrow L_{u}$ be the orthogonal projection and
observe that, since the triangles $p(u),p(v),p(w)$ and $q(u),q(v),q(w)$ are
congruent and $p(u),p(v),q(u),q(v)\in L_{1}$, we have that
$|q(w)-\pi(q(w))|=|p(w)-\pi(p(w))|$. It follows from Lemma 5.2 that
$q(w)=\theta p(w)$ for some $\theta\in\mathrm{Isom}(\\{L_{w},L_{u}\\})$ as
required. ∎

Next we introduce three basic types of partitioned graphs that will occur in
our inductive argument in the next section. We refer to Figure 4 for
illustrations. A partitioned graph $G$ is of

  * •

type 1 if it is a union of two cycles that have a single vertex $v$ in common,
and, each of the cycles contains a crossing edge that is not incident to $v$.

  * •

type 2 if it is a union of two disjoint cycles $C_{1},C_{2}$ and a simple path
$P$ with endpoints $v_{1},v_{2}$ such that $\\{v_{i}\\}=V(P)\cap
V(C_{i}),i=1,2$, and, such that for $i=1,2$, $C_{i}$ contains a crossing edge
that is not incident to $v_{i}$.

  * •

type 3 if it is a union of a cycle $C$ and a simple path $P$ with endpoints
$v_{1},v_{2}\in V(C)$ such that $V(P)\cap V(C)=\\{v_{1},v_{2}\\}$ and there
are crossing edges $e,f$ such that $e,f$ are not adjacent and so that each
simple path of $C$ joining $v_{1}$ to $v_{2}$ contains one of $e,f$.

|  |
---|---|---
Type 1 | Type 2 | Type 3
Figure 4: The three basic types of graphs. The solid edges are crossing. The
dotted arcs represent simple paths in the graph. In the case of the type 1 or
type 2 graph, all of the dotted paths must have at least one edge. In the case
of the type 3 graph, some of the dotted paths may have length zero as long as
the vertical dotted path in the centre has at least one edge and the two solid
edges are vertex disjoint.

######  Lemma 6.2.

Suppose that $G$ is a type $1$ partitioned graph. Then $G$ is generically
globally $\mathcal{L}$-rigid.

###### Proof.

We prove this by induction on the number of vertices. First observe that a
type 1 partitioned graph has at least 5 vertices. Suppose that
$|\mathcal{V}|=5$. So $\mathcal{V}=\\{v_{1},\dots,v_{5}\\}$ and
$\mathcal{E}=\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{1},v_{3}v_{4},v_{4}v_{5},v_{5}v_{3}\\}$
and note that we can choose the labelling so that
$\\{v_{1},v_{2}\\},\\{v_{1},v_{3}\\},\\{v_{3},v_{4}\\},\\{v_{4},v_{5}\\}$ are
all crossing. Suppose that $p,q\in\mathcal{L}^{\mathcal{V}}$, $p$ is
$\mathcal{L}$-generic and $M_{G}(q)=M_{G}(p)$. By Theorem 3.1,
$(G-v_{1},p|_{\mathcal{V}-v_{1}})$ is infinitesimally $\mathcal{L}$-rigid and
so by Lemma 5.3 we see that there is some isometry $\theta$ of
$\\{L_{v_{1}},L_{v_{2}},L_{v_{3}}\\}$ such that $q(x)=\theta p(x)$ for
$x\in\\{v_{1},v_{2},v_{3}\\}$. Similarly there is some isometry $\gamma$ of
$\\{L_{v_{3}},L_{v_{4}},L_{v_{5}}\\}$ such that $q(x)=\gamma p(x)$ for
$x\in\\{v_{3},v_{4},v_{5}\\}$. Now, if $\theta=\mathrm{Id}$ then
$q(v_{3})=p(v_{3})$ and since $p$ is $\mathcal{L}$-generic, $\gamma$
restricted to $L_{v_{3}}$ is the identity. Hence by Lemma 2.2,
$\gamma=\mathrm{Id}$. Therefore $q=p$ in this case. On the other hand if
$\theta\neq\mathrm{Id}$ then, again using the fact that $p$ is
$\mathcal{L}$-generic it follows that
$\theta|_{L_{v_{3}}}=\gamma|_{L_{v_{3}}}$ and, since $\mathcal{L}$ is in
general position, it follows that
$\\{L_{v_{1}},L_{v_{2}},L_{v_{3}}\\}=\\{L_{v_{3}},L_{v_{4}},L_{v_{5}}\\}$ and
hence that $\gamma=\theta\in\mathrm{Isom}(\mathcal{L}[G])$. Thus $q=\theta p$
for some $\theta\in\mathrm{Isom}(\mathcal{L}[G])$, as required.

Now suppose that $|\mathcal{V}|\geq 6$ and let $e,f$ be crossing edges, one in
each cycle of $G$ that are both not incident with the vertex of degree 4.
Since one of the cycles must have at least 4 vertices, there is some vertex
$w\in\mathcal{V}$ of degree 2 that is not incident to either $e$ or $f$. Then
the graph $G^{\prime}$ obtained from $G$ by smoothing at $w$ is again a type 1
partition graph. By induction, $G^{\prime}$ is generically globally
$\mathcal{L}$-rigid, and, by Theorem 5.5, $G$ is generically globally
$\mathcal{L}$-rigid. ∎

######  Lemma 6.3.

Suppose that $G$ is a type $2$ partitioned graph. Then $G$ is generically
globally $\mathcal{L}$-rigid.

###### Proof.

Again we proceed by induction on $|\mathcal{V}|$. Suppose that
$|\mathcal{V}|=6$ (which is minimal for type 2). Then
$\mathcal{V}=\\{v_{1},\dots,v_{6}\\}$,
$\mathcal{E}=\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{1},v_{4}v_{5},v_{5}v_{6},v_{6}v_{4},v_{1}v_{4}\\}$
and we may choose the labelling so that
$v_{1}v_{2},v_{1}v_{3},v_{4}v_{5},v_{5}v_{6}$ are all crossing edges.

Suppose that $(G,p)$, $(G,q)$ are $\mathcal{L}$-frameworks such that $p$ is
$\mathcal{L}$-generic and $M_{G}(q)=M_{G}(p)$. By Lemma 5.3 there is some
$\theta\in\mathrm{Isom}(\\{L_{v_{1}},L_{v_{2}},L_{v_{3}}\\})$ such that
$q(v_{3})=\theta p(v_{3})$ and some
$\gamma\in\mathrm{Isom}(\\{L_{v_{4}},L_{v_{5}},L_{v_{6}}\\})$ such that
$q(v_{4})=\gamma p(v_{4})$.

Suppose that $\theta p(v_{3})=p(v_{3})$. Then $\theta=\mathrm{Id}$ since $p$
is $\mathcal{L}$-generic. If in addition $\gamma p(v_{4})=p(v_{4})$ then
$\gamma=\mathrm{Id}$ and it follows that $q=p$. On the other hand if $\gamma
p(v_{4})\neq p(v_{4})$ then let $y=(\gamma p(v_{4})+p(v_{4}))/2$. Since $y$ is
a fixed point of $\gamma$ the coordinates of $y$ lie in
$\mathbb{Q}(\mathcal{L})$. However
$\|p(v_{3})-p(v_{4})\|=\|q(v_{3})-q(v_{4})\|=\|p(v_{3})-\gamma p(v_{4})\|$. So
the line joining $p(v_{3})$ and $y$ is perpendicular to $L_{v_{4}}$ which
contradicts the fact that $p$ is $\mathcal{L}$-generic. Hence we have shown
that $\theta p(v_{3})=q(v_{3})\neq p(v_{3})$ and by symmetry $\gamma
p(v_{4})=q(v_{4})\neq p(v_{4})$.

Define $f(x)=\|x-p(v_{3})\|^{2}-\|\gamma\cdot x-q(v_{3})\|^{2}$ for $x\in
L_{v_{4}}$. Observe that $\gamma\cdot x=2z-x$ where $z$ is the unique fixed
point of $\gamma$ in $L_{v_{4}}$ and $q(v_{3})=2w-p(v_{3})$ where $w$ is the
unique fixed point of $\theta$ in $L_{v_{3}}$. It follows that $f$ is a
polynomial function on $L_{v_{4}}$ with coefficients in
$\mathbb{Q}(\mathcal{L})(p(v_{3}))$ (i.e. $\mathbb{Q}(\mathcal{L})$ extended
by the coordinates of $p(v_{3})$). Now
$\|p(v_{4})-p(v_{3})\|=\|q(v_{4})-q(v_{3})\|$ implies $f(p(v_{4}))=0$. Since
$p$ is $\mathcal{L}$-generic, it follows that $f(x)=0$ for all $x\in
L_{v_{4}}$. In particular $f(z)=0$. Therefore $\|z-p(v_{3})\|=\|z-q(v_{3})\|$.
So it follows that either $L_{v_{3}}=L_{v_{4}}$ and $w=z$ or that the segment
$[w,z]$ is perpendicular to $L_{v_{3}}$. In either case, since $\mathcal{L}$
is in general position, it easily follows that
$\theta=\gamma\in\mathrm{Isom}(\mathcal{L}[G])$ and so $q=\theta p$ and so
$(G,p)$ is globally rigid.

The case when $|\mathcal{V}|>6$ can be solved in the same manner as in the
proof of Lemma 6.2 by induction applying Theorem 5.5 at a vertex of degree
two. ∎

######  Lemma 6.4.

Suppose that $G$ is a type $3$ partitioned graph. Then $G$ is generically
globally $\mathcal{L}$-rigid.

###### Proof.

Again we proceed by induction on $|\mathcal{V}|$. First suppose that
$|\mathcal{V}|=4$. Then $\mathcal{V}=\\{u,v,w,x\\}$,
$\mathcal{E}=\\{uv,vw,wx,xu,uw\\}$. By the property of type 3, each of the two
paths $uvw$ and $uxw$ contains a crossing edge. Suppose that
$p,q\in\mathcal{L}^{\mathcal{V}}$ with $p$ $\mathcal{L}$-generic and
$M_{G}(q)=M_{G}(p).$ We split the proof into three cases.

Case 1: $uw$ is not a crossing edge.

In this case $uv,vw,wx,xu$ are all crossing. By Lemma 5.3, there is some
$\theta\in\mathrm{Isom}(\\{L_{u},L_{v}\\})$ such that $q(z)=\theta p(z)$ for
$z\in\\{u,v,w\\}$, and there is some
$\gamma\in\mathrm{Isom}(\\{L_{u},L_{x}\\})$ such that $q(z)=\gamma p(z)$ for
$z\in\\{u,x,w\\}$. Since $\gamma p(u)=q(u)=\theta p(u)$ we have
$\gamma=\theta$. Since $\mathcal{L}$ is in general position, either $\theta$
is the identity or
$\mathrm{Isom}(\\{L_{u},L_{v}\\})=\mathrm{Isom}(\\{L_{u},L_{v},L_{x}\\})=\mathrm{Isom}(\mathcal{L}[G])$
holds by Lemma 2.2. In either case, $q=\theta p$ for some
$\theta\in\mathrm{Isom}(\mathcal{L}[G])$.

Case 2: $uw$ is crossing and $|\mathcal{L}[G]|=2$.

Relabelling if necessary, we can assume that $uv,uw,wx$ are crossing edges and
that $vw,xu$ are not crossing edges. By Lemma 6.1 $q(u)=\theta p(u)$ for some
$\theta\in\mathrm{Isom}\\{L_{u},L_{w}\\}$ and $q(w)=\gamma p(w)$ for some
$\gamma\in\mathrm{Isom}\\{L_{u},L_{w}\\}$. If $\theta$ is the identity, then
we have $\|p(u)-p(w)\|=\|q(u)-q(w)\|=\|p(u)-\gamma p(w)\|$, which implies
$\gamma=\mathrm{Id}=\theta$ due to the $\mathcal{L}$-genericity of $p$. Hence,
since $|\mathrm{Isom}\\{L_{u},L_{w}\\}|=2$ by Lemma 2.2, we can always deduce
$\gamma=\theta$. Moreover $\\{L_{u},L_{w}\\}=\mathcal{L}[G]$, so
$\theta\in\mathrm{Isom}(\mathcal{L}[G])$. Now, replacing $q$ by
$\theta^{-1}q$, we see that $q(u)=p(u)$ and $q(w)=p(w)$. Since $p$ is
$\mathcal{L}$-generic, we know that $L_{v}$ is not perpendicular to
$[p(u),p(w)]$ and so $q(v)=p(v)$. Similarly $q(x)=p(x)$ and so $q=p$.

Case 3: $uw$ is crossing and $|\mathcal{L}[G]|\geq 3$.

Relabelling if necessary we can assume that $uv,vw,uw$ are all crossing edges.
By Lemma 5.3 there is some $\theta\in\mathrm{Isom}(\\{L_{u},L_{v},L_{w}\\})$
such that $q(z)=\theta p(z)$ for $z\in\\{u,v,w\\}$. But $L_{u},L_{v},L_{w}$
are pairwise distinct and so by Lemma 2.2, $\theta=\mathrm{Id}$ and so
$q(z)=p(z)$ for $z\in\\{u,v,w\\}$. Now since $p$ is $\mathcal{L}$-generic,
$[p(u),p(w)]$ is not perpendicular to $L_{x}$ and it follows that $q(x)=p(x)$.
This completes the proof for the case when $\|\mathcal{V}\|=4$.

Now suppose that $|\mathcal{V}|\geq 5$. Let $u,w$ be the vertices of degree
$3$ and let $P_{1},P_{2},P_{3}$ be the three internally vertex disjoint paths
joining $u,v$. Since $G$ is type 3, we may assume that $P_{1}$ contains a
crossing edge $e_{1}$ not incident to $w$ and $P_{2}$ contains a crossing edge
$e_{2}$ not incident to $u$. If $P_{3}$ contains an internal vertex $x$, then
smoothing at $x$ results in a graph of type 3. Hence, by applying the
induction hypothesis and then Theorem 5.5, the generic global
$\mathcal{L}$-rigidity of $G$ follows.

Therefore, we may assume $|V(P_{3})|=2$. Since $|\mathcal{V}|\geq 5$, we may
further suppose $|V(P_{1})|\geq 3$. Let $y$ be a vertex of $P_{1}$, which is
closest from $u$ among those which are not belong to the same vertex component
$V_{i}$ as that of $u$ in the vertex partition. Since $|V(P_{1})|\geq 3$, $y$
has a neighbor $z\notin\\{u,w\\}$. Observe that smoothing at $z$ results in a
graph of type 3. Hence, by applying the induction hypothesis and then Theorem
5.5, the generic global $\mathcal{L}$-rigidity of $G$ follows. ∎

######  Remark 1.

For a given $\mathcal{L}$, we may define the $\mathcal{L}$-rigidity matroid of
$(G,p)$ to be the matroid, with ground set $\mathcal{E}$, in which a set
$E\subset\mathcal{E}$ is independent if the rows of
$R^{\prime}(G,p,\mathcal{L})$ associated with $E$ are linearly independent. It
is clear that the rank function of this matroid is determined by which square
submatrices of $R^{\prime}(G,p,\mathcal{L})$ have vanishing determinant. Thus
we may define the generic line-constrained rigidity matroid to be the
$\mathcal{L}$-rigidity matroid for any set $\mathcal{L}$ of lines in general
position. We note that type 1, 2 or 3 graphs are all circuits in the generic
line-constrained matroid. However, there are circuits that are not type 1, 2,
or 3.

We also note that there are circuits that are not globally rigid, in contrast
to the classical one dimensional rigidity matroid111The (generic)
$d$-dimensional rigidity matroid may be defined similarly to the (generic)
$\mathcal{L}$-rigidity matroid. The difference is that the matroid is the row
matroid of the matrix of coefficients of the linear system in Equation 1
rather than $R^{\prime}(G,p,\mathcal{L})$. in which all circuits are also
globally rigid. For example, the (generic) framework on the left in Figure 2
represents a circuit in the line constrained rigidity matroid which is not
generically globally rigid.

##  7 Characterising Global $\mathcal{L}$-rigidity

In this section we give the main theorem of this paper, a combinatorial
characterisation of generic global $\mathcal{L}$-rigidity. We begin with the
case when $G$ is 2-connected.

######  Lemma 7.1.

Suppose that $G$ is P-connected, $2$-connected and generically redundantly
$\mathcal{L}$-rigid. Then $G$ contains a subgraph of type $3$.

###### Proof.

Suppose, seeking a contradiction, that $G$ satisfies the hypotheses of the
lemma but does not contain a type $3$ subgraph.

######  Claim 7.2.

There are crossing edges $e,f\in E(G)$ that are vertex disjoint.

###### Proof.

Suppose not. Since $G$ is rigid, it has a crossing edge $e$. By redundant
rigidity $G-e$ is rigid, so there is some crossing edge $f\neq e$. By
assumption $e$ and $f$ are not disjoint, so $e=uv$ and $f=vw$ for some
vertices $u,v,w$. Now, by $P$-connectivity, $G-v$ has a crossing edge $g$. If
$g\neq uw$ then two of $e,f,g$ are vertex disjoint contradicting our
assumption. So $g=uw$ is the only crossing edge of $G-v$. Furthermore, if
there is some crossing edge $h\neq e,f$ that is incident to $v$ then $h,g$ are
disjoint crossing edges, contradicting our assumption. It follows that $e$ and
$f$ are the only crossing edges in $G-uw$ and so $G-uw$ has no crossing cycle,
contradicting the assumption that $G-uw$ is rigid. ∎

######  Claim 7.3.

There are crossing edges $e,f$ and cycles $C,D$ so that $e,f$ are vertex
disjoint and $e\in E(C)\setminus E(D)$, $f\in E(D)\setminus E(C)$.

###### Proof.

By Claim 7.2 we can choose vertex disjoint crossing edges $e,f\in\mathcal{E}$.
Since $G$ is 2-connected there are (not necessarily distinct) cycles $C,D$
such that $e\in E(C)$ and $f\in E(D)$. Suppose that one of $C,D$, without loss
of generality $D$, contains both of $e,f$. If $G-\\{e,f\\}$ is connected then
it follows that $G$ has a subgraph of type 3, contradicting our assumption. So
we can assume that $G-\\{e,f\\}$ is not connected.

Now $G-e$ is rigid and so contains a crossing cycle $D^{\prime}$. Since $f$ is
a bridge of $G-e$, $D^{\prime}$ is contained in $G-\\{e,f\\}$. Now
$D^{\prime}$ contains at least two crossing edges,
$f^{\prime},f^{\prime\prime}$ and without loss of generality we can assume
that $f^{\prime}$ and $e$ are vertex disjoint. Then $C\cup D^{\prime}$
contains a cycle $C^{\prime}$ which contains $e$ and avoids $f^{\prime}$, and
$e,f^{\prime},C^{\prime},D^{\prime}$ are the required edges and cycles. ∎

Now we can complete the proof of Lemma 7.1. Let $e,f$ be edges and $C,D$ be
cycles as in the statement of Claim 7.3. Suppose that $e$ is vertex disjoint
from $D$. Since $G$ is 2-connected there are two vertex disjoint paths
$P_{1},P_{2}$ from the endpoints of $e$ to the vertex set of $D$. Since $D$
contains the crossing edge $f$, the graph $P_{1}\cup P_{2}\cup e\cup D$ is a
type 3 graph, contradicting our assumption.

So we may suppose that $e$ is incident to $D$. If $e$ is a chord of $D$ then
since $f$ and $e$ are disjoint, the graph $D\cup e$ is type 3. Otherwise
suppose $e=uv$ with $v\in V(D)$ and $u\not\in V(D)$. Then, since $G$ is
$2$-connected, we can find a path $P$ from $u$ to $D$ that does not contain
$v$. Now $P\cup e\cup D$ is a type 3 graph. Thus in all cases we arrive at a
contradiction.

∎

Now we recall a basic and well-known property of 2-connected graphs. We
include a proof for completeness.

######  Lemma 7.4.

Suppose that $D$ is a $2$-connected graph and that $K$ is a subgraph of $D$
with at least two vertices. There is a sequence of subgraphs
$K_{1},\dots,K_{s}$ of $D$ such that $K_{1}=K$, $K_{s}=D$ and for
$i=1,\dots,s-1$, $K_{i+1}=K_{i}\cup P_{i}$ where $P_{i}$ is a simple path
internally vertex disjoint from $K_{i}$ whose endvertices are distinct and
both lie in $K_{i}$.

###### Proof.

Suppose that we have constructed $K_{1},\dots,K_{j}$ as required and that
$K_{j}\neq D$. If $V(K_{j})=V(D)$ then choose some edge $uv\in E(D)\setminus
E(K_{j})$, let $P_{j}$ be the subgraph of $D$ induced by $\\{u,v\\}$. On the
other hand if $V(K_{j})\neq V(D)$ then since $D$ is connected we can choose an
edge $uv\in E(D)$ such that $u\in V(K_{j})$ and $v\not\in V(K_{j})$. Since
$|V(K_{j})|\geq|V(K)|\geq 2$ and since $D$ is 2-connected there is a path from
$v$ to $V(K_{j})$ that misses $u$. Let $R$ be a path of minimal length from
$v$ to $V(K_{j})$ such that $u\not\in V(R)$ and let $P_{j}=R+u+uv$. Now let
$K_{j+1}=K_{j}\cup P_{j}$ and we can continue in this way until we have
constructed the required sequence. ∎

In the case where $K$ is the graph consisting of a single edge, the sequence
$K_{1},\dots,K_{s}$ is often referred to as an open ear decomposition of $D$.
Hence, we call a path $P_{i}$ given in Lemma 7.4 an open ear of $K_{i}$.

######  Lemma 7.5.

Suppose that $G$ is a crossing partitioned graph and that $\mathcal{L}$ is a
set of lines in general position. If $G$ is P-connected, redundantly
$\mathcal{L}$-rigid and $2$-connected then $G$ is generically globally
$\mathcal{L}$-rigid.

###### Proof.

Let $H$ be the subgraph whose existence is asserted by Lemma 7.1. By Lemmas
6.2, 6.3 and 6.4 $H$ is generically globally $\mathcal{L}$-rigid. Now, by
Lemma 7.4 there is a sequence of graphs $H=G_{1},G_{2},\dots,G_{s}=G$ and for
$i=1,\dots,s-1$ such that $G_{i+1}=G_{i}\cup P_{i}$, where $P_{i}$ is an open
ear of $G_{i}$. Since edge-addition and subdivision preserve generic global
$\mathcal{L}$-rigidity by Theorem 5.5, the addition of an open ear preserves
generic global $\mathcal{L}$-rigidity. Hence $G$ is generically globally
$\mathcal{L}$-rigid. ∎

To deal with partitioned graphs that are not $2$-connected we first review
some basic facts about block decompositions of graphs. A block of a graph $G$
is a subgraph that is either a maximal 2-connected subgraph of $G$, or is a
copy of $K_{2}$ whose edge is a bridge of $G$. Let $B(G)$ be the set of blocks
of $G$ and $C(G)$ be the set of cutvertices of $G$. The block-cutvertex forest
of $G$ is the bipartite forest whose vertex set is $B(G)\cup C(G)$ and whose
edge set is $\\{Dv:D\in B(G),v\in C(G)\cap V(D)\\}$. Clearly the block-
cutvertex forest is a tree if and only if $G$ is connected. A leaf block is a
block that is a leaf of the block-cutvertex forest.

211134111151$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{6}$$D_{7}$ | 12345$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{6}$$D_{7}$
---|---
Figure 5: The graph on the left has cutvertices labelled $1,\cdots,5$ and
blocks labelled $D_{1},\cdots,D_{7}$. The corresponding block-cutvertex forest
is shown on the right. The unique path connecting the blocks $1$ and $7$ is
$D_{1},1,D_{2},2,D_{4},4,D_{6},5,D_{7}$. So $[D_{1},D_{7}]=D_{1}\cup D_{2}\cup
D_{4}\cup D_{6}\cup D_{7}$.

Now suppose that $L$ and $K$ are distinct leaf blocks of a connected graph.
Then there is a unique simple path
$L=D_{1},v_{1},D_{2},\dots,D_{k-1},v_{k-1},D_{k}=K$ in the block-cutvertex
tree. (See Figure 5 for an illustration of these concepts.) Let
$[L,K]=D_{1}\cup\dots\cup D_{k}$.

######  Lemma 7.6.

Suppose that $G$ is connected, P-connected and redundantly rigid and that
$L,K$ are distinct leaf blocks of $G$. Then $[L,K]$ is globally
$\mathcal{L}$-rigid.

###### Proof.

Suppose that $[L,K]=D_{1}\cup\cdots\cup D_{k}$ where $L=D_{1},\dots,D_{k}=K$
are blocks of $G$. Let $v_{i}=V(D_{i})\cap V(D_{i+1})$, $i=1,\dots,k-1$. By
redundant rigidity, $K$ and $L$ are maximal 2-connected subgraphs of $G$.
Since $G$ is P-connected there is a crossing edge $e$ in $L-v_{1}$. Since $L$
is 2-connected, there is a cycle $C_{L}$ in $L$ such that $e\in E(C_{L})$.
Similarly, $K$ has a cycle $C_{K}$ that contains a crossing edge not incident
to $v_{k-1}$.

By the connectivity of $G$, $G$ has a path $P$ with endvertices in $V(C_{L})$
and $V(C_{K})$ such that $P$ is internally disjoint from $C_{L}$ and $C_{K}$.
Let $H=C_{L}\cup C_{K}\cup P$. Then $H$ is a type 1 or type 2 partitioned
graph, and hence it is generically globally $\mathcal{L}$-rigid by Lemmas 6.2
and 6.3.

We now augment $H$ to $[L,K]$ by adding open ears sequentially. Specifically,
for each $i=1,\dots,k-1$, $E(D_{i})\cap E(H)\neq\emptyset$ holds by the
definition of block-cutvertex forests. Hence, by Lemma 7.4, $D_{i}\cap H$ can
be augmented to $D_{i}$ by adding open ears. Therefore, $H$ can be augmented
to $[L,K]$ by adding open ears. Since the addition of an open ear preserves
generic global $\mathcal{L}$-rigidity by Theorem 5.5, the global
$\mathcal{L}$-rigidity of $[L,K]$ follows from that of $H$. ∎

Finally, our main result.

######  Theorem 7.7.

Let $\mathcal{L}$ be a set of lines in general position. A crossing
partitioned graph $G$ is generically globally $\mathcal{L}$-rigid if and only
if $G$ is P-connected and redundantly $\mathcal{L}$-rigid.

###### Proof.

Following Theorem 4.6, it remains to show that if $G$ is P-connected and
redundantly $\mathcal{L}$-rigid then it is generically globally
$\mathcal{L}$-rigid.

If $G$ is 2-connected then Lemma 7.5 gives the required conclusion. If $G$ is
not 2-connected but is connected, then there are leaf blocks $L_{i},K_{i}$,
$i=1,\dots,s$ such that $L_{i}\neq K_{i}$ for $i=1,\dots,s$,
$G=\cup_{i=1}^{s}[L_{i},K_{i}]$ and such that for $i=2,\dots,s$,
$[L_{i},K_{i}]$ shares a block with $[L_{j},K_{j}]$ for some $j<i$. Now an
easy induction argument using Lemma 7.6 and Theorem 5.6 shows that $G$ is
generically globally $\mathcal{L}$-rigid.

If $G$ is not connected, then the $P$-connectivity of $G$ implies that
$|\mathcal{L}[H]|\geq 3$ for each connected component $H$ of $G$. Hence, the
generic global $\mathcal{L}$-rigidity of $G$ follows by applying the induction
hypothesis to each connected component and then applying Theorem 5.6. ∎

######  Corollary 7.8.

Suppose that $(G,p)$ is a generic globally rigid $\mathcal{L}$-framework. Then
$G$ is generically globally $\mathcal{L}$-rigid.

###### Proof.

By Lemma 4.2 and Theorem 4.4, $G$ is P-connected and redundantly
$\mathcal{L}$-rigid. The result follows from Theorem 7.7. ∎

##  8 Concluding Remarks

1\. Theorems 3.1 and 7.7 are good characterisations in the sense that they
lead quickly to efficient deterministic algorithms to check
$\mathcal{L}$-rigidity and global $\mathcal{L}$-rigidity.

2\. It would be natural to consider extensions of our results where lines are
replaced by (two-dimensional) planes. When $\mathcal{L}$ is replaced by a set
of parallel planes then characterising rigidity is a straightforward extension
of the plane case (see e.g. [19, Theorem 5.1]) and global rigidity is
similarly easy. However allowing the planes to be non-parallel, even for
generic planes, opens up substantial difficulties that arise in the standard
bar-joint rigidity model in dimension at least 3. One fundamental such
difficulty is the existence of ‘flexible circuits’ in the $d$-dimensional
rigidity matroid when $d\geq 3$ (see [8, 12] inter alia). Perhaps the simplest
non-trivial flexible circuit that can arise in the context under discussion is
the graph obtained from two copies of $K_{4}$ sharing a single vertex $v$ such
that $v$ is the only vertex on the second plane. Here the natural sparsity
counts would predict rigidity but there is an obvious motion. Similarly,
extending the 2-dimensional global rigidity characterisation of Jackson and
Jordán [11] to non-parallel planes is a challenging open problem.

3\. A related generalisation of our results would be to allow one additional
part in the partition of a partitioned graph, with this part corresponding to
vertices that are not constrained to some line of $\mathcal{L}$. To avoid well
known problems in dimension at least 3, let us restrict to the case when
$d=2$. When both the set of points and the set of lines are generic then
rigidity [23] and global rigidity [9] are understood. When the points are
generic but the lines are allowed to be non-generic then a result of [17]
applies for rigidity. When more than two vertices are allowed on any given
line then, even with generic lines, this seems to be an open but potentially
tractable problem for both rigidity and global rigidity.

4\. It is possible to adapt Theorem 3.1 to apply to ‘circle constrained
frameworks’; here the set of lines is replaced by a set of circles and the
analogue of parallel is concentric. The intuition for this translation is that
the constraint that a point $p(v)$ moves on a circle $C$ at the infinitesimal
level is simply the constraint that $p(v)$ moves on the tangent line to $C$ at
$p(v)$. However this observation does not provide any information about
whether the global rigidity problem is equivalent in the circle constrained
rigidity model. In [9] an equivalence for global rigidity was deduced in
dimension 2 in the special case where the set of points and lines is generic.
It may also be interesting to extend this question to general curves.

### Acknowledgements

This project grew from discussions at the Fields Institute Thematic Program on
Geometric Constraint Systems, Framework Rigidity, and Distance Geometry, and
we are grateful to the organizers for bringing us together. F.M. was partially
supported by the KU Leuven grant iBOF/23/064, the UiT Aurora project MASCOT,
and the FWO grants G0F5921N and G023721N. A.N. was partially supported by
EPSRC grant number EP/W019698/1. S.T. was partially supported by JST PRESTO
Grant Number JPMJPR2126 and JSPS KAKENHI Grant Number 20H05961.

## References

  * [1] L. Asimow and B. Roth, The rigidity of graphs, Transactions of the American Mathematical Society, 245 (1978) 279–289.
  * [2] S. Basu, R. Pollack and M.F. Roy, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, Springer Berlin Heidelberg (2007).
  * [3] J. Bochnak, M. Coste and M. F. Roy, Real algebraic geometry, Vol. 36, Springer Science & Business Media (2013).
  * [4] R. Connelly, T. Jordán, and W. Whiteley, Generic global rigidity of body-bar frameworks, J. Comb. Theory, B, 103 (2013) 689–705.
  * [5] J. Cruickshank, H. Guler, B. Jackson and A. Nixon, Rigidity of linearly constrained frameworks, International Mathematics Research Notices, 2020:12 (2020) 3824–3840.
  * [6] J. Cruickshank, B. Jackson and S. Tanigawa, Global Rigidity of Triangulated Manifolds, arXiv:2204.02503.
  * [7] S. Gortler, A. Healy and D. Thurston, Characterizing generic global rigidity, American Journal of Mathematics, 132:4 (2010) 897–939.
  * [8] G. Grasegger, H. Guler, B. Jackson and A. Nixon, Flexible circuits in the $d$-dimensional rigidity matroid, Journal of Graph Theory, 100:2 (2022) 315–330.
  * [9] H. Guler, B. Jackson and A. Nixon, Global rigidity of 2D linearly constrained frameworks, International Mathematics Research Notices, 22 (2021) 16811–16858.
  * [10] B. Hendrickson, Conditions for unique graph realizations, SIAM Journal of Computing, 21:1 (1992) 65-84.
  * [11] B. Jackson and T. Jordán, Connected Rigidity Matroids and Unique Realisations of Graphs, Journal of Combinatorial Theory, Series B, 94 (2005) 1–29.
  * [12] B. Jackson and T. Jordán, The $d$-dimensional rigidity matroid of sparse graphs, Journal of Combinatorial Theory, Series B, 95 (2005) 118-133.
  * [13] B. Jackson and T. Jordán, Graph Theoretic Techniques in the Analysis of Uniquely Localizable Sensor Networks, In: G. Mao and and B. Fidan (Editors) Localization Algorithms and Strategies for Wireless Sensor Networks, IGI Global, 2009, 146–173.
  * [14] B. Jackson, A. Nixon and S. Tanigawa, An Improved bound for the rigidity of linearly constrained frameworks. SIAM Journal on Discrete Mathematics, 35:2 (2021) 928–933.
  * [15] T. Jordán, C. Kiŕaly and S. Tanigawa, Generic global rigidity of body-hinge frameworks, Journal of Combinatorial Theory, Series B, 117 (2016) 59–76.
  * [16] T. Jordán and W. Whiteley, Global rigidity, Handbook of Discrete and Computational Geometry (third edition), CRC Press (2018), pp. 1661–1694.
  * [17] N. Katoh, and S. Tanigawa, Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries. SIAM Journal on Discrete Mathematics, 27:1 (2013) 155–185.
  * [18] G. Laman, On graphs and rigidity of plane skeletal structures, Journal of Engineering Mathematics, 4 (1970) 331–340.
  * [19] A. Nixon, J.C. Owen, and S.C. Power, Rigidity of frameworks supported on surfaces, SIAM Journal on Discrete Mathematics 26:4 (2012) 1733–1757.
  * [20] J. Saxe, Embeddability of weighted graphs in k-space is strongly NP-hard, In Seventeenth Annual Allerton Conference on Communication, Control, and Computing, Proceedings of the Conference held in Monticello, Ill., October 10-12, 1979.
  * [21] A. Seidenberg, A new decision method for elementary algebra, Annals of Mathematics 2:60 (1954) 365–374.
  * [22] M. Spivak, A comprehensive introduction to differential geometry. Vol. I (second edition). Publish or Perish, Inc., Wilmington, Del. (1979).
  * [23] I. Streinu and L. Theran, Slider-pinning rigidity: a Maxwell-Laman-type theorem, Discrete & Computational Geometry, 44:4 (2010) 812–837.
  * [24] A. Tarski, A Decision Method for Elementary Algebra and Geometry. In: Caviness, B.F., Johnson, J.R. (eds) Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation. Springer, Vienna (1998).

Authors’ addresses:

Mathematics, Statistics & Applied Mathematics, NUI Galway, Ireland
<EMAIL_ADDRESS>
Department of Mathematics and Department of Computer Science, KU Leuven,
Belgium
Department of Mathematics & Statistics, University of Tromsø, Norway
<EMAIL_ADDRESS>
Department of Mathematics, Ghent University, Belgium
<EMAIL_ADDRESS>
Mathematics and Statistics, Lancaster University, Lancaster, UK
<EMAIL_ADDRESS>
Department of Mathematical Informatics, University of Tokyo, Japan
<EMAIL_ADDRESS>


# The dense galactic environments of the Milky Way

Quang Nguyen-Luong1,2,3 Neal Evans4,2 Kee-Tae Kim2 Hyunwoo Kang2 and DEGAMA
survey  1IBM Canada, 120 Bloor Street East, Toronto, ON, M4Y 1B7, Canada,
2Korea Astronomy and Space Science Institute, Yuseoung, Daejeon 34055, Korea,
3Visiting researcher at the Graduate School of Natural Sciences, Nagoya City
University, Japan
4Department of Astronomy, The University of Texas at Austin, 2515 Speedway,
Stop C1400, Austin, TX 78712-1205, USA
email<EMAIL_ADDRESS>
(2019)

###### Abstract

Star formation takes place in the dense gas phase, and therefore a simple
dense gas and star formation rate relation has been proposed. With the advent
of multi-beam receivers, new observations show that the deviation from linear
relations is possible. In addition, different dense gas tracers might also
change significantly the measurement of dense gas mass and subsequently the
relation between star formation rate and dense gas mass. We report the
preliminary results the DEnse GAs in MAssive star-forming regions in the Milky
Way (DEGAMA) survey that observed the dense gas toward a suit of well-
characterized massive star forming regions in the Milky Way. Using the
resulting maps of HCO+ 1–0, HCN 1–0, CS 2–1, we discuss the current
understanding of the dense gas phase where star formation takes place.

###### keywords:

stars: formation, ISM: clouds, ISM: structure, (ISM:) evolution, Galaxy:
evolution

††volume: 345††journal: Origins: from the Protosun to the First Steps of
Life††editors: Bruce G. Elmegreen, L. Viktor Tóth, Manuel Güdel, eds.

##  1 Introduction

We perform a survey of DEnse GAs in MAssive star-forming regions in the Milky
Way (DEGAMA) survey to study the distribution of dense gas in molecular clouds
and its role in forming stars. DEGAMA focusses on a larger sample that is
sensitive to all gas above a column density threshold of 1022 cm-2 with the
goal of improving the understanding of how dense gas is formed and the
relation between dense gas and star formation. The threshold column density of
$N_{\mathrm{H}_{2}}\sim 10^{22}$ cm-2, which might correspond to a volume
density of $1\times 10^{4}$ cm-3, is chosen because this gas directly builds
massive star forming regions and forms lower mass stars (i.e., [Onishi et al.
(1998), Onishi et al. 1998], [André et al. (2010), Andre et al. 2010]).

At the extragalactic scale, we seek to understand the relationship between
stellar density and gas density that was put forward by [Thackeray(1948),
Thackeray (1948)] and [van den Bergh(1957), Van den Bergh (1957)]), and
crystallized in a relationship between the observable surface density of SFR,
$\Sigma_{SFR}$, and the surface density of gas, $\Sigma{{}_{gas}}$, as:
$\Sigma_{SFR}=A~{}\Sigma{{}_{gas}^{N}}$ by [Schmidt(1959), Schmidt (1959)] and
[Kennicutt(1998), Kennicutt (1998)]. However, this relation is not scale-
invariant, the power-law indexes depend on the size scales of the objects, as
pointed out using the diffuse cloud tracer CO 1–0 and radio continuum
luminosity ([nguyen-luong16, Nguyen Luong et al. 2016]). These relationships
may behave differently if one considers only dense gas tracers, as was
suggested for extragalactic environment ([Wu et al.(2010)Wu, Evans, Shirley, &
Knez, Wu et al. 2010], [liu16, Liu et al. 2016]). The linear relationship
manifests in the extragalactic environments ([Gao & Solomon (2004), Gao &
Solomon 2004]) and in the Milky Way environments ([Lada et al.(2012)Lada,
Forbrich, Lombardi, & Alves, Lada et al. 2012]), but significant gaps remain
between extragalactic and galactic star formation laws ([Heiderman et
al.(2010)Heiderman, Evans, Allen, Huard, & Heyer, Heiderman et al. 2010]).
Nevertheless, the linear relationship between dense gas and SFR shows real
scatter in excess of observational uncertainties ([Usero et al.(2015)Usero,
Leroy, Walter, Schruba, García-Burillo, Sandstrom, Bigiel, Brinks, Kramer,
Rosolowsky, Schuster, & de Blok, Usero et al. 2015]), so additional factors
are at work beyond a simple “more dense gas gives more star formation” model.

Figure 1: An overview of HCO+ 1–0 integrated maps of DEGAMA targets.

At the extragalactic scale, we seek to understand the relationship between
stellar density and gas density that was put forward by [Thackeray(1948),
Thackeray (1948)] and [van den Bergh(1957), Van den Bergh (1957)]), and
crystallized in a relationship between the observable surface density of SFR,
$\Sigma_{SFR}$, and the surface density of gas, $\Sigma{{}_{gas}}$, as:
$\Sigma_{SFR}=A~{}\Sigma{{}_{gas}^{N}}$ by [Schmidt(1959), Schmidt (1959)] and
[Kennicutt(1998), Kennicutt (1998)]. However, this relation is not scale-
invariant, the power-law indexes depend on the size scales of the objects, as
pointed out using the diffuse cloud tracer CO 1–0 and radio continuum
luminosity ([nguyen-luong16, Nguyen Luong et al. 2016]). These relationships
may behave differently if one considers only dense gas tracers, as was
suggested for extragalactic environment ([Wu et al.(2010)Wu, Evans, Shirley, &
Knez, Wu et al. 2010], [liu16, Liu et al. 2016]). The linear relationship
manifests in the extragalactic environments ([Gao & Solomon (2004), Gao &
Solomon 2004]) and in the Milky Way environments ([Lada et al.(2012)Lada,
Forbrich, Lombardi, & Alves, Lada et al. 2012]), but significant gaps remain
between extragalactic and galactic star formation laws ([Heiderman et
al.(2010)Heiderman, Evans, Allen, Huard, & Heyer, Heiderman et al. 2010]).
Nevertheless, the linear relationship between dense gas and SFR shows real
scatter in excess of observational uncertainties ([Usero et al.(2015)Usero,
Leroy, Walter, Schruba, García-Burillo, Sandstrom, Bigiel, Brinks, Kramer,
Rosolowsky, Schuster, & de Blok, Usero et al. 2015]), so additional factors
are at work beyond a simple “more dense gas gives more star formation” model.

With a critical density of $\sim 10^{4}$ cm-3, HCO+ 1–0 (89.188 MHz) and HCN
1–0 (88.631 GHz), and CS 2–1 (97.980 GHz) is suitable to trace the total dense
gas component in star forming regions. We observed these lines with the Taeduk
Radio Astronomy Observatory (TRAO) telescope
111https://radio.kasi.re.kr/trao/main_trao.php in the DEGAMA survey and report
its first results in this paper.

##  2 Observations

TRAO was established in October 1986 with the 13.7 meter Radio Telescope and
recently equipped with the 16 pixels 4x4 SEQUOIA receiver. The 2nd IF modules
with the narrow band and the 8 channels with 4 FFT spectrometers allow to
observe 2 frequencies simultaneously within the 85–100 or 100–115 GHz bands
for all 16 pixels of the receiver. We carried out the DEGAMA mapping
observations between December 2016 and December 2017. Observations were done
in OTF mode and the native velocity resolution is less than 0.1 km/sec (15
kHz) per channel, and their full spectra bandwidth is 60 MHz. The telescope
beam size is $\sim 50\mbox{${}^{\prime\prime}$}$ at 100 GHz, and the main-beam
efficiency $\eta_{\rm MB}$ is $\sim 50\%$ at 100 GHz.

Our target is a sample of massive star-forming cloud complexes in the Galaxy
that present the entire massive star forming sequences from quiescent to
active and evolved regions. This sample includes the massive star forming
regions that are rather nearby (d$<5$ kpc), so known star formation rates
measurements from direct YSOs counting with Spitzer/WISE or Herschel. The
sample includes the following sources that can be categorized in evolutionary
stages, from quiescient to more active states: M17, M16, DR21, IRAS05358, W3,
MonOB1, NGC7538, NGC2264, W40, NGC7023 , MonR2, and Mon-OB1.

##  3 Results

From a global perspective, dense gas tracers such as $L_{\rm HCO^{+}}$ or
$L_{\rm HCN}$ and SFR tracers such as $L_{\rm IR}$ or $L_{\rm H_{\alpha}}$ are
believed to correlate well with each other in log-log space ([Gao & Solomon
(2004), Gao & Solomon .2004], [Bussmann et al. (2008), Bussmann et al. 2008],
[Wu et al.(2010)Wu, Evans, Shirley, & Knez, Wu et al. 2010]). The relations,
however, are not identical for different transitions nor for different dense
gas tracers ([Krumholz & Tan(2007), Krumholz & Tan 2007], [Narayanan et
al.(2008)Narayanan, Cox, Shirley, Davé, Hernquist, & Walker, Narayanan 2008],
[Juneau et al.(2009)Juneau, Narayanan, Moustakas, Shirley, Bussmann,
Kennicutt, & Vanden Bout, Juneau et al. 2009]). Moreover, intrinsic variation
in this relationship suggests that simple correlations are inadequate for
capturing the full range of star formation behavior ([Usero et al.(2015)Usero,
Leroy, Walter, Schruba, García-Burillo, Sandstrom, Bigiel, Brinks, Kramer,
Rosolowsky, Schuster, & de Blok, Usero et al. 2015]).

We calculate the integrated line luminosity using equation developed in
[Solomon & Vanden Bout(2005), Solomon & Vanden Bout (2005)] where

$\frac{L^{\prime}_{\rm line}}{{\rm K~{}km/s~{}pc^{2}}}=23.5\times
10^{-6}\times\frac{D}{\rm
kpc}^{2}\times\frac{A}{\rm\mbox{${}^{\prime\prime}$}^{2}}\times\frac{I_{\rm
line}}{\rm K~{}km/s}\,.$ (1)

In DEGAMA survey, integrated line luminosity was derived from a collection of
integrated maps of HCO+ 1–0, HCN 1–0 and CS 2–1. Figure 1 shown an example of
only HCO+ 1–0 maps. The ratio of $L_{\rm HCO^{+}}/L_{\rm HCN}$ from DEGAMA
survey show that HCO+ varies from cloud-to-cloud and vary around the average
extragalactic ratio of 2 (Figure 2a). It might show that although having
similar critical density, HCO+ and HCN might trace quite different types of
dense gas that When plotting on the $L_{\rm TIR}$-$L_{\rm HCN}$ plane, there
is evidence that Galactic clouds do not follow a simple linear relation as the
extragalactic clouds or the scatter is very large (Figure 2b).

Then, we divide the integrated line luminosities into a 100 bins and calculate
the cumulative distributions (CDs) of the integrated line luminosities for
each bin. The results are plotted as functions of luminosity bin in normalized
forms (Figure 3). As the CDs profiles are different for different sources and
different tracers, we model them using a Plummer-like function that describes
flat plateaux and powerlaw decreasing at higher column density as:

$L(>L_{\rm bin})=L_{\rm tot}\left(\frac{L_{\rm cut}}{\sqrt{L_{\rm
cut}^{2}+L_{\rm bin}^{2}}}\right)^{p}~{}~{}~{}.$ (2)

$L_{\rm bin}$ is the luminosity threshold of each bin, $L_{\rm tot}$ is the
total luminosity of the cloud, $L_{\rm cut}$ is where the luminosity profile
changes from power-law shape to flat plateau, and $p$ is the power-law index
of the profile’s section at the high luminosity tail. Figures 3 show that each
cloud can be characterized by parameters $L_{\rm tot}$, $L_{\rm cut}$, ${p}$
from the profile in Equation 2. This differentiation is potential applicable
to differentiate different types of clouds and also its behaviour in different
dense gas tracers. We will explore this topic further in the next paper.

$\begin{array}[]{ccc}\includegraphics[angle={0},height=199.16928pt]{dense1.pdf}&\includegraphics[angle={0},height=199.16928pt]{dense2.pdf}\end{array}$

Figure 2: a: Ratio $L_{\rm HCO^{+}}/L_{\rm HCN}$ as function of $L_{\rm HCN}$
luminosity, the horizontal line indicates where the average ratio $L_{\rm
HCO^{+}}/L_{\rm HCN}=2$. b $L_{\rm TIR}$ as function of $L_{\rm HCN}$ and the
straightline is the linear function $\rm log(L_{\rm TIR})=log(L_{\rm HCN})+3$
([Gao & Solomon (2004), Gao & Solomon 2004], [Wu et al.(2010)Wu, Evans,
Shirley, & Knez, Wu et al. 2010]).

$\begin{array}[]{ccc}\includegraphics[angle={0},width=170.71652pt]{W3_LCMD.pdf}&\includegraphics[angle={0},width=227.62204pt,height=105.2751pt]{all_LCMD_HCOp.pdf}\end{array}$

Figure 3: Normalized cumulative integrated line luminosity distributions of
different tracers (a) and normalized cumulative integrated line luminosity
distributions of HCO+ for different DEGAMA targets (b).

## References

  * [André et al. (2010)] André, P., Men’shchikov, A., Bontemps, S., et al. 2010, A&A, 518, L102+
  * [Bussmann et al. (2008)] Bussmann, R. S., Narayanan, D., Shirley, Y. L., et al. 2008, ApJ, 681, L73
  * [Gao & Solomon (2004)] Gao, Y., & Solomon, P. M. 2004, ApJS, 152, 63
  * [Heiderman et al.(2010)Heiderman, Evans, Allen, Huard, & Heyer] Heiderman, A., Evans, II, N. J., Allen, L. E., Huard, T., & Heyer, M. 2010, ApJ, 723, 1019
  * [Hennemann et al. (2010)] Hennemann, M., Motte, F., Bontemps, S., et al. 2010, A&A, 518, L84+
  * [Hill et al. (2011)] Hill, T., Motte, F., Didelon, P., et al. 2011, A&A, 533, A94
  * [Juneau et al.(2009)Juneau, Narayanan, Moustakas, Shirley, Bussmann, Kennicutt, & Vanden Bout] Juneau, S., Narayanan, D. T., Moustakas, J., et al. 2009, ApJ, 707, 1217
  * [Kennicutt(1998)] Kennicutt, Jr., R. C. 1998, ApJ, 498, 541
  * [Krumholz & Tan(2007)] Krumholz, M. R., & Tan, J. C. 2007, ApJ, 654, 304
  * [Lada et al.(2012)Lada, Forbrich, Lombardi, & Alves] Lada, C. J., Forbrich, J., Lombardi, M., & Alves, J. F. 2012, ApJ, 745, 190
  * [Narayanan et al.(2008)Narayanan, Cox, Shirley, Davé, Hernquist, & Walker] Narayanan, D., Cox, T. J., Shirley, Y., et al. 2008, ApJ, 684, 996
  * [Nguyen Luong et al.(2011)] Nguyen Luong, Q., Motte, F., Hennemann, M., et al. 2011, A&A, 535, A76
  * [Nguyen-Luong et al.(2013)] Nguyen-Luong, Q., Motte, F., Carlhoff, P., et al. 2013, ApJ, 775, 88
  * [Nguyen-Luong et al.(2016)] Nguyen-Luong, Q., Nguyen, Hans V. V., Motte, F., et al. 2016, ApJ, 833, 23
  * [Onishi et al. (1998)] Onishi, T., Mizuno, A., Kawamura, A., Ogawa, H., & Fukui, Y. 1998, ApJ, 502, 296
  * [Peretto et al.(2013)Peretto, Fuller, Duarte-Cabral, Avison, Hennebelle, Pineda, André, Bontemps, Motte, Schneider, & Molinari] Peretto, N., Fuller, G. A., Duarte-Cabral, A., et al. 2013, A&A, 555, A112
  * [Schmidt(1959)] Schmidt, M. 1959, ApJ, 129, 243
  * [Solomon & Vanden Bout(2005)] Solomon, P. M., Vanden Bout, P. A., ARA&A, 43, 677
  * [Schneider et al. (2012)] Schneider, N., Csengeri, T., Hennemann, M., et al. 2012, A&A, 540, L11
  * [Thackeray(1948)] Thackeray, A. D. 1948, The Observatory, 68, 22
  * [Usero et al.(2015)Usero, Leroy, Walter, Schruba, García-Burillo, Sandstrom, Bigiel, Brinks, Kramer, Rosolowsky, Schuster, & de Blok] Usero, A., Leroy, A. K., Walter, F., et al. 2015, ArXiv e-prints, arXiv:1506.00703
  * [van den Bergh(1957)] van den Bergh, S. 1957, ZAp, 43, 236
  * [Wu et al.(2010)Wu, Evans, Shirley, & Knez] Wu, J., Evans, II, N. J., Shirley, Y. L., & Knez, C. 2010, ApJS, 188, 313

Hacar You are comparing line luminosities but line tracers are subject to
excitation, opacity and temperature effects. How do you take into account all
these effects in your comparisons?

Quang The better way is to compare the column density distributions of
different lines if we can have multiple transitions of multiple isotopologue
observations of the same molecules. With only lines at single transitions, we
can only compare them and examine how excitation, opacity and temperature
affect the line luminosity distributions.

Marov In modern cosmology there are theories assuming dark matter properties
with an existence of multiple galaxies around the Milky Way core. Could you
associate dense clouds which you have been talking about with such faint
observing features?

Quang I couldn’t comment on that because there is no observational evidence to
distinguish dark matter properties associated with multiple galaxies in the
Milky Way vicinity.