کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777093 1632570 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two-layer Drawings of Bipartite Graphs
ترجمه فارسی عنوان
نقوش دو لایه دو طرفه نمودارها
کلمات کلیدی
نمودار توپولوژیک انتزاعی، طراحی دو لایه گراف دو طرفه،
ترجمه چکیده
ما یک الگوریتم زمان چندجملهای را برای تصمیم گیری در مورد اینکه آیا یک گراف دو طرفه متصل به یک رسم دو لایه در یک هواپیما اجازه می دهد تا یک زیرمجموعه مشخص از جفت های لبه های متقاطع عبور کند، ارائه می دهیم. ما مسئله تصمیم گیری در مورد اینکه آیا یک نقاشی وجود دارد که در آن یک زیرمجموعه مشخص از سه گانه لبه های عبور دوطرفه همزمان هستند وجود دارد. ما یک شرط لازم برای همین و حدس می زنیم که کافی است.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش مقاله
نقوش دو لایه دو طرفه نمودارها
چکیده انگلیسی
We give a polynomial-time algorithm to decide whether a connected bipartite graph admits a two-layer drawing in the plane such that a specified subset of pairs of disjoint edges cross. We consider the problem of deciding whether there exists such a drawing in which a specified subset of triples of pairwise crossing edges are concurrent. We give a necessary condition for the same and conjecture that it is sufficient.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 351-357
نویسندگان
, , ,