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.

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. A distance constraint system (G,\delta) , where G=(V,E) is a graph and \delta: E \rightarrow \mathbb{R}^ 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 connection to Cayley configuration spaces below. 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 Deza & Laurent. 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. Example. The wheel graph W_5 contains K_4 as a minor. Thus, it is not 2-flattenable. 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 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. 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1272070201 under CC BY-SA 4.0; modifications have been made.