On multi-objective optimization aided drawing of special graphs

摘要

A special graph drawing problem related to the visualization of business process diagrams is considered. It is requested to find aesthetically looking paths between the given pairs of vertices of a grid, where the vertices represent the business process flow objects, and the paths represent the sequence flow. The sites of flow objects on the grid are fixed, and the sequence flow is defined. We state the problem of search for aesthetically looking paths as a problem of combinatorial multi-objective optimization, where the objectives correspond to the generally recognized criteria of aesthetics. To find a solution precisely, the algorithm of linear binary programming CPLEX was applied. For a faster solution, supposed for an interactive mode, a heuristic algorithm is developed. The experimental comparison of the mentioned algorithms is performed to substantiate the applicability of the latter.