Skip navigation
Skip navigation

Nested hierarchies in planar graphs

Song, Won-Min; Di Matteo, Tiziana; Aste, Tomaso

Description

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...[Show more]

dc.contributor.authorSong, Won-Min
dc.contributor.authorDi Matteo, Tiziana
dc.contributor.authorAste, Tomaso
dc.date.accessioned2015-12-10T22:54:59Z
dc.identifier.issn0166-218X
dc.identifier.urihttp://hdl.handle.net/1885/59893
dc.description.abstractWe 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.
dc.publisherElsevier
dc.sourceDiscrete Applied Mathematics
dc.subjectKeywords: 3-clique; Bubble; Community; Hierarchy; Planar graph; Graphic methods; Plant extracts; Trees (mathematics) 3-clique; Bubble; Community; Hierarchy; Maximal planar graph
dc.titleNested hierarchies in planar graphs
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume159
dc.date.issued2011
local.identifier.absfor020406 - Surfaces and Structural Properties of Condensed Matter
local.identifier.ariespublicationu9210271xPUB512
local.type.statusPublished Version
local.contributor.affiliationSong, Won-Min, College of Physical and Mathematical Sciences, ANU
local.contributor.affiliationDi Matteo, Tiziana, King's College London
local.contributor.affiliationAste, Tomaso, University of Kent
local.description.embargo2037-12-31
local.bibliographicCitation.issue17
local.bibliographicCitation.startpage2135
local.bibliographicCitation.lastpage2145
local.identifier.doi10.1016/j.dam.2011.07.018
local.identifier.absseo970102 - Expanding Knowledge in the Physical Sciences
dc.date.updated2016-02-24T11:56:28Z
local.identifier.scopusID2-s2.0-80052603806
local.identifier.thomsonID000295859500017
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Song_Nested_hierarchies_in_planar_2011.pdf858.18 kBAdobe PDF    Request a copy
02_Song_Nested_hierarchies_in_planar_2011.pdf938.83 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator