Nested hierarchies in planar graphs

Won Min Song; T. Di Matteo; Tomaso Aste

doi:10.1016/j.dam.2011.07.018

Nested hierarchies in planar graphs

Won Min Song^*, T. Di Matteo, Tomaso Aste

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

24 Citations (Scopus)

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 language	English
Pages (from-to)	2135-2146
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	159
Issue number	17
DOIs	https://doi.org/10.1016/j.dam.2011.07.018
Publication status	Published - 28 Oct 2011

Access to Document

10.1016/j.dam.2011.07.018

Cite this

@article{91b56131f19a46f6b1d54ee64d06f182,

title = "Nested hierarchies in planar graphs",

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.",

keywords = "3-clique, Bubble, Community, Hierarchy, Maximal planar graph",

author = "Song, {Won Min} and {Di Matteo}, T. and Tomaso Aste",

year = "2011",

month = oct,

day = "28",

doi = "10.1016/j.dam.2011.07.018",

language = "English",

volume = "159",

pages = "2135--2146",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "17",

}

TY - JOUR

T1 - Nested hierarchies in planar graphs

AU - Song, Won Min

AU - Di Matteo, T.

AU - Aste, Tomaso

PY - 2011/10/28

Y1 - 2011/10/28

N2 - 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.

AB - 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.

KW - 3-clique

KW - Bubble

KW - Community

KW - Hierarchy

KW - Maximal planar graph

UR - http://www.scopus.com/inward/record.url?scp=80052603806&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2011.07.018

DO - 10.1016/j.dam.2011.07.018

M3 - Article

SN - 0166-218X

VL - 159

SP - 2135

EP - 2146

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 17

ER -

Nested hierarchies in planar graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this