November 14 – 19 , 2010, Dagstuhl Seminar 10461
Schematization in Cartography, Visualization, and Computational Geometry
For support, please contact
Exhibition: Underground Maps Unravelled
|The exhibition "Underground Maps Unravelled: Explorations in Information Design" by seminar participant Maxwell Roberts (University of Essex) opens during the seminar. Using the London Underground and other networks as testbeds, it will explore how the chosen rules and design priorities can influence the appearance and usability of schematic network maps.|
Preliminary List of Participants
The list of participants will be updated regularly only eight weeks before the seminar.
In this seminar, we were interested in computing the layout of complex networks under angular restrictions. We refer to this problem as angular schematization and subsume under it also the combined effort of network construction and layout. It is striking that edge directions are being restricted in networks of very different nature and that these networks are constructed in very different communities: graph drawing, information visualization, geographic information science, computational geometry, very-large-scale-integrated circuit (VLSI) layout, and underground mining. In some of these communities (such as graph drawing or VLSI layout), rectilinear connections have a long history, but recently octilinear connections have moved into the spotlight, bringing with them completely new problems and challenges. In other fields of application such as underground mining, it is not the number of slopes that is restricted, but there is an upper bound on the maximum slope.
We believed that it was high time for these communities to meet and to exchange problems and ideas. For example, the drawing of subway maps has been discussed independently in graph drawing, information visualization, and GIS. Manhattan networks are constructed by operations researchers and computational geometers. Octilinear connections are used when drawing subway maps, but also in the new X-architecture in VLSI layout.
We wanted to bring together researchers from different communities that all have to do with (angular) schematization but have little overlap otherwise. These communities have different backgrounds, literature, and histories. Therefore, we needed a forum where we could spend time learning from each other, transferring knowledge and developing common or at least translatable language. This was a difficult process and took time, but Dagstuhl provided an excellent environment for this kind of activity.
One of the key workshop objectives was to ``develop a common language'' across communities. This is difficult to achieve, and even the identification of ``open problems'' and the use of a problem-led approach drew attention to the different approaches and expectations of groups from the participating disciplines.
The beauty of Dagstuhl is that it provided a means of enabling colleagues from different disciplines and with different backgrounds and expectations to communicate and share perspectives: whether in an ``open problem'' description, an ``open mic'' demonstration of work in progress, or during a game of table tennis!
Lots of knowledge about how the different groups operate was shared... along with many suggestions of work relating to some of the approaches and open problems. The Dagstuhl library proved to be an excellent source of information to support this activity.
In summary, we did manage to get people from different communities to contribute to the groups in which open problems were discussed... certainly in some cases. Those with backgrounds in disciplines that do not have a tradition of working in this way tended to move between groups -- meaning that groups were able to both focus on the problem in hand and benefit from a range of perspectives, whilst these individuals were able to sample the scope of problems being addressed and apply their knowledge in diverse contexts.
There was some ``retreat'' in a few cases, where participants with shared background focused on known and specific problems. But even here some sharing of knowledge, approaches and understanding took place, particularly through the intermittent participation of ``floating'' group members, the stimulating ``open mic'' sessions, informal discussion during the very useful breaks and the plenary reporting. And some of this intra-disciplinary effort may be beneficial to the wider community -- involving, for example, members of a single discipline identifying the need to describe and communicate established knowledge within their domain more widely.
Undeniably, those who participated in the meeting acquired valuable knowledge, new perspectives and insights into the ways in which domains relating to their own discipline operate. New and lasting contacts were forged as ideas were shared and understanding of the similarities and differences between subject areas and their associated approaches were established.
- Data Structures / Algorithms / Complexity
- Information visualization
- Geographic information systems
- Graph drawing
- VLSI layout
- Underground mining
- Cartographic generalization
- Building simplification
- Orthogonal graph drawing
- Octilinear layout
- Schematic maps
- Steiner trees
- Minimum Manhattan networks
- Boundary labeling.