کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949124 | 1439983 | 2017 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Orthogonal layout with optimal face complexity
ترجمه فارسی عنوان
طرح ارتوگنال با پیچیدگی چهره بهینه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
طراحی گراف رسم ارتوگنال، پیچیدگی صورت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study a problem motivated by rectilinear schematization of geographic maps. Given a biconnected plane graph G and an integer kâ¥0, does G have a strict-orthogonal drawing (i.e., an orthogonal drawing without edge bends) with at most k reflex angles per face? For k=0, the problem is equivalent to realizing each face as a rectangle. We prove that the strict-orthogonal drawability problem for arbitrary reflex complexity k can be reduced to a graph matching or a network flow problem. Consequently, we obtain an OË(n10/7k1/7)-time algorithm to decide strict-orthogonal drawability, where OË(r) denotes O(rlogcâ¡r), for some constant c. In contrast, if the embedding is not fixed, we prove that it is NP-complete to decide whether a planar graph admits a strict-orthogonal drawing with reflex face complexity 4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 63, June 2017, Pages 40-52
Journal: Computational Geometry - Volume 63, June 2017, Pages 40-52
نویسندگان
Md. Jawaherul Alam, Stephen G. Kobourov, Debajyoti Mondal,