GA for straight-line grid drawings of maximal planar graphs | Zendy

Mohamed A. El-Sayed | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

GA for straight-line grid drawings of maximal planar graphs

Author(s) -

Mohamed A. El-Sayed

Publication year - 2012

Publication title -

egyptian informatics journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.728

H-Index - 34

eISSN - 2090-4754

pISSN - 1110-8665

DOI - 10.1016/j.eij.2012.01.003

Subject(s) - grid , computer science , graph drawing , planar graph , vertex (graph theory) , planar , enhanced data rates for gsm evolution , line (geometry) , point (geometry) , algorithm , line segment , combinatorics , genetic algorithm , graph , mathematical optimization , theoretical computer science , geometry , mathematics , computer graphics (images) , artificial intelligence , machine learning

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⌋ 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research