کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | ترجمه فارسی | نسخه تمام متن |
---|---|---|---|---|---|
8902724 | 1632242 | 2018 | 6 صفحه PDF | سفارش دهید | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bend-optimal orthogonal drawings of triconnected plane graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 15, Issue 2, August 2018, Pages 168-173
نویسندگان
Siddharth Bhatia, Kunal Lad, Rajiv Kumar,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت