×

Multi-objective optimization aided to allocation of vertices in aesthetic drawings of special graphs. (English) Zbl 1297.05169

I was recently asked by a referee to provide an additional figure to clarify a process that I specified in a technical paper. Such drawings are even more important to explain and demonstrate a business process. Besides such common criteria of being simple, clear, and informational, this paper is to address the issue of drawing aesthetically appealing flowcharts. It is indeed a well-studied problem: when I entered “aesthetic layout of flowcharts” into the Google search box, two and half million results were sent back. The introductory section of this paper under review also provides a rich set of background information of this interesting yet important research area.
To be precise, this paper is to address a specific and simplified version of this NP-complete problem. A business process diagram, the focus of this paper, consists of a collection of columns, where rectangles, rhombuses, and circles are added and connected with lines. With the input being a collection of shapes for the permutable columns and pairs of preceding and following shapes to be connected, the task is to fix those shapes in certain positions of their respective columns so that the total length of connecting lines and/or the total number of the preceding shapes that are either not higher than, or to the right of, their corresponding following shapes are minimized. The output is a chart with multiple rows, whose number depends on the sought objective(s).
Once the aforementioned objectives are defined, a searching space cutting and depth-first search oriented branch and bound version of the shape fixing algorithm is derived and its “efficiency” is anecdotally compared with that of the complete enumeration. Several experiments are made and their results presented. It is pointed out that the time spent with the branch and bound algorithm grows approximately twice when the number of rows goes up by one, and a problem that takes nineteen rows is solved in two and half hours in a reasonably equipped computer. I have to say that the final drawing is indeed aesthetically appealing.
This is certainly another interesting and successful application of the branch and bound method, almost always the first tool that we rush to when an NP-hard optimization problem is to be solved.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
90C29 Multi-objective and goal programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite