Graph flattenability

A distance constraint system $(G,\backslash delta)$, where $G=(V,E)$ is a graph and $\backslash delta:\; E\; \backslash rightarrow\; \backslash mathbb\{R\}^$

A graph $G=(V,E)$ is $d$-flattenable in $\backslash 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 connection to Cayley configuration spaces below.

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 flattenable 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.{{cite book|last1=Laurent|first1=Monique|authorlink1=Monique Laurent|last2=Varvitsiotis|first2=Antonios|year=2012|chapter=The Gram Dimension of a Graph|title=Combinatorial Optimization|series=Lecture Notes in Computer Science|volume=7422|pages=356–367|doi=10.1007/978-3-642-32147-4_32|doi-access=free|isbn=978-3-642-32146-7|s2cid=18567150}} The following is an upper-bound on the flattening dimension of an arbitrary graph under the $l\_2$-norm.

Theorem. {{cite journal|last1=Barvinok|first1=A.|authorlink1=Alexander Barvinok|year=1995|title=Problems of distance geometry and convex properties of quadratic maps|journal=Discrete & Computational Geometry|volume=13|issue=2|pages=189–202|doi=10.1007/BF02574037|doi-access=free|s2cid=20628306}} The flattening dimension of a graph $G\; =\; \backslash left(V,E\backslash right)$ under the $l\_2$-norm is at most $O\; \backslash left(\; \backslash sqrt\{\backslash left|\; E\; \backslash right|\}\; \backslash right)$.

For a detailed treatment of this topic, see Chapter 11.2 of Deza & Laurent.{{cite book|last1=Deza|first1=Michel|authorlink1=Michel Deza|title=Geometry of Cuts and Metrics|last2=Laurent|first2=Monique|authorlink2=Monique Laurent|date=1997|publisher=Springer-Verlag Berlin Heidelberg|doi=10.1007/978-3-642-04295-9|doi-access=free|isbn=978-3-540-61611-5}}

This section concerns flattenability results in Euclidean space, where distance is measured using the $l\_2$ norm, also called the Euclidean norm.

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.

File:1-flat.jpg

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$ 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 Belk & Connelly for a detailed explanation.

File:1 flat nonex.jpg

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 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$ 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 $\backslash delta$ on the edges $K\_3$. Note that if $\backslash 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 $\backslash 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 $\backslash delta\_\{13\}$ and $\backslash 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 $\backslash 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.

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\; \backslash times\; C\_2$, but $V\_8$, and $C\_5\; \backslash times\; C\_2$ are 3-flattenable.{{cite journal|last1=Belk|first1=Maria|year=2007|title=Realizability of Graphs in Three Dimensions|journal=Discrete & Computational Geometry|volume=37|issue=2|pages=139–162|doi=10.1007/s00454-006-1285-4|doi-access=free|s2cid=20238879}} 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$ and $K\_\{2,2,2\}$.

File:Partial 3-tree forb min.jpg

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 Belk & Connelly assumes that $V\_8$, and $C\_5\; \backslash 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$ 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 $\backslash 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 $\backslash 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 $\backslash 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.

File:Octahedron embedding.gif

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\; \backslash 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$ 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$, $V\_8$, and $C\_5\; \backslash 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.

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.{{cite journal|last1=Sitharam|first1=Meera|last2=Gao|first2=Heping|year=2010|title=Characterizing Graphs with Convex and Connected Cayley Configuration Spaces|journal=Discrete & Computational Geometry|volume=43|issue=3|pages=594–625|doi=10.1007/s00454-009-9160-8|doi-access=free|s2cid=35819450}} See the section on the connection to Cayley configuration spaces.

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\; \backslash 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 Belk & Connelly. For $d=3$, the algorithm in So & Ye{{cite book|last1=So|first1=Anthony Man-Cho|last2=Ye|first2=Yinyu|title=Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 |chapter=A semidefinite programming approach to tensegrity theory and realizability of graphs |authorlink2=Yinyu Ye|year=2006|pages=766–775|doi=10.1145/1109557.1109641|isbn=0898716055|s2cid=10134807}} obtains a framework $r$ of a DCS using semidefinite programming techniques and then utilizes the "folding" method described in Belk to transform $r$ into a 3-dimensional framework.

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

