Dagstuhl Seminar 10461
Schematization in Cartography, Visualization, and Computational Geometry
( Nov 14 – Nov 19, 2010 )
Permalink
Organizers
- Jason Dykes (City University - London, GB)
- Matthias Müller-Hannemann (Martin-Luther-Universität Halle-Wittenberg, DE)
- Alexander Wolff (Universität Würzburg, DE)
Contact
Press/News
Impacts
- Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve : article : pp. 1036-1041 - Chepoi, Victor; Felsner, Stefan - (Computational geometry : 46. 2013, 9).
- Boundary-labeling algorithms for panorama images : article : pp. 289-298 - Gemsa, Andreas; Haunert, Jan-Henrik; Nöllenburg, Martin - New York : ACM, 2011 - (GIS 11 : Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems : article ).
- Computing cartograms with optimal complexity : article in SoCG 2012 : pp. 21-30 - Alam, Muhammad Jawaherul; Biedl, Therese; Felsner, Stefan; Kaufmann, Michael; Kobourov, Stephen G.; Ueckerdt, Torsten - New York : ACM, 2012. - pp. 21-30 - Proceedings of the 2012 symposuim on Computational Geometry. ISBN: 978-1-4503-1299-8.
- Drawing Metro Maps Using Bezier Curves : article : pp. 463-474 - Fink, Martin; Haverkort, Herman; Nöllenburg, Martin; Roberts, Maxwell J.; Schuhmann, Julian; Wolff, Alexander - Berlin : Springer, 2012 - ((Lecture notes in computer science : 7704 : article).
- Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations : article in LNCS 7074 - Alam, Muhammad Jawaherul; Biedl, Therese; Felsner, Stefan; Gerasch, Andreas; Kaufmann, Michael; Kobourov, Stephen G. - Berlin : Springer, 2012. - pp. 281-291 - (Lecture notes in computer science : 7074 ; pp. 281-291). ISBN: 978-3-642-25591-5.
- Linear-Time Algorithms for Proportional Contact Graph Representations - Alam, Muhammad J.; Biedl, Therese; Felsner, Stefan; Gerasch, Andreas; Kaufmann, Michael; Kobourov, Stephen G. - Waterloo : University, 2011. - 15 pp. - (Technical Report / Waterloo / Cheriton School of Computer Science ; 2011-19).
- Proportional Contact Representations of Planar Graphs : article in LNCS 7034 - Alam, Muhammad Jawaherul; Biedl, Therese; Felsner, Stefan; Kaufmann, Michael; Kobourov, Stephen G. - Berlin : Springer, 2012. - pp. 26-38 - (Lecture notes in computer science : 7034 ; pp. 26-38). ISBN: 978-3-642-25878-7 / 3-642-25878-6.
- Vertex angle and crossing angle resolution of leveled tree drawings : pp. 630-635 - Didimo, Walter; Kaufmann, Michael; Liotta, Giuseppe; Okamoto, Yoshio; Spillner, Andreas - Amsterdam : Elsevier, 2012 - (Information Processing Letters : 112. 2012, 16 : pp- 630-635).
Schedule
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.
- Silvania Avelar (Empa-Akademie - Zürich, CH)
- Therese Biedl (University of Waterloo, CA) [dblp]
- Marcus Brazil (The University of Melbourne, AU)
- Victor Chepoi (Aix-Marseille University, FR)
- Walter Didimo (University of Perugia, IT) [dblp]
- Jürgen Döllner (Hasso-Plattner-Institut - Potsdam, DE)
- Jason Dykes (City University - London, GB) [dblp]
- Peter Eades (The University of Sydney, AU) [dblp]
- Stefan Felsner (TU Berlin, DE) [dblp]
- Martin Fink (Universität Würzburg, DE) [dblp]
- David Forrest (Univ. of Glasgow - Glasgow, GB)
- Emden R. Gansner (AT&T Labs Research - Florham Park, US) [dblp]
- Jan-Henrik Haunert (Universität Würzburg, DE) [dblp]
- Herman J. Haverkort (TU Eindhoven, NL) [dblp]
- Seok-Hee Hong (The University of Sydney, AU) [dblp]
- Christophe Hurter (ENAC - Toulouse, FR) [dblp]
- Michael Kaufmann (Universität Tübingen, DE) [dblp]
- Christian Knauer (Universität Bayreuth, DE) [dblp]
- Stephen Kobourov (University of Arizona - Tucson, US) [dblp]
- Marcus Krug (KIT - Karlsruher Institut für Technologie, DE)
- Giuseppe Liotta (University of Perugia, IT) [dblp]
- Anna Lubiw (University of Waterloo, CA) [dblp]
- William A. Mackaness (University of Edinburgh, GB)
- Wouter Meulemans (TU Eindhoven, NL) [dblp]
- Matthias Müller-Hannemann (Martin-Luther-Universität Halle-Wittenberg, DE) [dblp]
- Martin Nöllenburg (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Yoshio Okamoto (JAIST, JP) [dblp]
- Andreas Reimer (GFZ Potsdam, DE) [dblp]
- Maxwell J. Roberts (University of Essex, GB) [dblp]
- Peter Rodgers (University of Kent, GB) [dblp]
- Ignaz Rutter (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Jörg-Rüdiger Sack (Carleton University - Ottawa, CA) [dblp]
- Heiko Schilling (TomTom International - Amsterdam, NL) [dblp]
- Falko Schmid (Universität Bremen, DE)
- Takeshi Shirabe (KTH Royal Institute of Technology, SE)
- Bettina Speckmann (TU Eindhoven, NL) [dblp]
- Andreas Spillner (Universität Greifswald, DE)
- He Sun (MPI für Informatik - Saarbrücken, DE) [dblp]
- Alexandru C. Telea (University of Groningen, NL) [dblp]
- Marc van Kreveld (Utrecht University, NL) [dblp]
- Jarke J. van Wijk (TU Eindhoven, NL) [dblp]
- Mark Ware (University of Glamorgan, GB)
- Alexander Wolff (Universität Würzburg, DE) [dblp]
- Jo Wood (City University - London, GB) [dblp]
- Martin Zachariasen (University of Copenhagen, DK)
- Qiuju Zhang (University of Twente, NL)
Classification
- Data structures / algorithms / complexity
- Networks
Keywords
- 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.