کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419167 681748 2007 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Queue layouts of iterated line directed graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Queue layouts of iterated line directed graphs
چکیده انگلیسی

In this paper, we study queue layouts of iterated line directed graphs. A k-queue layout of a directed graph consists of a linear ordering of the vertices and an assignment of each arc to exactly one of the k queues so that any two arcs assigned to the same queue do not nest. The queuenumber of a directed graph is the minimum number of queues required for a queue layout of the directed graph.We present upper and lower bounds on the queuenumber of an iterated line directed graph Lk(G)Lk(G) of a directed graph G. Our upper bound depends only on G and is independent of the number of iterations k  . Queue layouts can be applied to three-dimensional drawings. From the results on the queuenumber of Lk(G)Lk(G), it is shown that for any fixed directed graph G  , Lk(G)Lk(G) has a three-dimensional drawing with O(n)O(n) volume, where n   is the number of vertices in Lk(G)Lk(G). These results are also applied to specific families of iterated line directed graphs such as de Bruijn, Kautz, butterfly, and wrapped butterfly directed graphs. In particular, the queuenumber of k-ary butterfly directed graphs is determined if k is odd.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 9, 1 May 2007, Pages 1141–1154
نویسندگان
,