کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437722 690179 2015 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fan-planarity: Properties and complexity
ترجمه فارسی عنوان
فان پلاریستی: خواص و پیچیدگی
کلمات کلیدی
نمودار پلاناریسم طراحی گراف گذرگاه های لبه، چگالی لبه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt [35], who proved that every n  -vertex fan-planar drawing has at most 5n−105n−10 edges, and that this bound is tight for n≥20n≥20. We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and k-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 589, 19 July 2015, Pages 76–86
نویسندگان
, , , , , , ,