Hacker News new | comments | ask | show | jobs | submit login
Realizability of Graphs (2008) [pdf] (bard.edu)
35 points by luu 4 months ago | hide | past | web | favorite | 6 comments

So, n-realizability seems to mean you can make a model of the graph in n dimensions, with every edge the same length. (i.e. much more strict than the usual planarity) What is that useful for?

Not quite. If I understand correctly, the requirement is that any model of the graph with arbitrary edge lengths can be "flattened" into n dimensions, without changing any edge lengths. This is not necessarily stronger than planarity; in particular, according to these slides, the complete bipartite graph K3,3 is 2-realizable but not planar.

I'm not sure what practical applications there are for this area of theory. But intuitively, it seems like the "flattening" process captures some notion of rigidity. For instance, there's a sense in which a 1-realizable graph is as non-rigid as it's possble to get. If you make a physical model of a tree, using (idealized, infinitely thin) rigid rods and joints, the tree can always be folded up so that all of its edges lie parallel.

Similarly, a 2-realizable graph consists of rigid, flat pieces, connected along their edges by "hinges" that can always be folded flat, whatever their original configuration.

So maybe this could be somehow applied to the automated design of structures that can be assembled from foldable pieces.

Oh geez, yeah I misread that totally! thanks.

A graph is d-realizable if given any realization of the graph in n dimensions (possibly high dimensional), there exists a realization in d dimensions with the same edge lengths.

(I thought 'n dimensions' looked clearer than RR^n, though less accurate I guess)

Wild guess is dimensional reduction. Sorta perfect PCA

What's PCA?

Principal Component Analysis

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact