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?

Improve this question
$\endgroup$
4
  • $\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
    Commented Oct 28, 2016 at 12:58
  • $\begingroup$ I meant arc-symmetric. Sorry for any confusion. $\endgroup$
    – Hans-Peter Stricker
    Commented Oct 28, 2016 at 13:21
  • $\begingroup$ I replaced "symmetric" by "undirected", because that's why I really meant. $\endgroup$
    – Hans-Peter Stricker
    Commented Oct 31, 2016 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
    Commented Oct 31, 2016 at 9:28

0

Reset to default

You must log in to answer this question.