کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950902 1441042 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Monotone drawings of graphs with few directions
ترجمه فارسی عنوان
نقاشی های یکنواخت گراف ها با چند جهت
کلمات کلیدی
نقشه های مونوتونی، جنگل اسنایدر، الگوریتم های گراف، حداکثر نمودارهای مسطح نمودار همیلتون
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that a planar graph admits a monotone drawing with only one direction of monotonicity if and only if it has a Hamiltonian path between two vertices lying in the same face. Also, we prove that maximal planar graphs admit monotone drawings with two (orthogonal) directions, while triconnected planar graphs with three directions. The latter two results are obtained by applying the famous drawing algorithm based on Schnyder realizers.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 120, April 2017, Pages 16-22
نویسندگان
,