Menu

Giuseppe Di Battista
Professor of Computer Science & Vice President for Research, Università Roma Tre, Italy
Title: Morphing Planar Graph Drawings
Abstract: Given two drawings $\Gamma_0$ and $\Gamma_1$ of the same graph $G$ a \emph{morph} between $\Gamma_0$ and $\Gamma_1$ is a continuously changing family of drawings of $G$ indexed by time $t \in [0, 1]$, such that the drawing at time $t = 0$ is $\Gamma_0$ and the drawing at time $t = 1$ is $\Gamma_1$. Suppose that both $\Gamma_0$ and $\Gamma_1$ have a certain geometric property. E.g. they are planar, their edges are straight-line segments, or their edges are polygonal lines composed of horizontal and vertical segments. It is interesting, both from the theoretical and from the applications perspectives, that all the drawings of the morph \emph{preserve} that property. The problem of finding a morph between two drawings of the same graph that preserves one or more properties is not trivial and attracted the attention of several researchers since the first half of the twentieth century. As an example, Cairns in 1944 proved that a morph that preserves planarity of a triangulation always exists. Thomassen in 1983 extended the result to all planar straight-line drawings of embedded graphs. Morphs that preserve a certain property can be classified from several perspectives. As an example they can be different in terms of vertex trajectories, in terms of vertex speed, in terms of number of steps, or in terms of arithmetic precision that is needed to compute the position of the geometric components of the drawings. We survey the state-of-the-art on this intriguing topic focusing the attention on morphs that preserve planarity.

Naoki Katoh
Department of Informatics, Kwansei Gakuin University, Japan
Title: Optimal sink location problems on dynamic flow networks
Abstract: In recent years, catastrophic disasters by massive natural disasters such as typhoon, earthquake, tsunami, volcano eruption have been increasing in the world, and disaster management is becoming extremely important more than ever. For example, in the Tohoku-Pacific Ocean Earthquake that happened in Japan on March 11, 2011, serious damage was caused by a tsunami. Although disaster prevention in civil and architectural engineering fields in Japan has been considered previously mainly from physical aspects, it is difficult to prevent large tsunamis physically. Therefore, disaster prevention from non-physical aspects, such as city planning and evacuation planning, has become more important recently. In particular, to reduce the deaths due to tsunami is critically important on coastal areas of Japan. For this, we need to prepare evacuation building so that people can protect their lives. Such problems are formulated by the use of a dynamic network which consists of a graph that models a road network in which a capacity as well as a transit time is associated with each edge, and asks to find a way to evacuate evacuees originally existing at vertices to facilities (evacuation centers) as quickly as possible. The problem can be viewed as a generalization of classical $k$-center and $k$-median problems. We shall show recent results about the difficulty and approximability of a single-facility location for general networks and polynomial time algorithms for $k$-facility location problems in path and tree networks. We also mention the minimax regret version of these problems, and multi-commodity dynamic flow problems.

Limsoon Wong
School of Computing and School of Medicine, National University of Singapore, Singapore
Title: Logic in computational biology
Abstract: I will describe some problem-solving principles that are common to multiple types of problems, even in different disciplines (I will illustrate using different areas in computer science, medicine, biology, and biotechnology.) These principles are simple logical ways to exploit fundamental properties of each problem domain, highlighting the value of both logical thought and domain knowledge, and bringing out the sometimes creative way of applying the former to the latter in the context of each problem being solved. In the specific context of computational biology, I will discuss the use of deductive, abductive, and inductive inference in de-noising of protein-protein interaction networks, identifying homologous proteins, inferring key mutations, and diagnosing specific pediatric leukemias. In the course of this discussion, I will illustrate also the useful tactics of fixing violation of invariants and guilt by association. As a demonstration of the universality of logic as a scientific problem-solving paradigm, I will show parallels in common computer science applications (e.g. deriving a better database design and securing computers against rootkit attacks).
Bio: Limsoon Wong is Kwan-Im-Thong-Hood-Cho-Temple Chair Professor in the School of Computing at the National University of Singapore (NUS). He was also a professor (now honourary) of pathology in the Yong Loo Lin School of Medicine at NUS. He currently works mostly on knowledge discovery technologies and their application to biomedicine. Limsoon is a Fellow of the ACM, inducted in 2013 for his contributions to database theory and computational biology.