November 14 – 19 , 2010, Dagstuhl Seminar 10461

Schematization in Cartography, Visualization, and Computational Geometry


Jason Dykes (City University – London, GB)
Matthias Müller-Hannemann (Martin-Luther-Universität Halle-Wittenberg, DE)
Alexander Wolff (Universität Würzburg, DE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]

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.


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
  • Networks


  • Information visualization
  • Geovisualization
  • Geographic information systems
  • Cartography
  • Graph drawing
  • VLSI layout
  • Underground mining
  • Cartographic generalization
  • Schematization
  • Building simplification
  • Orthogonal graph drawing
  • Octilinear layout
  • Schematic maps
  • Steiner trees
  • Minimum Manhattan networks
  • Boundary labeling.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.