کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777584 | 1632966 | 2017 | 37 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Layered separators in minor-closed graph classes with applications
ترجمه فارسی عنوان
جداکننده های لایه در کلاس های گراف کوچک و با برنامه های کاربردی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جداساز نمودار پلانار، سطح، جزئی، توپولوژی جزئی، جداساز لایه، عرض درخت لایه رنگ آمیزی بی نظیر، طرح چیدمان، طراحی شبکه 3 بعدی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We use layered separators to prove O(logâ¡n) bounds for a number of problems where O(n) was a long-standing previous best bound. This includes the nonrepetitive chromatic number and queue-number of graphs with bounded Euler genus. We extend these results with a O(logâ¡n) bound on the nonrepetitive chromatic number of graphs excluding a fixed topological minor, and a logO(1)â¡n bound on the queue-number of graphs excluding a fixed minor. Only for planar graphs were logO(1)â¡n bounds previously known. Our results imply that every n-vertex graph excluding a fixed minor has a 3-dimensional grid drawing with nlogO(1)â¡n volume, whereas the previous best bound was O(n3/2).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 127, November 2017, Pages 111-147
Journal: Journal of Combinatorial Theory, Series B - Volume 127, November 2017, Pages 111-147
نویسندگان
Vida DujmoviÄ, Pat Morin, David R. Wood,