关键词: 分层, 最小化边交叉数, 遗传算法, 哑结点

Abstract:

The DAG graph（Directed Acyclic Graph） is widely used in database modeling and engineering design，and it is always stored by using matrix．If the DAG graph which is stored by matrix can be draw precisely and clearly，the graph will be easily to read.Many problems will be conveniently to solve.There are three main aspects in the drawing of the DAG graph：delaminating，minimizing the edge crossing number and eliminating the void notes.An edge crossing minimization algorithm for layered digraphs based on genetic algorithms is presented，and a heuristic algorithm to eliminate void notes is also proposed.The result of the example shows that these methods can solve the DAG drawing problem effectively.

Key words: delaminating, edge crossing number minimization, inheritance arithmetic, void notes