- Source: Graph flattenability
Flattenability in some
d
{\displaystyle d}
-dimensional normed vector space is a property of graphs which states that any embedding, or drawing, of the graph in some high dimension
d
′
{\displaystyle d'}
can be "flattened" down to live in
d
{\displaystyle d}
-dimensions, such that the distances between pairs of points connected by edges are preserved. A graph
G
{\displaystyle G}
is
d
{\displaystyle d}
-flattenable if every distance constraint system (DCS) with
G
{\displaystyle G}
as its constraint graph has a
d
{\displaystyle d}
-dimensional framework. Flattenability was first called realizability, but the name was changed to avoid confusion with a graph having some DCS with a
d
{\displaystyle d}
-dimensional framework.
Flattenability has connections to structural rigidity, tensegrities, Cayley configuration spaces, and a variant of the graph realization problem.
Definitions
A distance constraint system
(
G
,
δ
)
{\displaystyle (G,\delta )}
, where
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
is a graph and
δ
:
E
→
R
|
E
|
{\displaystyle \delta :E\rightarrow \mathbb {R} ^{|E|}}
is an assignment of distances onto the edges of
G
{\displaystyle G}
, is
d
{\displaystyle d}
-flattenable in some normed vector space
R
d
{\displaystyle \mathbb {R} ^{d}}
if there exists a framework of
(
G
,
δ
)
{\displaystyle (G,\delta )}
in
d
{\displaystyle d}
-dimensions.
A graph
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
is
d
{\displaystyle d}
-flattenable in
R
d
{\displaystyle \mathbb {R} ^{d}}
if every distance constraint system with
G
{\displaystyle G}
as its constraint graph is
d
{\displaystyle d}
-flattenable.
Flattenability can also be defined in terms of Cayley configuration spaces; see connection to Cayley configuration spaces below.
Properties
Closure under subgraphs. Flattenability is closed under taking subgraphs. To see this, observe that for some graph
G
{\displaystyle G}
, all possible embeddings of a subgraph
H
{\displaystyle H}
of
G
{\displaystyle G}
are contained in the set of all embeddings of
G
{\displaystyle G}
.
Minor-closed. Flattenability is a minor-closed property by a similar argument as above.
Flattening dimension. The flattening dimension of a graph
G
{\displaystyle G}
in some normed vector space is the lowest dimension
d
{\displaystyle d}
such that
G
{\displaystyle G}
is
d
{\displaystyle d}
-flattenable. The flattening dimension of a graph is closely related to its gram dimension. The following is an upper-bound on the flattening dimension of an arbitrary graph under the
l
2
{\displaystyle l_{2}}
-norm.
Theorem. The flattening dimension of a graph
G
=
(
V
,
E
)
{\displaystyle G=\left(V,E\right)}
under the
l
2
{\displaystyle l_{2}}
-norm is at most
O
(
|
E
|
)
{\displaystyle O\left({\sqrt {\left|E\right|}}\right)}
.
For a detailed treatment of this topic, see Chapter 11.2 of Deza & Laurent.
Euclidean flattenability
This section concerns flattenability results in Euclidean space, where distance is measured using the
l
2
{\displaystyle l_{2}}
norm, also called the Euclidean norm.
= 1-flattenable graphs
=The following theorem is folklore and shows that the only forbidden minor for 1-flattenability is the complete graph
K
3
{\displaystyle K_{3}}
.
Theorem. A graph is 1-flattenable if and only if it is a forest.
Proof. A proof can be found in Belk & Connelly. For one direction, a forest is a collection of trees, and any distance constraint system whose graph is a tree can be realized in 1-dimension. For the other direction, if a graph
G
{\displaystyle G}
is not a forest, then it has the complete graph
K
3
{\displaystyle K_{3}}
as a subgraph. Consider the DCS that assigns the distance 1 to the edges of the
K
4
{\displaystyle K_{4}}
subgraph and the distance 0 to all other edges. This DCS has a realization in 2-dimensions as the 1-skeleton of a triangle, but it has no realization in 1-dimension.
This proof allowed for distances on edges to be 0, but the argument holds even when this is not allowed. See Belk & Connelly for a detailed explanation.
= 2-flattenable graphs
=The following theorem is folklore and shows that the only forbidden minor for 2-flattenability is the complete graph
K
4
{\displaystyle K_{4}}
.
Theorem. A graph is 2-flattenable if and only if it is a partial 2-tree.
Proof. A proof can be found in Belk & Connelly. For one direction, since flattenability is closed under taking subgraphs, it is sufficient to show that 2-trees are 2-flattenable. A 2-tree with
n
{\displaystyle n}
vertices can be constructed recursively by taking a 2-tree with
n
−
1
{\displaystyle n-1}
vertices and connecting a new vertex to the vertices of an existing edge. The base case is the
K
3
{\displaystyle K_{3}}
. Proceed by induction on the number of vertices
n
{\displaystyle n}
. When
n
=
3
{\displaystyle n=3}
, consider any distance assignment
δ
{\displaystyle \delta }
on the edges
K
3
{\displaystyle K_{3}}
. Note that if
δ
{\displaystyle \delta }
does not obey the triangle inequality, then this DCS does not have a realization in any dimension. Without loss of generality, place the first vertex
v
1
{\displaystyle v_{1}}
at the origin and the second vertex
v
2
{\displaystyle v_{2}}
along the x-axis such that
δ
12
{\displaystyle \delta _{12}}
is satisfied. The third vertex
v
3
{\displaystyle v_{3}}
can be placed at an intersection of the circles with centers
v
1
{\displaystyle v_{1}}
and
v
2
{\displaystyle v_{2}}
and radii
δ
13
{\displaystyle \delta _{13}}
and
δ
23
{\displaystyle \delta _{23}}
respectively. This method of placement is called a ruler and compass construction. Hence,
K
3
{\displaystyle K_{3}}
is 2-flattenable.
Now, assume a 2-tree with
k
{\displaystyle k}
vertices is 2-flattenable. By definition, a 2-tree with
k
+
1
{\displaystyle k+1}
vertices is a 2-tree with
k
{\displaystyle k}
vertices, say
T
{\displaystyle T}
, and an additional vertex
u
{\displaystyle u}
connected to the vertices of an existing edge in
T
{\displaystyle T}
. By the inductive hypothesis,
T
{\displaystyle T}
is 2-flattenable. Finally, by a similar ruler and compass construction argument as in the base case,
u
{\displaystyle u}
can be placed such that it lies in the plane. Thus, 2-trees are 2-flattenable by induction.
If a graph
G
{\displaystyle G}
is not a partial 2-tree, then it contains
K
4
{\displaystyle K_{4}}
as a minor. Assigning the distance of 1 to the edges of the
K
4
{\displaystyle K_{4}}
minor and the distance of 0 to all other edges yields a DCS with a realization in 3-dimensions as the 1-skeleton of a tetrahedra. However, this DCS has no realization in 2-dimensions: when attempting to place the fourth vertex using a ruler and compass construction, the three circles defined by the fourth vertex do not all intersect.
Example. Consider the graph in figure 2. Adding the edge
A
C
¯
{\displaystyle {\bar {AC}}}
turns it into a 2-tree; hence, it is a partial 2-tree. Thus, it is 2-flattenable.
Example. The wheel graph
W
5
{\displaystyle W_{5}}
contains
K
4
{\displaystyle K_{4}}
as a minor. Thus, it is not 2-flattenable.
= 3-flattenable graphs
=The class of 3-flattenable graphs strictly contains the class of partial 3-trees. More precisely, the forbidden minors for partial 3-trees are the complete graph
K
5
{\displaystyle K_{5}}
, the 1-skeleton of the octahedron
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
,
V
8
{\displaystyle V_{8}}
, and
C
5
×
C
2
{\displaystyle C_{5}\times C_{2}}
, but
V
8
{\displaystyle V_{8}}
, and
C
5
×
C
2
{\displaystyle C_{5}\times C_{2}}
are 3-flattenable. These graphs are shown in Figure 3. Furthermore, the following theorem from Belk & Connelly shows that the only forbidden minors for 3-flattenability are
K
5
{\displaystyle K_{5}}
and
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
.
Theorem. A graph is 3-flattenable if and only if it does not have
K
5
{\displaystyle K_{5}}
or
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
as a minor.
Proof Idea: The proof given in Belk & Connelly assumes that
V
8
{\displaystyle V_{8}}
, and
C
5
×
C
2
{\displaystyle C_{5}\times C_{2}}
are 3-realizable. This is proven in the same article using mathematical tools from rigidity theory, specifically those concerning tensegrities. The complete graph
K
5
{\displaystyle K_{5}}
is not 3-flattenable, and the same argument that shows
K
4
{\displaystyle K_{4}}
is not 2-flattenable and
K
3
{\displaystyle K_{3}}
is not 1-flattenable works here: assigning the distance 1 to the edges of
K
5
{\displaystyle K_{5}}
yields a DCS with no realization in 3-dimensions. Figure 4 gives a visual proof that the graph
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
is not 3-flattenable. Vertices 1, 2, and 3 form a degenerate triangle. For the edges between vertices 1- 5, edges
(
1
,
4
)
{\displaystyle (1,4)}
and
(
3
,
4
)
{\displaystyle (3,4)}
are assigned the distance
2
{\displaystyle {\sqrt {2}}}
and all other edges are assigned the distance 1. Vertices 1- 5 have unique placements in 3-dimensions, up to congruence. Vertex 6 has 2 possible placements in 3-dimensions: 1 on each side of the plane
Π
{\displaystyle \Pi }
defined by vertices 1, 2, and 4. Hence, the edge
(
5
,
6
)
{\displaystyle (5,6)}
has two distance values that can be realized in 3-dimensions. However, vertex 6 can revolve around the plane
Π
{\displaystyle \Pi }
in 4-dimensions while satisfying all constraints, so the edge
(
5
,
6
)
{\displaystyle (5,6)}
has infinitely many distance values that can only be realized in 4-dimensions or higher. Thus,
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
is not 3-flattenable. The fact that these graphs are not 3-flattenable proves that any graph with either
K
5
{\displaystyle K_{5}}
or
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
as a minor is not 3-flattenable.
The other direction shows that if a graph
G
{\displaystyle G}
does not have
K
5
{\displaystyle K_{5}}
or
K
2
,
2
,
2
{\displaystyle K_{2,2,2}}
as a minor, then
G
{\displaystyle G}
can be constructed from partial 3-trees,
V
8
{\displaystyle V_{8}}
, and
C
5
×
C
2
{\displaystyle C_{5}\times C_{2}}
via 1-sums, 2-sums, and 3-sums. These graphs are all 3-flattenable and these operations preserve 3-flattenability, so
G
{\displaystyle G}
is 3-flattenable.
The techniques in this proof yield the following result from Belk & Connelly.
Theorem. Every 3-realizable graph is a subgraph of a graph that can be obtained by a sequence of 1-sums, 2-sums, and 3-sums of the graphs
K
4
{\displaystyle K_{4}}
,
V
8
{\displaystyle V_{8}}
, and
C
5
×
C
2
{\displaystyle C_{5}\times C_{2}}
.
Example. The previous theorem can be applied to show that the 1-skeleton of a cube is 3-flattenable. Start with the graph
K
4
{\displaystyle K_{4}}
, which is the 1-skeleton of a tetrahedron. On each face of the tetrahedron, perform a 3-sum with another
K
4
{\displaystyle K_{4}}
graph, i.e. glue two tetrahedra together on their faces. The resulting graph contains the cube as a subgraph and is 3-flattenable.
= In higher dimensions
=Giving a forbidden minor characterization of
d
{\displaystyle d}
-flattenable graphs, for dimension
d
>
3
{\displaystyle d>3}
, is an open problem. For any dimension
d
{\displaystyle d}
,
K
d
+
2
{\displaystyle K_{d+2}}
and the 1-skeleton of the
d
{\displaystyle d}
-dimensional analogue of an octahedron are forbidden minors for
d
{\displaystyle d}
-flattenability. It is conjectured that the number of forbidden minors for
d
{\displaystyle d}
-flattenability grows asymptotically to the number of forbidden minors for partial
d
{\displaystyle d}
-trees, and there are over
75
{\displaystyle 75}
forbidden minors for partial 4-trees.
An alternative characterization of
d
{\displaystyle d}
-flattenable graphs relates flattenability to Cayley configuration spaces. See the section on the connection to Cayley configuration spaces.
= Connection to the graph realization problem
=Given a distance constraint system and a dimension
d
{\displaystyle d}
, the graph realization problem asks for a
d
{\displaystyle d}
-dimensional framework of the DCS, if one exists. There are algorithms to realize
d
{\displaystyle d}
-flattenable graphs in
d
{\displaystyle d}
-dimensions, for
d
≤
3
{\displaystyle d\leq 3}
, that run in polynomial time in the size of the graph. For
d
=
1
{\displaystyle d=1}
, realizing each tree in a forest in 1-dimension is trivial to accomplish in polynomial time. An algorithm for
d
=
2
{\displaystyle d=2}
is mentioned in Belk & Connelly. For
d
=
3
{\displaystyle d=3}
, the algorithm in So & Ye obtains a framework
r
{\displaystyle r}
of a DCS using semidefinite programming techniques and then utilizes the "folding" method described in Belk to transform
r
{\displaystyle r}
into a 3-dimensional framework.
Flattenability under p-norms
This section concerns flattenability results for graphs under general
p
{\displaystyle p}
-norms, for
1
≤
p
≤
∞
{\displaystyle 1\leq p\leq \infty }
.
= Connection to algebraic geometry
=Determining the flattenability of a graph under a general
p
{\displaystyle p}
-norm can be accomplished using methods in algebraic geometry, as suggested in Belk & Connelly. The question of whether a graph
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
is
d
{\displaystyle d}
-flattenable is equivalent to determining if two semi-algebraic sets are equal. One algorithm to compare two semi-algebraic sets takes
(
4
|
E
|
)
O
(
n
d
|
V
|
2
)
{\displaystyle (4|E|)^{O\left(nd|V|^{2}\right)}}
time.
= Connection to Cayley configuration spaces
=For general
l
p
{\displaystyle l_{p}}
-norms, there is a close relationship between flattenability and Cayley configuration spaces. The following theorem and its corollary are found in Sitharam & Willoughby.
Theorem. A graph
G
{\displaystyle G}
is
d
{\displaystyle d}
-flattenable if and only if for every subgraph
H
=
G
∖
F
{\displaystyle H=G\setminus F}
of
G
{\displaystyle G}
resulting from removing a set of edges
F
{\displaystyle F}
from
G
{\displaystyle G}
and any
l
p
p
{\displaystyle l_{p}^{p}}
-distance vector
δ
H
{\displaystyle \delta _{H}}
such that the DCS
(
H
,
δ
H
)
{\displaystyle (H,\delta _{H})}
has a realization, the
d
{\displaystyle d}
-dimensional Cayley configuration space of
(
H
,
δ
H
)
{\displaystyle (H,\delta _{H})}
over
F
{\displaystyle F}
is convex.
Corollary. A graph
G
{\displaystyle G}
is not
d
{\displaystyle d}
-flattenable if there exists some subgraph
H
=
G
∖
F
{\displaystyle H=G\setminus F}
of
G
{\displaystyle G}
and some
l
p
p
{\displaystyle l_{p}^{p}}
-distance vector
δ
{\displaystyle \delta }
such that the
d
{\displaystyle d}
-dimensional Cayley configuration space of
(
H
,
δ
H
)
{\displaystyle (H,\delta _{H})}
over
F
{\displaystyle F}
is not convex.
= 2-Flattenability under the l1 and l∞ norms
=The
l
1
{\displaystyle l_{1}}
and
l
∞
{\displaystyle l_{\infty }}
norms are equivalent up to rotating axes in 2-dimensions, so 2-flattenability results for either norm hold for both. This section uses the
l
1
{\displaystyle l_{1}}
-norm. The complete graph
K
4
{\displaystyle K_{4}}
is 2-flattenable under the
l
1
{\displaystyle l_{1}}
-norm and
K
5
{\displaystyle K_{5}}
is 3-flattenable, but not 2-flattenable. These facts contribute to the following results on 2-flattenability under the
l
1
{\displaystyle l_{1}}
-norm found in Sitharam & Willoughby.
Observation. The set of 2-flattenable graphs under the
l
1
{\displaystyle l_{1}}
-norm (and
l
∞
{\displaystyle l_{\infty }}
-norm) strictly contains the set of 2-flattenable graphs under the
l
2
{\displaystyle l_{2}}
-norm.
Theorem. A 2-sum of 2-flattenable graphs is 2-flattenable if and only if at most one graph has a
K
4
{\displaystyle K_{4}}
minor.
The fact that
K
4
{\displaystyle K_{4}}
is 2-flattenable but
K
5
{\displaystyle K_{5}}
is not has implications on the forbidden minor characterization for 2-flattenable graphs under the
l
1
{\displaystyle l_{1}}
-norm. Specifically, the minors of
K
5
{\displaystyle K_{5}}
could be forbidden minors for 2-flattenability. The following results explore these possibilities and give the complete set of forbidden minors.
Theorem. The banana graph, or
K
5
{\displaystyle K_{5}}
with one edge removed, is not 2-flattenable.
Observation. The graph obtained by removing two edges that are incident to the same vertex from
K
5
{\displaystyle K_{5}}
is 2-flattenable.
Observation. Connected graphs on 5 vertices with 7 edges are 2-flattenable.
The only minor of
K
5
{\displaystyle K_{5}}
left is the wheel graph
W
5
{\displaystyle W_{5}}
, and the following result shows that this is one of the forbidden minors.
Theorem. A graph is 2-flattenable under the
l
1
{\displaystyle l_{1}}
- or
l
∞
{\displaystyle l_{\infty }}
-norm if and only if it does not have either of the following graphs as minors:
the wheel graph
W
5
{\displaystyle W_{5}}
or
the graph obtained by taking the 2-sum of two copies of
K
4
{\displaystyle K_{4}}
and removing the shared edge.
= Connection to structural rigidity
=This section relates flattenability to concepts in structural (combinatorial) rigidity theory, such as the rigidity matroid. The following results concern the
l
p
p
{\displaystyle l_{p}^{p}}
-distance cone
Φ
n
,
l
p
{\displaystyle \Phi _{n,l_{p}}}
, i.e., the set of all
l
p
p
{\displaystyle l_{p}^{p}}
-distance vectors that can be realized as a configuration of
n
{\displaystyle n}
points in some dimension. A proof that this set is a cone can be found in Ball. The
d
{\displaystyle d}
-stratum of this cone
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
are the vectors that can be realized as a configuration of
n
{\displaystyle n}
points in
d
{\displaystyle d}
-dimensions. The projection of
Φ
n
,
l
p
{\displaystyle \Phi _{n,l_{p}}}
or
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
onto the edges of a graph
G
{\displaystyle G}
is the set of
l
p
p
{\displaystyle l_{p}^{p}}
distance vectors that can be realized as the edge-lengths of some embedding of
G
{\displaystyle G}
.
A generic property of a graph
G
{\displaystyle G}
is one that almost all frameworks of distance constraint systems, whose graph is
G
{\displaystyle G}
, have. A framework of a DCS
(
G
,
δ
)
{\displaystyle (G,\delta )}
under an
l
p
{\displaystyle l_{p}}
-norm is a generic framework (with respect to
d
{\displaystyle d}
-flattenability) if the following two conditions hold:
there is an open neighborhood
Ω
{\displaystyle \Omega }
of
δ
{\displaystyle \delta }
in the interior of the cone
Φ
n
,
l
p
{\displaystyle \Phi _{n,l_{p}}}
, and
the framework is
d
{\displaystyle d}
-flattenable if and only if all frameworks in
Ω
{\displaystyle \Omega }
are
d
{\displaystyle d}
-flattenable.
Condition (1) ensures that the neighborhood
Ω
{\displaystyle \Omega }
has full rank. In other words,
Ω
{\displaystyle \Omega }
has dimension equal to the flattening dimension of the complete graph
K
n
{\displaystyle K_{n}}
under the
l
p
{\displaystyle l_{p}}
-norm. See Kitson for a more detailed discussion of generic framework for
l
p
{\displaystyle l_{p}}
-norms. The following results are found in Sitharam & Willoughby.
Theorem. A graph
G
{\displaystyle G}
is
d
{\displaystyle d}
-flattenable if and only if every generic framework of
G
{\displaystyle G}
is
d
{\displaystyle d}
-flattenable.
Theorem.
d
{\displaystyle d}
-flattenability is not a generic property of graphs, even for the
l
2
{\displaystyle l_{2}}
-norm.
Theorem. A generic
d
{\displaystyle d}
-flattenable framework of a graph
G
{\displaystyle G}
exists if and only if
G
{\displaystyle G}
is independent in the generic
d
{\displaystyle d}
-dimensional rigidity matroid.
Corollary. A graph
G
{\displaystyle G}
is
d
{\displaystyle d}
-flattenable only if
G
{\displaystyle G}
is independent in the
d
{\displaystyle d}
-dimensional rigidity matroid.
Theorem. For general
l
p
{\displaystyle l_{p}}
-norms, a graph
G
{\displaystyle G}
is
independent in the generic
d
{\displaystyle d}
-dimensional rigidity matroid if and only if the projection of the
d
{\displaystyle d}
-stratum
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
onto the edges of
G
{\displaystyle G}
has dimension equal to the number of edges of
G
{\displaystyle G}
;
maximally independent in the generic
d
{\displaystyle d}
-dimensional rigidity matroid if and only if projecting the
d
{\displaystyle d}
-stratum
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
onto the edges of
G
{\displaystyle G}
preserves its dimension and this dimension is equal to the number of edges of
G
{\displaystyle G}
;
rigid in
d
{\displaystyle d}
-dimensions if and only if projecting the
d
{\displaystyle d}
-stratum
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
onto the edges of
G
{\displaystyle G}
preserves its dimension;
not independent in the generic
d
{\displaystyle d}
-dimensional rigidity matroid if and only if the dimension of the projection of the
d
{\displaystyle d}
-stratum
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
onto the edges of
G
{\displaystyle G}
is strictly less than the minimum of the dimension of
Φ
n
,
l
p
d
{\displaystyle \Phi _{n,l_{p}}^{d}}
and the number of edges of
G
{\displaystyle G}
.
References
Kata Kunci Pencarian:
- Graph flattenability
- Hypergraph
- Graph of desire
- Leiden algorithm
- Cayley configuration space
- Yo-yo problem
- Pooling layer
- Icosian calculus
- Duck curve
- Zocchihedron