کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418551 681684 2011 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Nested hierarchies in planar graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Nested hierarchies in planar graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 17, 28 October 2011, Pages 2135–2146
نویسندگان
, , ,