Graph flattenability

Flattenability in some $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'$ can be "flattened" down to live in $d$-dimensions, such that the distances between pairs of points connected by edges are preserved. A graph $G$ is $d$-flattenable if every distance constraint system (DCS) with $G$ as its constraint graph has a $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$-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,\delta )$, where $G=(V,E)$ is a graph and $\delta :E\rightarrow \mathbb {R} ^{|E|}$ is an assignment of distances onto the edges of $G$, is $d$-flattenable in some normed vector space $\mathbb {R} ^{d}$ if there exists a framework of $(G,\delta )$ in $d$-dimensions.

A graph $G=(V,E)$ is $d$-flattenable in $\mathbb {R} ^{d}$ if every distance constraint system with $G$ as its constraint graph is $d$-flattenable.

Flattenability can also be defined in terms of Cayley configuration spaces, see below connection to Cayley Configuration Spaces.

Properties

Closure under subgraphs. Flattenability is closed under taking subgraphs. To see this, observe that for some graph $G$, all possible embeddings of a subgraph $H$ of $G$ are contained in the set of all embeddings of $G$.

Minor-closed. Flattenability is a minor-closed property by a similar argument as above.

Flattening-Dimension. The flattening dimension of a graph $G$ in some normed vector space is the lowest dimension $d$ such that $G$ is $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}$-norm.

Theorem. The flattening dimension of a graph $G=\left(V,E\right)$ under the $l_{2}$-norm is at most $O\left({\sqrt {\left|E\right|}}\right)$.

For a detailed treatment of this topic, see Chapter 11.2 of.

Euclidean flattenability

This section concerns flattenability results in Euclidean space, where distance is measured using the $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}$.

Theorem. A graph is 1-flattenable if and only if it is a forest.

Figure 1. A $2$-dimensional framework of a DCS whose graph is a tree with six vertices is shown in blue. A $1$-dimensional framework of the same DCS is shown in red.

Proof. A proof can be found in. 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$ is not a forest, then it has the complete graph $K_{3}$ as a subgraph. Consider the DCS that assigns the distance $1$ to the edges of the $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 for a detailed explanation.

Figure 2. For certain linkages, this graph has a 1-dimensional realization (e.g. the assignment of 1 to every edge). However, $C_{3}$ can be obtained by contracting the edge ${\bar {AB}}$, so the graph is not $1$-flattenable.

2-Flattenable graphs

The following theorem is folklore and shows that the only forbidden minor for $2$-flattenability is the complete graph $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. 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$ vertices can be constructed recursively by taking a 2-tree with $n-1$ vertices and connecting a new vertex to the vertices of an existing edge. The base case is the $K_{3}$. Proceed by induction on the number of vertices $n$. When $n=3$, consider any distance assignment $\delta$ on the edges $K_{3}$. Note that if $\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}$ at the origin and the second vertex $v_{2}$ along the x-axis such that $\delta _{12}$ is satisfied. The third vertex $v_{3}$ can be placed at an intersection of the circles with centers $v_{1}$ and $v_{2}$ and radii $\delta _{13}$ and $\delta _{23}$ respectively. This method of placement is called a ruler and compass construction. Hence, $K_{3}$ is 2-flattenable.

Now, assume a 2-tree with $k$ vertices is 2-flattenable. By definition, a 2-tree with $k+1$ vertices is a 2-tree with $k$ vertices, say $T$, and an additional vertex $u$ connected to the vertices of an existing edge in $T$. By the inductive hypothesis, $T$ is 2-flattenable. Finally, by a similar ruler and compass construction argument as in the base case, $u$ can be placed such that it lies in the plane. Thus, 2-trees are 2-flattenable by induction.

If a graph $G$ is not a partial 2-tree, then it contains $K_{4}$ as a minor. Assigning the distance of $1$ to the edges of the $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 ${\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}$ contains $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}$, the 1-skeleton of the octahedron $K_{2,2,2}$, $V_{8}$, and $C_{5}\times C_{2}$, but $V_{8}$, and $C_{5}\times C_{2}$ are $3$-flattenable. These graphs are shown in Figure 3. Furthermore, the following theorem from shows that the only forbidden minors for $3$-flattenability are $K_{5}$ and $K_{2,2,2}$.

