Topology of tangledness of network embeddings

The force directed layout (FDL; mass and spring model) is a class of layouts in which the position of the nodes are highly correlated with the network structure. In three dimensional space, one can embed any network without link crossings. However, as in glassy systems, the number of low energy configurations in FDL is extremely large, and distinguishing between them is very difficult. Here we introduce a topological measure, which we call the graph linking number, that allows us to classify some of these energy states.
We study the relation between graph linking number and the energy of the FDL. We find that the graph linking number for FDL is much lower than random layouts. Also, the distribution of graph linking number in FDL for networks with different topologies can be very different. For some network topologies, e.g. lattices, there is a strong correlation between the graph linking number and energy, while for other network topologies, e.g. Erdos-Renyi and Barabasi-Albert networks we observe less correlation between graph linking number and energy. This shows that the graph linking number is capturing a new interesting aspect of the topology of embeddings not captured by the energy and is therefore useful for classification of graph embeddings.