کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436749 690032 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
چکیده انگلیسی

A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete.In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition of any edge destroys 1-planarity of G. We first study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected.Using the properties, we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system Φ (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding ξ of G that is consistent with the given rotation system Φ. Our algorithm also produces such an embedding in linear time, if it exists.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 513, 18 November 2013, Pages 65–76
نویسندگان
, , , , , ,