کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871764 1440191 2017 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
NIC-planar graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
NIC-planar graphs
چکیده انگلیسی
We characterize embeddings of maximal NIC-planar graphs in terms of generalized planar dual graphs. The characterization is used to derive tight bounds on the density of maximal NIC-planar graphs which ranges between 3.2(n−2) and 3.6(n−2). Further, we prove that optimal NIC-planar graphs with 3.6(n−2) edges have a unique embedding and can be recognized in linear time, whereas the general recognition problem of NIC-planar graphs is NP-complete. In addition, we show that there are NIC-planar graphs that do not admit right angle crossing drawings, which distinguishes NIC-planar from IC-planar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 232, 11 December 2017, Pages 23-40
نویسندگان
, , , , ,