2
$\begingroup$

One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The maximum may be local or global.) The pattern in question is a 2-dimensional one.

Another way to unveil a hidden structure of a undirected graph is to replace its edges by identical springs (that may - unphysically - cross each other in the course of relaxation) and look at the 3-dimensional figure in which the system has reached minimal energy. (This figure may be unique or not. It may have locally or globally minimal energy.) The pattern in question is a 3-dimensional one.

E.g. the skeleton graph of a Platonic solid will "spring" into the Platonic solid itself, thus unveiling its "true nature".

Do these ways of unveiling hidden structures have names? Which abstract mathematical principles do they follow? What do they have in common or - more generally - have to do with each other?

$\endgroup$
  • $\begingroup$ Are you using "symmetric" in the conventional sense of "arc-symmetric", or more loosely ("highly symmetric")? In any case, you might want to look into spectral embeddings. $\endgroup$ – Robin Saunders Oct 28 '16 at 12:58
  • $\begingroup$ I meant arc-symmetric. Sorry for any confusion. $\endgroup$ – Hans-Peter Stricker Oct 28 '16 at 13:21
  • $\begingroup$ I replaced "symmetric" by "undirected", because that's why I really meant. $\endgroup$ – Hans-Peter Stricker Oct 31 '16 at 8:33
  • 1
    $\begingroup$ You may be interested in the paper "Structure Preserving Embedding" (metablake.com/spe/spe-icml09.pdf), which details an embedding algorithm closely related to spectral embedding and gives visual comparisons of the results. The paper briefly discusses spring-based embeddings. Some of the references might be helpful too. I'd also recommend reviewing the answers to your previous question mathoverflow.net/questions/24978. There's plenty there that seems relevant to your current question. $\endgroup$ – Robin Saunders Oct 31 '16 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.