Figure 3. The graphs of interest for $3$-flattenability.

Theorem. A graph is $3$-flattenable if and only if it does not have $K_{5}$ or $K_{2,2,2}$ as a minor.

Proof Idea: The proof given in assumes that $V_{8}$, and $C_{5}\times C_{2}$ are $3$-realizable. This is proven in using mathematical tools from rigidity theory, specifically those concerning tensegrities. The complete graph $K_{5}$ is not $3$-flattenable, and the same argument that shows $K_{4}$ is not $2$-flattenable and $K_{3}$ is not $1$-flattenable works here: assigning the distance $1$ to the edges of $K_{5}$ yields a DCS with no realization in $3$-dimensions. Figure 4 gives a visual proof that the graph $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)$ and $(3,4)$ are assigned the distance ${\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 $\Pi$ defined by vertices $1$, $2$, and $4$. Hence, the edge $(5,6)$ has two distance values that can be realized in $3$-dimensions. However, vertex $6$ can revolve around the plane $\Pi$ in $4$-dimensions while satisfying all constraints, so the edge $(5,6)$ has infinitely many distance values that can only be realized in $4$-dimensions or higher. Thus, $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}$ or $K_{2,2,2}$ as a minor is not $3$-flattenable.

Figure 4. Construction steps to show the $1$-skeleton of an octahedron is not $3$-flattenable.

The other direction shows that if a graph $G$ does not have $K_{5}$ or $K_{2,2,2}$ as a minor, then $G$ can be constructed from partial $3$-trees, $V_{8}$, and $C_{5}\times C_{2}$ via [[Clique-sum}|$1$-sums]], $2$-sums, and $3$-sums. These graphs are all $3$-flattenable and these operations preserve $3$-flattenability, so $G$ is $3$-flattenable.

The techniques in this proof yield the following result from.

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}$, $V_{8}$, and $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}$, which is the 1-skeleton of a tetrahedron. On each face of the tetrahedron, perform a 3-sum with another $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.

Flattenability in higher dimensions

Giving a forbidden minor characterization of $d$-flattenable graphs, for dimension $d>3$, is an open problem. For any dimension $d$, $K_{d+2}$ and the 1-skeleton of the $d$-dimensional analogue of an octahedron are forbidden minors for $d$-flattenability. It is conjectured that the number of forbidden minors for $d$-flattenability grows asymptotically to the number of forbidden minors for partial $d$-trees, and there are over $75$ forbidden minors for partial $4$-trees.

An alternative characterization of $d$-flattenable graphs relates flattenability to Cayley configuration spaces. See the section Connection to Cayley Configuration Spaces.

Connection to the Graph Realization Problem

Given a distance constraint system and a dimension $d$, the Graph Realization Problem asks for a $d$-dimensional framework of the DCS, if one exists. There are algorithms to realize $d$-flattenable graphs in $d$-dimensions, for $d\leq 3$, that run in polynomial time in the size of the graph. For $d=1$, realizing each tree in a forest in $1$-dimension is trivial to accomplish in polynomial time. An algorithm for $d=2$ is mentioned in. For $d=3$, the algorithm in obtains a framework $r$ of a DCS using semidefinite programming techniques and then utilizes the "folding" method described in to transform $r$ into a $3$-dimensional framework.

Flattenability under p-norms

This section concerns flattenability results for graphs under general $p$-norms, for $1\leq p\leq \infty$.

Connection to algebraic geometry

Determining the flattenability of a graph under a general $p$-norm can be accomplished using methods in algebraic geometry, as suggested in. The question of whether a graph $G=(V,E)$ is $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\left(nd|V|^{2}\right)}$ time.

Connection to Cayley configuration spaces

For general $l_{p}$-norms, there is a close relationship between flattenability and Cayley configuration spaces. The following theorem and its corollary are found in.

Theorem. A graph $G$ is $d$-flattenable if and only if for every subgraph $H=G\setminus F$ of $G$ resulting from removing a set of edges $F$ from $G$ and any $l_{p}^{p}$-distance vector $\delta _{H}$ such that the DCS $(H,\delta _{H})$ has a realization, the $d$-dimensional Cayley configuration space of $(H,\delta _{H})$ over $F$ is convex.

