کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
8902724 1632242 2018 6 صفحه PDF سفارش دهید دانلود رایگان
عنوان انگلیسی مقاله ISI
Bend-optimal orthogonal drawings of triconnected plane graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bend-optimal orthogonal drawings of triconnected plane graphs
چکیده انگلیسی
A drawing of a plane graph G in which each edge is represented by a sequence of alternating horizontal and vertical line segments is called an orthogonal drawing. The points of intersection of horizontal and vertical line segments of an edge in an orthogonal drawing are called bends. The best known algorithm to find a bend-optimal orthogonal drawing of a plane graph takes time O(n1.5) where n is the number of vertices in the graph. In this paper we present a new linear time algorithm to find an orthogonal drawing of a plane 3-connected graph (with maximum degree 4) and give bounds on number of bends (in terms of number k of degree-4 vertices in the graph) in the resulting drawing with respect to the number b(G) of bends in the bend-optimal orthogonal drawing of the same graph. The bound is b(G)+3k.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 15, Issue 2, August 2018, Pages 168-173
نویسندگان
, , ,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت