Graph flattenability explained

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,^[1] but the name was changed to avoid confusion with a graph having some DCS with a d -dimensional framework.^[2]

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 → R ^{|E|} is an assignment of distances onto the edges of G , is d -flattenable in some normed vector space R ^{d} if there exists a framework of (G,\delta) in d -dimensions.

A graph

G = (V,E) is d -flattenable in 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.

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.^[3] The following is an upper-bound on the flattening dimension of an arbitrary graph under the l _{2} -norm.

Theorem. ^[4] 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 Deza & Laurent.^[5]

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.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.

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 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 \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.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} x C _{2} , but V _{8} , and C _{5} x C _{2} are 3-flattenable.^[6] 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} .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} x 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 \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.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} x 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} x 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.

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.^[7] 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 , 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 Belk & Connelly. For d =3 , the algorithm in So & Ye^[8] 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.

Flattenability under p-norms

This section concerns flattenability results for graphs under general

p -norms, for

1 \leq p \leq inf ty .

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 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\left(nd|V| ^{2\right)}} time.^[9]

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

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.^[10] 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 _{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. ^[11] 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 Ball.^[12] The d -stratum of this cone \Phi ^{d} _{n,l _{p}} 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 ^{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,\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

1. 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 Kitson^[13] 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 \Phi ^{d} _{n,l _{p}} onto the edges of G has dimension equal to the number of edges of G ;

1. maximally independent in the generic

d -dimensional rigidity matroid if and only if projecting the d -stratum \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 ;

1. rigid in

d -dimensions if and only if projecting the d -stratum \Phi ^{d} _{n,l _{p}} onto the edges of G preserves its dimension;

1. not independent in the generic

d -dimensional rigidity matroid if and only if the dimension of the projection of the d -stratum \Phi ^{d} _{n,l _{p}} onto the edges of G is strictly less than the minimum of the dimension of \Phi ^{d} _{n,l _{p}} and the number of edges of G .

References

1. Belk. Maria. Connelly. Robert. Robert Connelly. 2007. Realizability of Graphs. Discrete & Computational Geometry. 37. 2. 125–137. 10.1007/s00454-006-1284-5. free. 12755057.
2. Book: Sitharam. M.. Willoughby. J.. 2014. On Flattenability of Graphs. Automated Deduction in Geometry. Lecture Notes in Computer Science. 9201. 129–148. 10.1007/978-3-319-21362-0_9. 978-3-319-21361-3. 23208.
3. Book: Laurent. Monique. Monique Laurent. Varvitsiotis. Antonios. 2012. The Gram Dimension of a Graph. Combinatorial Optimization. Lecture Notes in Computer Science. 7422. 356–367. 10.1007/978-3-642-32147-4_32. free. 978-3-642-32146-7. 18567150.
4. Barvinok. A.. Alexander Barvinok. 1995. Problems of distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry. 13. 2. 189–202. 10.1007/BF02574037. free. 20628306.
5. Book: Deza. Michel. Michel Deza. Geometry of Cuts and Metrics. Laurent. Monique. Monique Laurent. 1997. Springer-Verlag Berlin Heidelberg. 10.1007/978-3-642-04295-9. free. 978-3-540-61611-5.
6. Belk. Maria. 2007. Realizability of Graphs in Three Dimensions. Discrete & Computational Geometry. 37. 2. 139–162. 10.1007/s00454-006-1285-4. free. 20238879.
7. Sitharam. Meera. Gao. Heping. 2010. Characterizing Graphs with Convex and Connected Cayley Configuration Spaces. Discrete & Computational Geometry. 43. 3. 594–625. 10.1007/s00454-009-9160-8. free. 35819450.
8. Book: So. Anthony Man-Cho. Ye. Yinyu. Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 . A semidefinite programming approach to tensegrity theory and realizability of graphs . Yinyu Ye. 2006. 766–775. 10.1145/1109557.1109641. 0898716055. 10134807.
9. Book: Basu. Saugata. Algorithms in Real Algebraic Geometry. Pollack. Richard. Richard M. Pollack. Marie-Francoise. Roy. Marie-Françoise Roy. Springer, Berlin, Heidelberg. 2003. Existential Theory of the Reals. Algorithms and Computation in Mathematics. 10. 10.1007/3-540-33099-2_14. free. 978-3-540-33098-1.
10. Witsenhausen. Hans S.. 1986. Minimum dimension embedding of finite metric spaces. Journal of Combinatorial Theory. Series A. 42. 2. 184–199. 10.1016/0097-3165(86)90089-0.
11. Fiorini. Samuel. Huynh. Tony. Joret. Gwenaël. Varvitsiotis. Antonios. 2017-01-01. The Excluded Minors for Isometric Realizability in the Plane. SIAM Journal on Discrete Mathematics. 31. 1. 438–453. 10.1137/16M1064775. 1511.08054. 10356/81454. 2579286. 0895-4801.
12. Ball. Keith. Keith Martin Ball. 1990. Isometric Embedding in lp-spaces. European Journal of Combinatorics. 11. 4. 305–311. 10.1016/S0195-6698(13)80131-X. free.
13. Kitson. Derek. 2015. Finite and Infinitesimal Rigidity with Polyhedral Norms. Discrete & Computational Geometry. 54. 2. 390–411. 10.1007/s00454-015-9706-x. free. 15520982. 1401.1336.