کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
477020 700071 2012 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
GA for straight-line grid drawings of maximal planar graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
GA for straight-line grid drawings of maximal planar graphs
چکیده انگلیسی

A straight-line grid drawing of a planar graph G of n vertices is a drawing of G   on an integer grid such that each vertex is drawn as a grid point and each edge is drawn as a straight-line segment without edge crossings. Finding algorithms for straight-line grid drawings of maximal planar graphs (MPGs) in the minimum area is still an elusive goal. In this paper we explore the potential use of genetic algorithms to this problem and various implementation aspects related to it. Here we introduce a genetic algorithm, which nicely draws MPG of moderate size. This new algorithm draws these graphs in a rectangular grid with area ⌊2(n-1)/3⌋×⌊2(n-1)/3⌋⌊2(n-1)/3⌋×⌊2(n-1)/3⌋ at least, and that this is optimal area (proved mathematically). Also, the novel issue in the proposed method is the fitness evaluation method, which is less costly than a standard fitness evaluation procedure. It is described, tested on several MPG.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Egyptian Informatics Journal - Volume 13, Issue 1, March 2012, Pages 9–17
نویسندگان
,