Graph flattenability

Flattenability in some d {\displaystyle 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 ′ {\displaystyle d'} can be "flattened" down to live in d {\displaystyle d} -dimensions, such that the distances between pairs of points connected by edges are preserved. A graph G {\displaystyle G} is d {\displaystyle d} -flattenable if every distance constraint system (DCS) with G {\displaystyle G} as its constraint graph has a d {\displaystyle 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 {\displaystyle 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 , δ ) {\displaystyle (G,\delta )} , where G = ( V , E ) {\displaystyle G=(V,E)} is a graph and δ : E → R | E | {\displaystyle \delta :E\rightarrow \mathbb {R} ^{|E|}} is an assignment of distances onto the edges of G {\displaystyle G} , is d {\displaystyle d} -flattenable in some normed vector space R d {\displaystyle \mathbb {R} ^{d}} if there exists a framework of ( G , δ ) {\displaystyle (G,\delta )} in d {\displaystyle d} -dimensions. A graph G = ( V , E ) {\displaystyle G=(V,E)} is d {\displaystyle d} -flattenable in R d {\displaystyle \mathbb {R} ^{d}} if every distance constraint system with G {\displaystyle G} as its constraint graph is d {\displaystyle 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 {\displaystyle G} , all possible embeddings of a subgraph H {\displaystyle H} of G {\displaystyle G} are contained in the set of all embeddings of G {\displaystyle 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 {\displaystyle G} in some normed vector space is the lowest dimension d {\displaystyle d} such that G {\displaystyle G} is d {\displaystyle 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 {\displaystyle l_{2}} -norm. Theorem. The flattening dimension of a graph G = ( V , E ) {\displaystyle G=\left(V,E\right)} under the l 2 {\displaystyle l_{2}} -norm is at most O ( | E | ) {\displaystyle O\left({\sqrt {\left|E\right|}}\right)} . For a detailed treatment of this topic, see Chapter 11.2 of Deza & Laurent.

Euclidean flattenability This section concerns flattenability results in Euclidean space, where distance is measured using the l 2 {\displaystyle 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 {\displaystyle K_{3}} . Theorem. A graph is 1-flattenable if and only if it is a forest.

… excerpt ends here. Continue reading the full article.