کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8960181 | 1646386 | 2018 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Gap-planar graphs
ترجمه فارسی عنوان
نمودارهای گاف-فلاری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We introduce the family of k-gap-planar graphs for kâ¥0, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 36-52
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 36-52
نویسندگان
Sang Won Bae, Jean-Francois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok-Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, Csaba D. Tóth,