Dagstuhl Seminar 13151
Drawing Graphs and Maps with Curves
( Apr 07 – Apr 12, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13151
Organizers
- Sara Irina Fabrikant (Universität Zürich, CH)
- Stephen Kobourov (University of Arizona - Tucson, US)
- Martin Nöllenburg (KIT - Karlsruher Institut für Technologie, DE)
- Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Impacts
- An Algorithmic Framework for Labeling Network Maps : article - Niedermann, Benjamin; Haunert, Jan-Henrik - Berlin : Springer, 2018. - 41 pp. - (Algorithmica ; 2018).
- An Algorithmic Framework for Labeling Network Maps : article in LNCS 9198 COCOON 2015 : pp. 689-700 - Haunert, Jan-Henrik; Niedermann, Benjamin - Berlin : Springer, 2014 - Lecture notes in computer science : 9198 ; article).
Schedule
Visualization of graphs and maps is a topic that spans several fields of science, humanities, and the arts. In some areas the visualization is used to explore a given data set, in other areas the focus is on designing efficient algorithms for effective visualizations, or in understanding how humans perceive and communicate with visualizations. The main goal of this seminar is to create an open-minded and inspiring forum that brings together researchers from diverse communities who share a common interest in drawing graphs and maps: Information Visualization, Graph Drawing, Cartography an GIS, Computational Geometry, Human-Computer Interaction, Cognitive Science and Psychology. In particular, we want to exchange ideas and initiate interdisciplinary collaborations along the common thread of using smooth curves, such as circular arcs or splines, instead of sequences of line segments to depict the edges of a graph or the boundaries of a map. Whereas artists and graphic designers frequently work with curves, most drawings of graphs and map features in GIS are still based on straight lines and polygons. Possible research questions to be addressed in the seminar range from how the aesthetic appeal of smooth curves translates into perceptual advantages or disadvantages for common graph and map reading tasks, to algorithmic problems for actually computing curved drawings with certain properties in theory and practice.
The format of the seminar will take into account the interdisciplinary nature and the different backgrounds of the participants, and will encourage interaction between the communities. During the first two days representatives of the different research communities will give overview talks to delineate the state-of-the-art in their fields and discuss the main open problems from their perspective. By the end of the second day, a set of open problems will be collected and working groups will form to work in depth on the selected topics. The remaining three days will have a flexible schedule dedicated to solving a set of identified research problems in groups, and presenting group status reports back to all participants in plenary format.
Additionally, we plan to organize an art exhibition with works contributed by workshop participants and solicited from artists, to stimulate and inspire discussions among the seminar participants.
The exhibition "Bending Reality: Where arc and science meet", organized by seminar participant Maxwell Roberts and organizers Martin Nöllenburg and Stephen Kobourov, opened during the seminar. Presenting information from a variety of contexts, the exhibit focuses on how designers have investigated the use of curves in order to show routes, structures, movement, time and connections.
The full digital exhibit is now available on the Dagstuhl web pages.
Graphs and networks, maps and schematic map representations are frequently used in many fields of science, humanities and the arts. The need for effective visualization and aesthetically pleasing design is attested by the numerous conferences and symposia on related topics, and a history that is several centuries old. From Mercator's maps dating to the 1500's, to interactive services such as Google Earth, geography and cartography have generated and solved many theoretical and practical problems in displaying spatial data effectively and efficiently. From Euler's visualization of the bridges of Königsberg in the 1700's, to Facebook's social networks, graph drawing has also proven a fertile area for theoretical and practical work. More recent is the notion of highly schematized maps and graphs, with the classic examples of statistical value-by-area cartograms by Raisz and Henry Beck's London Tube map, both dating back to the 1930's.
A key challenge in graph and cartographic visualization is designing cognitively useful spatial mappings of the underlying data that allow people to intuitively understand the displayed information. Such work draws on the intellectual history of several traditions, including information visualization, human-computer interaction, psychology, cognitive science, graphic design, cartography, and art. The synthesis of relevant ideas from these fields with new techniques can lead to new and better visualizations to help us keep pace with the torrents of data confronting us.
Although a great deal is known, both in theory and in practice, about drawing graphs and maps with straight-line segments, there are few corresponding results about circular-arc drawings in particular, and curve drawings in general. The use of circular arcs in place of straight-line segments opens a new chapter in drawing graphs and maps from both theoretical and practical points of view. Specifically, we are interested in the interplay between practical requirements of drawing with curves, arising in cartography and GIS, and theoretical results in computational geometry and graph drawing. Such work is motivated by perception research which indicates that representing paths with smooth geodesic trajectories aids in comprehension, as well as by the aesthetic appeal of smooth curves
Aims of the Seminar
The main goal of this seminar was to bring together researchers with interests in drawing graphs and maps with curves coming from information visualization, psychology, cognitive science, human-computer interaction, graph drawing, computational geometry, cartography, and GIS. It follows in a tradition of several previous similarly structured Dagstuhl seminars on graph drawing and map visualization. From April 7th to April 12th a group of 34 junior and senior researchers from eight different countries gathered in Dagstuhl. Being a small seminar with a target participation of 30 persons, the seminar was fully booked, which shows that this seemingly narrow topic still raises a lot of interest in the different communities. We all came together to discuss open research questions and engage in new collaborations around visualizations that replace straight lines with circular arcs and curves. This topic opens a great deal of theoretical and practical possibilities and with this in mind, the specific aims of the Dagstuhl seminar were:
- To learn about the state of the art of the use of curves in the different research areas. We invited a small number of survey lectures to define a common ground for interdisciplinary work.
- To organize an exhibition of art and visual designs on the common theme of curves contributed by participants and artists, and use this to stimulate discussion.
- To identify specific theoretical and practical open problems that need to be solved in order to make it possible to draw graphs and maps with circular arcs and curves.
- To form smaller working groups around some of the identified problems and to initiate a collaborative research process for finding answers and solutions to these problems.
- To report about the progress made in the working groups in a plenary session for getting feedback and further input from members of the other groups.
- To continue the joint research efforts beyond the seminar week and eventually publish those results.
Achievements of the Seminar
The achievements in the seminar were numerous and varied. The subsequent chapters of this report summarize the more important ones.
- On Monday and Tuesday, we enjoyed seven survey lectures; see Section Talks for the abstracts. David Eppstein opened with a broad overview of the use of curves in visualization of graphs and networks. Günter Rote talked about algorithms for approximating polygonal curves by simpler curves and sequences of biarcs. Sylvain Lazard illustrated connections with algebra and geometry when dealing with curves. Jo Wood surveyed the use of curves in cartography and information visualization. Helen Purchase discussed perception theories and empirical studies on the use of curves in visualization, and Maxwell Roberts discussed the question whether curvilinear metro maps have cognitive benefits over traditional straight-line schematic maps. Finally, Monique Teillaud and Michael Hemmer overviewed the history of the open source project CGAL, the Computational Geometry Algorithms Library, and then discussed specific CGAL packages that are relevant for drawing circular arcs and smooth algebraic curves. Beyond the survey and review talks, we also heard a presentation by Wouter Meulemans about the use of curved schematization of geometric shapes, where the results were obtained via a user study of the participants in the seminar.
- We also had two short impromptu presentations and software demos. In particular, Günter Rote presented an ipelet to transform polygons into splines in the drawing editor ipe. Jan-Henrik Haunert reported about work in progress and showed a demo on morphing polygonal lines so that edge lengths and angles behave as consistently as possible over time.
- A number of relevant open problems were formulated early in the seminar and six working groups formed around some of the problems. The groups then worked by themselves, formalizing and solving their specific theoretical and practical challenges. Section Working Groups contains the working group reports summarizing the problem and sketching the current progress made by the groups. Below is a list of the working group topics.
- Smooth Orthogonal Drawings: What is the complexity of recognizing whether a given 4-planar graph admits a smooth orthogonal drawing of edge complexity 1?
- Confluent Drawing: What is the complexity of determining whether a given graph has a so-called strict confluent drawing?
- Automated Evaluation of Metro Map Usability: What are good, objective, quantifiable criteria by which curvilinear metro maps can be evaluated? Can such criteria be used so that linear maps can likewise be compared both with each other and also with curvilinear maps?
- Universal Point Sets for Planar Graph Drawings with Circular Arcs: What can be said about universal point sets for drawing planar graphs if curves are used instead of straight-line segments?
- Labeling Curves with Curved Labels: How can points on a smooth curve be labeled automatically using curved labels?
- Graphs with Circular Arc Contact Representation: Which graphs can be represented by contacts of circular arcs?
The remaining open problems collected during the seminar are listed in Section Open Problems.
- We had an excellent exhibition entitled ``Bending Reality: Where Arc and Science Meet''; see Section Exhibition. This exhibition is the third one in a series of exhibitions that accompany Dagstuhl seminars where aesthetics and art are naturally part of the scientific topics. It was on display from April 8 to April 21, 2013. Moreover, for the first time in Dagstuhl history, this exhibition is made permanently available as a virtual exhibition that can be accessed at http://www.dagstuhl.de/ueber-dagstuhl/kunst/13151.
The last three days of the seminar were dedicated to working group efforts. Several of the groups kept their focus on the original problems as stated in the open problem session, while other groups modified and expanded the problems; see Section Working Groups. On the last day of the seminar we heard progress reports from all groups. We are expecting several research publications to result directly from the seminar.
Arguably the best, and most-appreciated, feature of the seminar was the opportunity to engage in discussion and interactions with experts in various fields with shared passion about curves. The aforementioned exhibition "Bending Reality" helped make the topics of the seminar more visible and raised new questions. In summary, we regard the seminar as a great success. From the positive feedback that we got it is our impression that the participants enjoyed the unique scientific atmosphere at Schloss Dagstuhl and profited from the scientific program. We are grateful for having had the opportunity to organize this seminar and thank the scientific, administrative, and technical staff at Schloss Dagstuhl. We also thank Benjamin Niedermann for helping us to put this report together.
References
- Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, and Martin Nöllenburg. Lombardi drawings of graphs. J. Graph Algorithms and Applications, 16(1):85–108, 2012.
Creative Commons BY 3.0 Unported license
Stephen G. Kobourov and Martin Nöllenburg and Monique Teillaud
- Patrizio Angelini (University of Rome III, IT) [dblp]
- Michael A. Bekos (National TU - Athens, GR) [dblp]
- David Eppstein (University of California - Irvine, US) [dblp]
- Fabrizio Frati (The University of Sydney, AU) [dblp]
- Eric Fusy (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Martin Gronemann (Universität Köln, DE) [dblp]
- Jan-Henrik Haunert (Universität Würzburg, DE) [dblp]
- Herman J. Haverkort (TU Eindhoven, NL) [dblp]
- Michael Hemmer (TU Braunschweig, DE) [dblp]
- Danny Holten (SynerScope BV, NL) [dblp]
- Michael Kaufmann (Universität Tübingen, DE) [dblp]
- Stephen Kobourov (University of Arizona - Tucson, US) [dblp]
- Sylvain Lazard (INRIA Lorraine - Nancy, FR) [dblp]
- Maarten Löffler (Utrecht University, NL) [dblp]
- Tamara Mchedlidze (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Wouter Meulemans (TU Eindhoven, NL) [dblp]
- Lev Nachmanson (Microsoft Corporation - Redmond, US) [dblp]
- Benjamin Niedermann (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Arlind Nocaj (Universität Konstanz, DE) [dblp]
- Martin Nöllenburg (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Sergey Pupyrev (University of Arizona - Tucson, US) [dblp]
- Helen C. Purchase (University of Glasgow, GB) [dblp]
- Andreas Reimer (Universität Heidelberg, DE) [dblp]
- Maxwell J. Roberts (University of Essex, GB) [dblp]
- Günter Rote (FU Berlin, DE) [dblp]
- André Schulz (Universität Münster, DE) [dblp]
- Aidan Slingsby (City University - London, GB) [dblp]
- Bettina Speckmann (TU Eindhoven, NL) [dblp]
- Monique Teillaud (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Torsten Ueckerdt (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Kevin Verbeek (University of California - Santa Barbara, US) [dblp]
- Alexander Wolff (Universität Würzburg, DE) [dblp]
- Jo Wood (City University - London, GB) [dblp]
- Kai Xu (Middlesex University - London, GB) [dblp]
Classification
- computer graphics / computer vision
- data structures / algorithms / complexity
- society / human-computer interaction
Keywords
- graph drawing
- computational geometry
- information visualization
- geovisualization
- cartography
- human-computer interaction
- cognition
- schematic maps
- graph theory
- geographic information systems
