کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414681 681004 2014 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bend-optimal orthogonal graph drawing in the general position model
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Bend-optimal orthogonal graph drawing in the general position model
چکیده انگلیسی

We consider orthogonal drawings in the general position model, i.e., no two points share a coordinate. The drawings are also required to be bend minimal, i.e., each edge of a drawing in k   dimensions has exactly one segment parallel to each coordinate direction that are glued together at k−1k−1 bends.We provide a precise description of the class of graphs that admit an orthogonal drawing in the general position model in the plane. The main tools for the proof are Eulerian orientations of graphs and discrete harmonic functions.The tools developed for the planar case can also be applied in higher dimensions. We discuss two-bend drawings in three dimensions and show that K2k+2K2k+2 admits a k  -bend drawing in k+1k+1 dimensions. If we allow that a vertex is placed at infinity, we can draw K2k+3K2k+3 with k   bends in k+1k+1 dimensions.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 3, Part B, April 2014, Pages 460–468
نویسندگان
, , ,