----------------------------------------------------------------------------------------------------

             Department of Systems Engineering and Engineering Management
                     The Chinese University of Hong Kong

----------------------------------------------------------------------------------------------------

Date: Friday, April 23, 2021, 16:30 to 17:30

Title: Optimization in Graph Drawing

Speaker: Professor Rafael Martí, University of Valencia

Abstract:

Geometric representations have been the subject of study since ancient times. The famous words by Archimedes “Do not disturb my circles!” ("Noli turbare circulos meos!") indicate the early connection between graph drawing and geometry.  Today, automated graph-drawing systems utilize procedures to position nodes and arcs to produce graphs with desired properties. The literature contains many different standards to represent a graph (Di Battista et al., 1998). All of them have readability as the main objective, although there are different ways to achieve this goal.  Research studies of graph drawing have produced a prolific range of applications from trees to orthogonal graphs. In this talk, we focus on the realm of graph drawing called hierarchical representations.

General graphs can be drawn as hierarchical maps following Sugiyama's framework, which obtains a good drawing by representing the arcs according to certain aesthetics that induce readability: straight lines, uniform direction, and low number of crossings (Sugiyama et al., 1981). This framework has been applied in many settings (e.g., Kaufmann and Wagner, 2001; Napoletano et al., 2019), and consists of three steps: assign nodes to layers, reduce edge crossings, and assign coordinates to nodes. In this talk we show the mathematical models to optimize these steps, and the heuristic methods applied to solve them in short computational times, as required by graph drawing systems. We also cover some extensions, such as dynamic graph drawing, and how to solve them efficiently.
 

Biography:

Rafael Martí is Professor of Statistics and Operations Research at the University of Valencia, Spain. He received a doctoral degree in Mathematics from the University of Valencia in 1994. He has done extensive research in metaheuristics for hard optimization problems. Dr Martí has about 200 publications, half of them in indexed journals (JCR), including EJOR, Informs JoC, IIE Transactions, JOGO, C&OR, and Discrete and Applied Maths. His h-index is 54 according to Google scholar. He is the co-author of several monographic books: Scatter Search (Kluwer 2003), The Linear Ordering Problem (Springer 2011), and Metaheuristics for Business Analytics (Springer 2018), and has secured an American patent. Prof. Martí has recently co-edited the Handbook of Heuristics, a 3-volume reference in the area, published by Springer.

Prof. Martí is currently Area Editor in the Journal of Heuristics, Associate Editor in the European Journal of Operational Research, TOP, Math. Prog. Computation, and the Int. Journal of Metaheuristics. He is Senior Research Associate of OptTek Systems (USA), and has given about 50 invited and plenary talks. Dr. Martí has been invited Professor in many universities, including the University of Colorado (USA), the University of Molde (Norway), the University of Wien (Austria), and University of Bretagne-Sud (France), or the University College of Dublin (Ireland). He coordinates the Spanish Network on Metaheuristics, currently funded by the Spanish government and as a SEIO working group.