Corollary. A graph $G$ is not $d$-flattenable if there exists some subgraph $H=G\setminus F$ of $G$ and some $l_{p}^{p}$-distance vector $\delta$ such that the $d$-dimensional Cayley configuration space of $(H,\delta _{H})$ over $F$ is not convex.

2-Flattenability under the l₁ and l_∞ norms

The $l_{1}$ and $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}$-norm. The complete graph $K_{4}$ is $2$-flattenable under the $l_{1}$-norm and $K_{5}$ is $3$-flattenable, but not $2$-flattenable. These facts contribute to the following results on $2$-flattenability under the $l_{1}$-norm found in.

Observation. The set of $2$-flattenable graphs under the $l_{1}$-norm (and $l_{\infty }$-norm) strictly contains the set of $2$-flattenable graphs under the $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}$ minor.

The fact that $K_{4}$ is $2$-flattenable but $K_{5}$ is not has implications on the forbidden minor characterization for $2$-flattenable graphs under the $l_{1}$-norm. Specifically, the minors of $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}$ 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}$ is $2$-flattenable.

Observation. Connected graphs on $5$ vertices with $7$ edges are $2$-flattenable.

The only minor of $K_{5}$ left is the wheel graph $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}$- or $l_{\infty }$-norm if and only if it does not have either of the following graphs as minors:

• the wheel graph $W_{5}$ or
• the graph obtained by taking the $2$-sum of two copies of $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}$-distance cone $\Phi _{n,l_{p}}$, i.e., the set of all $l_{p}^{p}$-distance vectors that can be realized as a configuration of $n$ points in some dimension. A proof that this set is a cone can be found in. The $d$-stratum of this cone $\Phi _{n,l_{p}}^{d}$ are the vectors that can be realized as a configuration of $n$ points in $d$-dimensions. The projection of $\Phi _{n,l_{p}}$ or $\Phi _{n,l_{p}}^{d}$ onto the edges of a graph $G$ is the set of $l_{p}^{p}$ distance vectors that can be realized as the edge-lengths of some embedding of $G$.

A generic property of a graph $G$ is one that almost all frameworks of distance constraint systems, whose graph is $G$, have. A framework of a DCS $(G,\delta )$ under an $l_{p}$-norm is a generic framework (with respect to $d$-flattenability) if the following two conditions hold:

1. there is an open neighborhood $\Omega$ of $\delta$ in the interior of the cone $\Phi _{n,l_{p}}$, and
2. the framework is $d$-flattenable if and only if all frameworks in $\Omega$ are $d$-flattenable.

Condition (1) ensures that the neighborhood $\Omega$ has full rank. In other words, $\Omega$ has dimension equal to the flattening dimension of the complete graph $K_{n}$ under the $l_{p}$-norm. See for a more detailed discussion of generic framework for $l_{p}$-norms. The following results are found in.

Theorem. A graph $G$ is $d$-flattenable if and only if every generic framework of $G$ is $d$-flattenable.

Theorem. $d$-flattenability is not a generic property of graphs, even for the $l_{2}$-norm.

Theorem. A generic $d$-flattenable framework of a graph $G$ exists if and only if $G$ is independent in the generic $d$-dimensional rigidity matroid.

Corollary. A graph $G$ is $d$-flattenable only if $G$ is independent in the $d$-dimensional rigidity matroid.

Theorem. For general $l_{p}$-norms, a graph $G$ is

1. independent in the generic $d$-dimensional rigidity matroid if and only if the projection of the $d$-stratum $\Phi _{n,l_{p}}^{d}$ onto the edges of $G$ has dimension equal to the number of edges of $G$;
2. maximally independent in the generic $d$-dimensional rigidity matroid if and only if projecting the $d$-stratum $\Phi _{n,l_{p}}^{d}$ onto the edges of $G$ preserves its dimension and this dimension is equal to the number of edges of $G$;
3. rigid in $d$-dimensions if and only if projecting the $d$-stratum $\Phi _{n,l_{p}}^{d}$ onto the edges of $G$ preserves its dimension;
4. not independent in the generic $d$-dimensional rigidity matroid if and only if the dimension of the projection of the $d$-stratum $\Phi _{n,l_{p}}^{d}$ onto the edges of $G$ is strictly less than the minimum of the dimension of $\Phi _{n,l_{p}}^{d}$ and the number of edges of $G$.