کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414808 681046 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximum upward planar subgraphs of embedded planar digraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Maximum upward planar subgraphs of embedded planar digraphs
چکیده انگلیسی

Let G be an embedded planar digraph. A maximum upward planar subgraph of G is an embedding preserving subgraph that is upward planar and, among those, has the maximum number of edges. This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) we prove that the addressed problem is NP-Hard; (ii) a fast heuristic and an exponential-time exact algorithm are described; (iii) a wide experimental analysis is performed to show the effectiveness of our techniques.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 41, Issue 3, November 2008, Pages 230-246