| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 418551 | Discrete Applied Mathematics | 2011 | 12 Pages |
We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph GG and defines a unique hierarchy. We demonstrate that GG is the union of a set of special subgraphs, named ‘bubbles’, that are themselves maximal planar graphs. The graph GG 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 GG into communities and the tree structure defines the hierarchical relations between these communities.
► We construct unique hierarchies on a maximal planar graph. ► Separating property of cycles defines a partial order on the set of 3-cliques. ► The poset defines a complete set of special subgraphs called ‘bubbles’. ► The bubbles and separating 3-cliques constitute a unique bubble hierarchical tree. ► Communities and hierarchy naturally emerge from the bubble hierarchy.
