Nested hierarchies in planar graphs Original Research Article

We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph image and defines a unique hierarchy. We demonstrate that image is the union of a set of special subgraphs, named ‘bubbles’, that are themselves maximal planar graphs. The graph image 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 image into communities and the tree structure defines the hierarchical relations between these communities.