20th International Symposium on
Sept 19~21, 2012 | Redmond, Washington
Abstract: We review results concerning edge flips in triangulations concentrating mainly on various aspects of the following question: Given two different triangulations of the same size, how many edge flips are necessary and sufficient to transform one triangulation into the other? We focus both on the combinatorial perspective (where only a combinatorial embedding of the graph is specified) and the geometric perspective (where the graph is embedded in the plane, vertices are points and edges are straight-line segments). We highlight some of the techniques used to prove the main results and mention a few of the challenges remaining in this area.
Bio sketch: Prosenjit Bose (http://jitbose.ca) received his B. Math (1990) and M. Math (1991) in Computer Science and Combinatorics from the University of Waterloo, Canada. He completed his Ph.D. (1994) in Computer Science at McGill University, in Montreal, where he received the D.W. Ambridge Award as the outstanding Ph.D. graduate. In 1995, he was a Killam/NSERC Postdoctoral Fellow at the University of British Columbia and in 1996 became an assistant professor in the department of Math and Computer Science at l'Université du Québec à Trois-Rivières. In 1997 he moved to Carleton University, in Ottawa, where he is now a Full Professor in the School of Computer Science. In 2010 he was appointed to the position of Associate Dean for Research and Graduate Studies in the Faculty of Science at Carleton. His research interests are in computational geometry (with applications to network routing, graph spanners, triangulations, manufacturing, G.I.S., pattern recognition, image processing), data structures, algorithm design and analysis, randomized algorithms, and graph theory. He has received several research and teaching awards, has published over 100 journal articles, has been a member of numerous scientific committees and has been invited to give guest lectures all over the world.
Abstract: The growing importance of network analysis has increased attention on interactive exploration to derive insights and support personal, business, legal, scientific, or national security decisions. Since networks are often complex and cluttered, strategies for effective filtering, clustering, grouping, and simplification are helpful in finding key nodes and links, surprising clusters, important groups, or meaningful patterns. We describe readability metrics and strategies that have been implemented in NodeXL, our free and open source network analysis tool, and show examples from our research. While filtering, clustering, and grouping have been used in many tools, we present several advances on these techniques. We also discuss our recent work on motif simplification, in which common patterns are replaced with compact and meaningful glyphs, thereby improving readability.
Bio sketch: Ben Shneiderman (http://www.cs.umd.edu/~ben) is a Professor in the Department of Computer Science and Founding Director (1983-2000) of the Human-Computer Interaction Laboratory (http://www.cs.umd.edu/hcil) at the University of Maryland. He is a Fellow of the AAAS, ACM, and IEEE, and a Member of the National Academy of Engineering in 2010.
Ben is the co-author with Catherine Plaisant of Designing the User Interface: Strategies for Effective Human-Computer Interaction (5th ed., 2010) http://www.awl.com/DTUI. With Stu Card and Jock Mackinlay, he co-authored Readings in Information Visualization: Using Vision to Think (1999). With Ben Bederson he co-authored The Craft of Information Visualization (2003). His book Leonardo’s Laptop (2002, MIT Press) won the IEEE book award for Distinguished Literary Contribution. His latest book, with Derek Hansen and Marc Smith, is Analyzing Social Media Networks with NodeXL (http://www.codeplex.com/nodexl, 2010).