Di Matteo, T;
Nested hierarchies in planar graphs.
Discrete Applied Mathematics
We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named 'bubbles', that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tree structure where neighboring bubbles are joined together by a 3-clique. Bubbles naturally provide the subdivision of G into communities and the tree structure defines the hierarchical relations between these communities. © 2011 Elsevier B.V. All rights reserved.
|Title:||Nested hierarchies in planar graphs|
|Keywords:||3-clique, Bubble, Community, Hierarchy, Maximal planar graph|
|UCL classification:||UCL > School of BEAMS > Faculty of Engineering Science
UCL > School of BEAMS > Faculty of Engineering Science > Computer Science
Archive Staff Only