Determining the flattenability of a graph under a general $p$-norm can be accomplished using methods in algebraic geometry, as suggested in Belk & Connelly. 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\backslash left(nd|V|^2\backslash right)\}$ time.{{cite book|last1=Basu|first1=Saugata|title=Algorithms in Real Algebraic Geometry|last2=Pollack|first2=Richard|authorlink2=Richard M. Pollack|last3=Marie-Francoise|first3=Roy|authorlink3=Marie-Françoise Roy|publisher=Springer, Berlin, Heidelberg|year=2003|chapter=Existential Theory of the Reals|series=Algorithms and Computation in Mathematics|volume=10|doi=10.1007/3-540-33099-2_14|doi-access=free|isbn=978-3-540-33098-1}}

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 Sitharam & Willoughby.

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

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

The $l\_1$ and $l\_\{\backslash 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.{{cite journal|last1=Witsenhausen|first1=Hans S.|year=1986|title=Minimum dimension embedding of finite metric spaces|journal=Journal of Combinatorial Theory|series=Series A|volume=42|issue=2|pages=184–199|doi=10.1016/0097-3165(86)90089-0|doi-access=}} These facts contribute to the following results on 2-flattenability under the $l\_1$-norm found in Sitharam & Willoughby.

Observation. The set of 2-flattenable graphs under the $l\_1$-norm (and $l\_\{\backslash 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. {{Cite journal|last1=Fiorini|first1=Samuel|last2=Huynh|first2=Tony|last3=Joret|first3=Gwenaël|last4=Varvitsiotis|first4=Antonios|date=2017-01-01|title=The Excluded Minors for Isometric Realizability in the Plane|url=https://epubs.siam.org/doi/10.1137/16M1064775|journal=SIAM Journal on Discrete Mathematics|volume=31|issue=1|pages=438–453|doi=10.1137/16M1064775|arxiv=1511.08054|hdl=10356/81454|s2cid=2579286|issn=0895-4801}} A graph is 2-flattenable under the $l\_1$- or $l\_\{\backslash 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.

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 $\backslash 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 Ball.{{cite journal|last1=Ball|first1=Keith|authorlink1=Keith Martin Ball|year=1990|title=Isometric Embedding in lp-spaces|journal=European Journal of Combinatorics|volume=11|issue=4|pages=305–311|doi=10.1016/S0195-6698(13)80131-X|doi-access=free}} The $d$-stratum of this cone $\backslash Phi^d\_\{n,l\_p\}$ are the vectors that can be realized as a configuration of $n$ points in $d$-dimensions. The projection of $\backslash Phi\_\{n,l\_p\}$ or $\backslash Phi^d\_\{n,l\_p\}$ 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,\backslash 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 $\backslash Omega$ of $\backslash delta$ in the interior of the cone $\backslash Phi\_\{n,l\_p\}$, and
2. the framework is $d$-flattenable if and only if all frameworks in $\backslash Omega$ are $d$-flattenable.

Condition (1) ensures that the neighborhood $\backslash Omega$ has full rank. In other words, $\backslash Omega$ has dimension equal to the flattening dimension of the complete graph $K\_n$ under the $l\_p$-norm. See Kitson{{cite journal|last1=Kitson|first1=Derek|year=2015|title=Finite and Infinitesimal Rigidity with Polyhedral Norms|journal=Discrete & Computational Geometry|volume=54|issue=2|pages=390–411|doi=10.1007/s00454-015-9706-x|doi-access=free|s2cid=15520982|arxiv=1401.1336}} for a more detailed discussion of generic framework for $l\_p$-norms. The following results are found in Sitharam & Willoughby.

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 $\backslash Phi^d\_\{n,l\_p\}$ 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 $\backslash Phi^d\_\{n,l\_p\}$ 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 $\backslash Phi^d\_\{n,l\_p\}$ 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 $\backslash Phi^d\_\{n,l\_p\}$ onto the edges of $G$ is strictly less than the minimum of the dimension of $\backslash Phi^d\_\{n,l\_p\}$ and the number of edges of $G$.

{{Authority control}}

Category:Graph theory

Category:Mathematics of rigidity