×

TimGA: A genetic algorithm for drawing undirected graphs. (English) Zbl 1007.68138

Summary: The problem of drawing graphs nicely contains several computationally intractable subproblems. Hence, it is natural to apply genetic algorithms to graph drawing. This paper introduces a Genetic Algorithm (TimGA) which nicely draws undirected graphs of moderate size. The aesthetic criteria used are the number of edge crossings, even distribution of nodes, and edge length deviation. Although TimGA usually works well, there are some unsolved problems related to the genetic crossover operation of graphs. Namely, our tests indicate that TimGA’s search is mainly guided by the mutation operations.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)

Keywords:

drawing graphs

Software:

TimGA
PDFBibTeX XMLCite
Full Text: EuDML EMIS