New approach for ventilation network graph drawing based on Sugiyama method and GA-SA algorithm

Li-jun Deng, Jian Liu

College of Safety Science and Engineering, Liaoning Technical University, Liaoning Fuxin 123000, China

Ventilation network graph has an important place in the management of a coal mine. In that case, aesthetics plays a major role for generating readable and understandable layouts. Besides, the drawing is required to be oval. The traditional longest path method for drawing ventilation network graph is inefficient and cannot effectively reduce the number of arc crossings because of the geometric intersection method. In this paper, we developed a new approach to draw ventilation network graph, consist of Sugiyama method framework, the longest path method and GA-SA algorithm. The longest path method was employed to rank nodes, and long arcs were removed by solving integer programming problem to minimize the sum length of ventilation network. Then genetic algorithm and simulated annealing algorithm were adopted to optimize the node order on reducing the number of arc crossings. In order to make the drawing be oval, a modified version of the longest path method was made to calculate node coordinates and arc shapes, which is called the longest parallel path method. Finally, computational experiments were carried out on two test ventilation network with our new approach.