Invited speakers

Graph Drawing Through the Lens of a Framework for Analyzing Visualization Methods

Tamara Munzner (UBC Vancouver)

The visualization community has drawn heavily on the algorithmic and systems-building work that has appeared with the graph drawing literature, and in turn has been a fertile source of applications. In the spirit of further promoting the effective transfer of ideas between our two communities, I will discuss a framework for analyzing the design of visualization systems. I will then analyze a range of graph drawing techniques through this lens. In the early stages of a project, this sort of analysis may benefit algorithm developers who seek to identify open problems to attack. In later project stages, it could guide algorithm developers in characterizing how newly developed layout methods connect with the tasks and goals of target users in different application domains.

Biography: Tamara Munzner is a professor at the University of British Columbia Department of Computer Science, where she has been since 2002. She was a research scientist from 2000 to 2002 at the Compaq Systems Research Center in California, earned her PhD from Stanford between 1995 and 2000, and was a technical staff member at the Geometry Center mathematical visualization research group from 1991 to 1995. She was InfoVis Co-Chair in 2003 and 2004 and EuroVis Co-Chair in 2009 and 2010. Her research interests include the development, evaluation, and characterization of information visualization and graph drawing systems and techniques from both user-driven and technique-driven perspectives. She has worked on visualization projects in a broad range of application domains, including evolutionary biology, genomics, topology, computational linguistics, large-scale system administration, web site design, and web log analysis.

The Value of Research

Joe Marks (co-founder & CTO, Upfront Analytics Ltd.)

Which outcome would you prefer for your current research project: a paper with 500 citations, or a business worth $5M? Or maybe it doesn’t matter to you as long as you’re doing interesting work and having fun. But even if academic and industrial researchers tend to value research differently, deciding what to work on is the first and fundamental step in any inquiry, and so it is worth thinking about the process and criteria that researchers use for project selection.

To get you thinking about this issue, I will present a selection of recent industrial projects with which I was involved as a researcher or manager. In the tradition of reality TV, you the audience will be invited to predict a 10-year citation count, estimate a dollar value, and assess general coolness for each of the projects presented. Active participation is encouraged! Although the focus is on research from the media & entertainment industry, hopefully you will come away with thoughts about how to estimate the value of your own research from both an academic and a commercial perspective. I will end with some speculative potential graph-drawing projects to which we can apply our just-practiced judgment on project selection.

Biography: Joe Marks has recently embarked on a new career as an entrepreneur with Upfront Analytics Ltd, a small company in Dublin, Ireland that is developing a playful approach to market research. Immediately prior to co-founding Upfront Analytics, he was Vice President & Research Fellow at Disney Research in Los Angeles from 2007-2012. He holds three degrees from Harvard University. His areas of technical interest include computer graphics, human-computer interaction, and artificial intelligence. He was the Research Director at Mitsubishi Electric Research Labs (MERL) in Cambridge, MA, from 2000-2006. He has also worked at Digital's Cambridge Research Laboratory and at Bolt Beranek and Newman. His Google Scholar h-index is 26, and he has managed more than $100M in industrial R&D spend. He was conference chair for Graph Drawing 2000 in Williamsburg, Virginia, and conference chair for SIGGRAPH 2007 in San Diego. He has also held several other leadership positions in ACM- and IEEE-sponsored conferences and organizations.

The Counting of Crossing-Free Geometric Graphs—Algorithms and Combinatorics

Emo Welzl (ETH Zurich, Switzerland)

We are interested in the understanding of crossing-free geometric graphs—these are graphs with an embedding on a given planar point set where the edges are drawn as straight line segments without crossings. Often we are restricted to certain types of graphs, most prominently triangulations, but also spanning cycles, spanning trees, or (perfect) matchings (and crossing-free partitions), among others. A primary goal is to enumerate, to count, or to sample graphs of a certain type for a given point set—so these are algorithmic questions—, or to give estimates for the maximum and minimum number of such graphs on any set of n points—these are problems in extremal combinatorial geometry.

In this talk we will encounter some of the recent developments (since my GD'06 talk). Among others, I will show some of the new ideas for providing extremal estimates, e.g., for the number of crossing-free spanning cycles: the support-refined estimate for cycles versus triangulations, the use of pseudo-simultaneously flippable edges in triangulations, and the employment of Kasteleyn's beautiful linear algebra method for counting perfect matchings in planar graphs—here, interestingly, in a weighted version. Moreover, Raimund Seidel's recent 2ⁿ-algorithm for counting triangulations is discussed, with its extensions by Manuel Wettstein to other types of graphs (e.g., crossing-free perfect matchings).

Biography: Emo Welzl has been Professor of Computer Science at the Institute for Theoretical Computer Science of ETH Zurich since April 1996. His research interests are in the foundations of computer science, mainly algorithms and data structures, in particular computational geometry and applications, combinatorial models for optimization, analysis of geometric structures, randomized methods, and discrete geometry; recently also satisfiability.

1977–1981 Diplom in Applied Mathematics at the Graz University of Technology, Austria. 1983 doctorate (supervisor Hermann Maurer) with a topic in formal languages, 1988 Habilitation in Foundations of Computer Science, also in Graz. 1984 post-doc at Rijks University Leiden, Netherlands, 1985 visiting professor at the University of Denver, Colorado, USA, for one semester. 1987–1996 Professor of Mathematics (theory of computation) at Berlin Free University. 1994 four-month research stay at the International Computer Science Institute, Berkeley, California, USA. 1991–1996 chair of the graduate program "Algorithmic Discrete Mathematics" at Free University, Humboldt University, University of Technology, and the Konrad Zuse Center in Berlin. 2000–2005 chair (at site Zurich) of the Berlin–Zurich Graduate Program in "Combinatorics, Geometry, and Computation".