UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Nested hierarchies in planar graphs

Song, W-M; Di Matteo, T; Aste, T; (2011) Nested hierarchies in planar graphs. Discrete Applied Mathematics , 159 (17) pp. 2135-2146. 10.1016/j.dam.2011.07.018.

Full text not available from this repository.


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.

Type: Article
Title: Nested hierarchies in planar graphs
DOI: 10.1016/j.dam.2011.07.018
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
URI: http://discovery.ucl.ac.uk/id/eprint/1360874
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item