کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414576 680978 2016 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Orthogonal graph drawing with inflexible edges
ترجمه فارسی عنوان
رسم نمودار متعامد با لبه های غیرانعطاف پذیر
کلمات کلیدی
طراحی نمودار متعامد؛ به حداقل رساندن خم؛ تعبیه مسطح ؛ الگوریتم پارامتریک؛ پیچیدگی محاسباتی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We consider the problem of creating plane orthogonal drawings of 4-planar graphs (planar graphs with maximum degree 4) with constraints on the number of bends per edge. More precisely, we have a flexibility function assigning to each edge e   a natural number flex(e)flex(e), its flexibility. The problem FlexDraw asks whether there exists an orthogonal drawing such that each edge e   has at most flex(e)flex(e) bends. It is known that FlexDraw is NP-hard if flex(e)=0flex(e)=0 for every edge e [1]. On the other hand, FlexDraw can be solved efficiently if flex(e)≥1flex(e)≥1[2] and is trivial if flex(e)≥2flex(e)≥2[3] for every edge e.To close the gap between the NP-hardness for flex(e)=0flex(e)=0 and the efficient algorithm for flex(e)≥1flex(e)≥1, we investigate the computational complexity of FlexDraw in case only few edges are inflexible   (i.e., have flexibility 0). We show that for any ε>0ε>0FlexDraw is NP-complete for instances with O(nε)O(nε) inflexible edges with pairwise distance Ω(n1−ε)Ω(n1−ε) (including the case where they induce a matching), where n   denotes the number of vertices in the graph. On the other hand, we give an FPT-algorithm with running time O(2k⋅n⋅Tflow(n))O(2k⋅n⋅Tflow(n)), where Tflow(n)Tflow(n) is the time necessary to compute a maximum flow in a planar flow network with multiple sources and sinks, and k is the number of inflexible edges having at least one endpoint of degree 4.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 55, May 2016, Pages 26–40
نویسندگان
, , ,