کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431087 688270 2010 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Convex drawings of hierarchical planar graphs and clustered planar graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Convex drawings of hierarchical planar graphs and clustered planar graphs
چکیده انگلیسی

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 8, Issue 3, September 2010, Pages 282–295
نویسندگان
, ,