Nested hierarchies in planar graphs

Won Min Song, T. Di Matteo, Tomaso Aste

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)2135-2146
Number of pages12
JournalDiscrete Applied Mathematics
Volume159
Issue number17
DOIs
StatePublished - 28 Oct 2011
Externally publishedYes

Keywords

  • 3-clique
  • Bubble
  • Community
  • Hierarchy
  • Maximal planar graph

Fingerprint

Dive into the research topics of 'Nested hierarchies in planar graphs'. Together they form a unique fingerprint.

Cite this