کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433956 689660 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Upward planar graphs and their duals
ترجمه فارسی عنوان
نمودارهای فلات بالا و دوگانگی های آنها
کلمات کلیدی
نمودارهای پلانار، نمودار دوگانه، طراحی گراف منظر بالا سطوح
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider upward planar drawings of directed graphs in the plane (UP), and on standing (SUP) and rolling cylinders (RUP). In the plane and on the standing cylinder the edge curves are monotonically increasing in y  -direction. On the rolling cylinder they wind unidirectionally around the cylinder. There is a strict hierarchy of classes of upward planar graphs: UP⊂SUP⊂RUPUP⊂SUP⊂RUP.In this paper, we show that rolling and standing cylinders switch roles when considering an upward planar graph and its dual. In particular, we prove that a strongly connected graph is RUP if and only if its dual is a SUP dipole. A dipole is an acyclic graph with a single source and a single sink. All RUP graphs are characterized in terms of their duals using generalized dipoles. Moreover, we obtain a characterization of the primals and duals of wSUP graphs which are upward planar graphs on the standing cylinder and allow for horizontal edge curves.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 571, 16 March 2015, Pages 36–49
نویسندگان
, , , , ,