Graph flattenability
Flattenability in some -dimensional normed vector space is a property of graphs which states that any embedding, or drawing, of the graph in some high dimension can be "flattened" down to live in -dimensions, such that the distances between pairs of points connected by edges are preserved. A graph is -flattenable if every distance constraint system (DCS) with as its constraint graph has a -dimensional framework. Flattenability was first called realizability,[1] but the name was changed to avoid confusion with a graph having some DCS with a -dimensional framework.[2]
Flattenability has connections to structural rigidity, tensegrities, Cayley configuration spaces, and a variant of the graph realization problem.
Definitions
[edit]A distance constraint system , where is a graph and is an assignment of distances onto the edges of , is -flattenable in some normed vector space if there exists a framework of in -dimensions.
A graph is -flattenable in if every distance constraint system with as its constraint graph is -flattenable.
Flattenability can also be defined in terms of Cayley configuration spaces; see connection to Cayley configuration spaces below.
Properties
[edit]Closure under subgraphs. Flattenability is closed under taking subgraphs.[1] To see this, observe that for some graph , all possible embeddings of a subgraph of are contained in the set of all embeddings of .
Minor-closed. Flattenability is a minor-closed property by a similar argument as above.[1]
Flattening dimension. The flattening dimension of a graph in some normed vector space is the lowest dimension such that is -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 -norm.
Theorem. [4] The flattening dimension of a graph under the -norm is at most .
For a detailed treatment of this topic, see Chapter 11.2 of Deza & Laurent.[5]
Euclidean flattenability
[edit]This section concerns flattenability results in Euclidean space, where distance is measured using the norm, also called the Euclidean norm.
1-flattenable graphs
[edit]The following theorem is folklore and shows that the only forbidden minor for 1-flattenability is the complete graph .
Theorem. A graph is 1-flattenable if and only if it is a forest.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/1-flat.jpg/440px-1-flat.jpg)
Proof. A proof can be found in Belk & Connelly.[1] 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 is not a forest, then it has the complete graph as a subgraph. Consider the DCS that assigns the distance 1 to the edges of the 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[1] for a detailed explanation.
![](http://upload.wikimedia.org/wikipedia/commons/3/3d/1_flat_nonex.jpg)
2-flattenable graphs
[edit]The following theorem is folklore and shows that the only forbidden minor for 2-flattenability is the complete graph .
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.[1] 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 vertices can be constructed recursively by taking a 2-tree with vertices and connecting a new vertex to the vertices of an existing edge. The base case is the . Proceed by induction on the number of vertices . When , consider any distance assignment on the edges . Note that if 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 at the origin and the second vertex along the x-axis such that is satisfied. The third vertex can be placed at an intersection of the circles with centers and and radii and respectively. This method of placement is called a ruler and compass construction. Hence, is 2-flattenable.
Now, assume a 2-tree with vertices is 2-flattenable. By definition, a 2-tree with vertices is a 2-tree with vertices, say , and an additional vertex connected to the vertices of an existing edge in . By the inductive hypothesis, is 2-flattenable. Finally, by a similar ruler and compass construction argument as in the base case, can be placed such that it lies in the plane. Thus, 2-trees are 2-flattenable by induction.
If a graph is not a partial 2-tree, then it contains as a minor. Assigning the distance of 1 to the edges of the 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 turns it into a 2-tree; hence, it is a partial 2-tree. Thus, it is 2-flattenable.
Example. The wheel graph contains as a minor. Thus, it is not 2-flattenable.
3-flattenable graphs
[edit]The class of 3-flattenable graphs strictly contains the class of partial 3-trees.[1] More precisely, the forbidden minors for partial 3-trees are the complete graph , the 1-skeleton of the octahedron , , and , but , and are 3-flattenable.[6] These graphs are shown in Figure 3. Furthermore, the following theorem from Belk & Connelly[1] shows that the only forbidden minors for 3-flattenability are and .
![](http://upload.wikimedia.org/wikipedia/commons/2/2e/Partial_3-tree_forb_min.jpg)
Theorem. [1] A graph is 3-flattenable if and only if it does not have or as a minor.
Proof Idea: The proof given in Belk & Connelly[1] assumes that , and are 3-realizable. This is proven in the same article using mathematical tools from rigidity theory, specifically those concerning tensegrities. The complete graph is not 3-flattenable, and the same argument that shows is not 2-flattenable and is not 1-flattenable works here: assigning the distance 1 to the edges of yields a DCS with no realization in 3-dimensions. Figure 4 gives a visual proof that the graph is not 3-flattenable. Vertices 1, 2, and 3 form a degenerate triangle. For the edges between vertices 1- 5, edges and are assigned the distance 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 defined by vertices 1, 2, and 4. Hence, the edge has two distance values that can be realized in 3-dimensions. However, vertex 6 can revolve around the plane in 4-dimensions while satisfying all constraints, so the edge has infinitely many distance values that can only be realized in 4-dimensions or higher. Thus, is not 3-flattenable. The fact that these graphs are not 3-flattenable proves that any graph with either or as a minor is not 3-flattenable.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Octahedron_embedding.gif/330px-Octahedron_embedding.gif)
The other direction shows that if a graph does not have or as a minor, then can be constructed from partial 3-trees, , and via 1-sums, 2-sums, and 3-sums. These graphs are all 3-flattenable and these operations preserve 3-flattenability, so is 3-flattenable.
The techniques in this proof yield the following result from Belk & Connelly.[1]
Theorem. [1] 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 , , and .
Example. The previous theorem can be applied to show that the 1-skeleton of a cube is 3-flattenable. Start with the graph , which is the 1-skeleton of a tetrahedron. On each face of the tetrahedron, perform a 3-sum with another 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
[edit]Giving a forbidden minor characterization of -flattenable graphs, for dimension , is an open problem. For any dimension , and the 1-skeleton of the -dimensional analogue of an octahedron are forbidden minors for -flattenability.[1] It is conjectured that the number of forbidden minors for -flattenability grows asymptotically to the number of forbidden minors for partial -trees, and there are over forbidden minors for partial 4-trees.[1]
An alternative characterization of -flattenable graphs relates flattenability to Cayley configuration spaces.[2][7] See the section on the connection to Cayley configuration spaces.
Connection to the graph realization problem
[edit]Given a distance constraint system and a dimension , the graph realization problem asks for a -dimensional framework of the DCS, if one exists. There are algorithms to realize -flattenable graphs in -dimensions, for , that run in polynomial time in the size of the graph. For , realizing each tree in a forest in 1-dimension is trivial to accomplish in polynomial time. An algorithm for is mentioned in Belk & Connelly.[1] For , the algorithm in So & Ye[8] obtains a framework of a DCS using semidefinite programming techniques and then utilizes the "folding" method described in Belk[6] to transform into a 3-dimensional framework.
Flattenability under p-norms
[edit]This section concerns flattenability results for graphs under general -norms, for .
Connection to algebraic geometry
[edit]Determining the flattenability of a graph under a general -norm can be accomplished using methods in algebraic geometry, as suggested in Belk & Connelly.[1] The question of whether a graph is -flattenable is equivalent to determining if two semi-algebraic sets are equal. One algorithm to compare two semi-algebraic sets takes time.[9]
Connection to Cayley configuration spaces
[edit]For general -norms, there is a close relationship between flattenability and Cayley configuration spaces.[2][7] The following theorem and its corollary are found in Sitharam & Willoughby.[2]
Theorem. [2] A graph is -flattenable if and only if for every subgraph of resulting from removing a set of edges from and any -distance vector such that the DCS has a realization, the -dimensional Cayley configuration space of over is convex.
Corollary. A graph is not -flattenable if there exists some subgraph of and some -distance vector such that the -dimensional Cayley configuration space of over is not convex.
2-Flattenability under the l1 and l∞ norms
[edit]The and norms are equivalent up to rotating axes in 2-dimensions,[5] so 2-flattenability results for either norm hold for both. This section uses the -norm. The complete graph is 2-flattenable under the -norm and is 3-flattenable, but not 2-flattenable.[10] These facts contribute to the following results on 2-flattenability under the -norm found in Sitharam & Willoughby.[2]
Observation. [2] The set of 2-flattenable graphs under the -norm (and -norm) strictly contains the set of 2-flattenable graphs under the -norm.
Theorem. [2] A 2-sum of 2-flattenable graphs is 2-flattenable if and only if at most one graph has a minor.
The fact that is 2-flattenable but is not has implications on the forbidden minor characterization for 2-flattenable graphs under the -norm. Specifically, the minors of could be forbidden minors for 2-flattenability. The following results explore these possibilities and give the complete set of forbidden minors.
Theorem. [2] The banana graph, or with one edge removed, is not 2-flattenable.
Observation. [2] The graph obtained by removing two edges that are incident to the same vertex from is 2-flattenable.
Observation. [2] Connected graphs on 5 vertices with 7 edges are 2-flattenable.
The only minor of left is the wheel graph , and the following result shows that this is one of the forbidden minors.
Theorem. [11] A graph is 2-flattenable under the - or -norm if and only if it does not have either of the following graphs as minors:
- the wheel graph or
- the graph obtained by taking the 2-sum of two copies of and removing the shared edge.
Connection to structural rigidity
[edit]This section relates flattenability to concepts in structural (combinatorial) rigidity theory, such as the rigidity matroid. The following results concern the -distance cone , i.e., the set of all -distance vectors that can be realized as a configuration of points in some dimension. A proof that this set is a cone can be found in Ball.[12] The -stratum of this cone are the vectors that can be realized as a configuration of points in -dimensions. The projection of or onto the edges of a graph is the set of distance vectors that can be realized as the edge-lengths of some embedding of .
A generic property of a graph is one that almost all frameworks of distance constraint systems, whose graph is , have. A framework of a DCS under an -norm is a generic framework (with respect to -flattenability) if the following two conditions hold:
- there is an open neighborhood of in the interior of the cone , and
- the framework is -flattenable if and only if all frameworks in are -flattenable.
Condition (1) ensures that the neighborhood has full rank. In other words, has dimension equal to the flattening dimension of the complete graph under the -norm. See Kitson[13] for a more detailed discussion of generic framework for -norms. The following results are found in Sitharam & Willoughby.[2]
Theorem. [2] A graph is -flattenable if and only if every generic framework of is -flattenable.
Theorem. [2] -flattenability is not a generic property of graphs, even for the -norm.
Theorem. [2] A generic -flattenable framework of a graph exists if and only if is independent in the generic -dimensional rigidity matroid.
Corollary. [2] A graph is -flattenable only if is independent in the -dimensional rigidity matroid.
Theorem. [2] For general -norms, a graph is
- independent in the generic -dimensional rigidity matroid if and only if the projection of the -stratum onto the edges of has dimension equal to the number of edges of ;
- maximally independent in the generic -dimensional rigidity matroid if and only if projecting the -stratum onto the edges of preserves its dimension and this dimension is equal to the number of edges of ;
- rigid in -dimensions if and only if projecting the -stratum onto the edges of preserves its dimension;
- not independent in the generic -dimensional rigidity matroid if and only if the dimension of the projection of the -stratum onto the edges of is strictly less than the minimum of the dimension of and the number of edges of .
References
[edit]- ^ a b c d e f g h i j k l m n o p q Belk, Maria; Connelly, Robert (2007). "Realizability of Graphs". Discrete & Computational Geometry. 37 (2): 125–137. doi:10.1007/s00454-006-1284-5. S2CID 12755057.
- ^ a b c d e f g h i j k l m n o p q Sitharam, M.; Willoughby, J. (2014). "On Flattenability of Graphs". Automated Deduction in Geometry. Lecture Notes in Computer Science. 9201: 129–148. doi:10.1007/978-3-319-21362-0_9. ISBN 978-3-319-21361-3. S2CID 23208.
- ^ Laurent, Monique; Varvitsiotis, Antonios (2012). "The Gram Dimension of a Graph". Combinatorial Optimization. Lecture Notes in Computer Science. Vol. 7422. pp. 356–367. doi:10.1007/978-3-642-32147-4_32. ISBN 978-3-642-32146-7. S2CID 18567150.
- ^ Barvinok, A. (1995). "Problems of distance geometry and convex properties of quadratic maps". Discrete & Computational Geometry. 13 (2): 189–202. doi:10.1007/BF02574037. S2CID 20628306.
- ^ a b Deza, Michel; Laurent, Monique (1997). Geometry of Cuts and Metrics. Springer-Verlag Berlin Heidelberg. doi:10.1007/978-3-642-04295-9. ISBN 978-3-540-61611-5.
- ^ a b Belk, Maria (2007). "Realizability of Graphs in Three Dimensions". Discrete & Computational Geometry. 37 (2): 139–162. doi:10.1007/s00454-006-1285-4. S2CID 20238879.
- ^ a b Sitharam, Meera; Gao, Heping (2010). "Characterizing Graphs with Convex and Connected Cayley Configuration Spaces". Discrete & Computational Geometry. 43 (3): 594–625. doi:10.1007/s00454-009-9160-8. S2CID 35819450.
- ^ So, Anthony Man-Cho; Ye, Yinyu (2006). "A semidefinite programming approach to tensegrity theory and realizability of graphs". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. pp. 766–775. doi:10.1145/1109557.1109641. ISBN 0898716055. S2CID 10134807.
- ^ Basu, Saugata; Pollack, Richard; Marie-Francoise, Roy (2003). "Existential Theory of the Reals". Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Vol. 10. Springer, Berlin, Heidelberg. doi:10.1007/3-540-33099-2_14. ISBN 978-3-540-33098-1.
- ^ Witsenhausen, Hans S. (1986). "Minimum dimension embedding of finite metric spaces". Journal of Combinatorial Theory. Series A. 42 (2): 184–199. doi:10.1016/0097-3165(86)90089-0.
- ^ 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. arXiv:1511.08054. doi:10.1137/16M1064775. hdl:10356/81454. ISSN 0895-4801. S2CID 2579286.
- ^ Ball, Keith (1990). "Isometric Embedding in lp-spaces". European Journal of Combinatorics. 11 (4): 305–311. doi:10.1016/S0195-6698(13)80131-X.
- ^ Kitson, Derek (2015). "Finite and Infinitesimal Rigidity with Polyhedral Norms". Discrete & Computational Geometry. 54 (2): 390–411. arXiv:1401.1336. doi:10.1007/s00454-015-9706-x. S2CID 15520982.