Fun with Recursion and Tree Drawings
University of Illinois at Urbana-Champaign, US
Divide-and-conquer has always been one of my favorite algorithm design paradigms. In this talk, I will survey existing techniques on drawings of trees on grids with small area or width, which nicely illustrate the power of recursive thinking. I will also mention some new improved upper bounds (work in progress) for certain types of tree drawings. Along the way, we will encounter a number of interesting functions and recurrences, and plenty of open problems.
Timothy Chan is a Founder Professor in Computer Science at the University of Illinois at Urbana-Champaign. Previously, from 1999 to 2016, he taught at the University of Waterloo. He received his B.A. from Rice University in 1992 and his Ph.D. from the University of British Columbia in 1995. He has broad interests in algorithms and data structures, with near 120 conference publications and 80 journal publications, and is especially known for his work in computational geometry. He was a winner of the NSERC Doctoral Prize, was a plenary speaker at many conferences (including SODA 2011, ISAAC 2012, WADS 2013, CCCG 2014, and SoCG/STOC 2016), has served on numerous program committees, and is on the editorial boards of several journals (including Discrete and Computational Geometry and SIAM Journal on Computing).
Northeastern University, US
Prof. Vespignani received his undergraduate degree and Ph.D., both in physics and both from the University of Rome “La Sapienza,” in 1990 and 1994 respectively. He completed his postdoctoral research at Yale University and Leiden University. Prof. Vespignani worked at the International Center for Theoretical Physics (UNESCO) in Trieste and at the University of Paris-Sud in France as a member of the National Council for Scientific Research (CNRS) before moving to Indiana University in 2004. Before joining Northeastern University Vespignani was J.H.Rudy Professor of Informatics and Computing at Indiana University and serving as the Director of the Center for Complex Networks and Systems Research and the Associate Director of the Pervasive Technology Institute. Vespignani is elected fellow of the American Physical Society, member of the Academy of Europe, and fellow of the Institute for Quantitative Social Sciences at Harvard University. He is serving in the board/leadership of a variety of professional association and journals and the Institute for Scientific Interchange Foundation.
Vespignani has worked in a number of areas of non-equilibrium particle systems, statistical physics and computational sciences, including characterization of non-equilibrium phase transitions, fractal growth and self-organized criticality. Recently Vespignani’s research activity focuses on the interdisciplinary application of statistical and numerical simulation methods in the analysis of epidemic and spreading phenomena and the study of biological, social and technological networks. For several years he has been working on the characterization and modeling of the Internet, the WWW and large-scale information networks. He is now focusing his research activity in modeling the spatial spread of epidemics, including the realistic and data-driven computational modeling of emerging infectious diseases, the resilience of complex networks and the behavior of techno-social systems.
Vespignani has published 140+ peer reviewed papers in top rated scientific journals, including Nature, Science and PNAS that have accrued more than 29,000 citations according to the Google Scholar database. He is author, together with Romualdo Pastor-Satorras, of the book Evolution and Structure of the Internet. Together with Alain Barrat and Marc Barthelemy he has published in 2008 the monograph Dynamical Processes on Complex Networks.