# Backbone Layout

### Description

Small-world graphs have characteristically low average distance and thus cause force-directed methods to generate drawings that look like hairballs.

The backbone layout tries to untangle hairball graphs. The method is based on a spanning subgraph that is sparse but connected and consists of strong ties holding together communities.

Strong ties are identified using a measure of embeddedness which is based on a weighted accumulation of triangles in quadrangles.

More detailed background information is provided in

- Arlind Nocaj, Mark Ortmann, and Ulrik Brandes: Untangling Hairballs: From 3 to 14 Degrees of Separation, to appear in Proceedings of the 22nd International Symposium on Graph Drawing (GD 2014).

### Asymptotic Complexity

The computation of the embeddedness together with the backbone extraction scales well for large networks with, e.g., millions of edges and nodes.

The asymptotic runtime is for a graph where is the maximum degree of a vertex .

The final layout based on the extracted backbone needs time and memory, which does not scale for very large graphs.