English Intern
Lehrstuhl für Informatik I - Algorithmen und Komplexität

Dr. Thomas van Dijk

Lehrstuhl für Informatik I
Universität Würzburg
Am Hubland
D-97074 Würzburg

Raum: 01.002, Gebäude M4

Tel.: +49 (0) 931-31-89040
Fax: +49 (0) 931-31-825200

Email: thomas.van.dijk@uni-wuerzburg.de

Twitter: @tvdmaps GitHub: tcvdijk
Youtube: YouTube    

Forschung

  • Algorithmically-guided user interaction
  • Algorithms for Geographic Information Systems
  • Implementation; computational experiments
  • Exact algorithms (exponential-time / parameterised ...)

Awards

  • 2. Platz aus 15 ($300), ACM SIGSPATIAL Cup 2018. For “Wüpstream: efficient enumeration of upstream features (GIS cup),’’ with Tobias Greiner, Bas den Heijer, Nadja Henning, Felix Klesen, and Andre Löffler.
  • Best Fast-forward Presentation at ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2018. For “Realtime linear cartograms and metro maps,” with Dieter Lutz.
  • Shortlist Junges Kolleg (Bayerische Akademie der Wissenschaften), Jahrgang 2017.
  • ACM Computing Review’s “Best of Computing” list of notable publications, 2016. For ”Matching Labels and Markers in Historical Maps: An Algorithm with
    Interactive Postprocessing,” with Benedikt Budig and Alexander Wolff.
  • Best Paper award, theory track, at the International Conference on Graph Drawing and Network Visualization. For “Block Crossings in Storyline Visualizations.” with Martin Fink, Norbert Fischer, Fabian Lipp, Peter Markfelder, Alex Ravsky, Subhash Suri, Alexander Wolff.
  • Best Poster Award Runners up at ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2015 (ACMGIS) for "There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points.with Lukas Beckmann, Benedikt Budig and Johannes Schamel.
  • Best Applied Paper Award at Discovery Science 2015 for "Active Learning for Classifying Template Matches in Historical Maps." [PDF] [ Videowith Benedikt Budig.
  • Best student contribution at Schematic Mapping 2014 for "An automated method for circular-arc metro maps." [PDFwith Arthur van Goethem and Wouter Meulemans.
  • Best paper at MapInteract 2014 for "Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing." with Benedikt Budig and Alexander Wolff.
  • Best Fast-forward Presentation and Runner-up Best Poster at ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems 2013 (ACMGIS) for "Accentuating Focus Maps via Partial Schematization." [PDF] with Arthur van Goethem, Jan-Henrik Haunert, Wouter Meulemans and Bettina Speckmann.
  • Best Short Presentation at Web and Wireless GIS 2013 (W2GIS) for "A Probabilistic Model for Road Selection in Mobile Maps" [PPT] with Jan-Henrik Haunert.

Betreuung

Doktorarbeit

Masterarbeit

  • Maximilian Schmitt: Tourenplanung unter Berücksichtigung heterogener Metriken.
  • Andre Löffler: Snapping Graph Drawings to the Grid
  • Benedikt Budig: Algorithmische Analyse historischer Landkarten
  • Dieter Lutz: Realtime Linear Cartograms using Least-Squares Optimisation

Bachelorarbeit

  • Fabian Sieper: Zuweisen von Kantenrichtungen in Metronetzen
  • Julian Walter: Rotation and scale invariant template matching for historical maps
  • Peter Markfelder: Optimale Zeichnungen von Storylines mit Blockkreuzungen
  • Martin Becker: String Matching von historischen Toponymen
  • Fabian Feitsch: From Many User-Contributed Polygons to One Polygon Consensus
  • Lukas Beckmann: Analyse von Umkehrpunkten auf GPS-Trajektorien unter Verwendung der Fréchet-Distanz

Lehrveranstaltungen

 

 

SS20 Vorlesung  Algorithmen für geographische Informationssysteme
  Seminar Algorithmen für Programmierwettbewerbe
WS19 Vorlesung Algorithmische Geometrie
SS19  Vorlesung  Algorithmen für geographische Informationssysteme
  Seminar Algorithmen für Programmierwettbewerbe
SS18 Vorlesung  Algorithmen für geographische Informationssysteme
  Seminar Visualisierung von Graphen
WS17 Vorlesung Exakte Algorithmen (vollständige Überarbeitung des Inhalts)
SS17  Vorlesung Algorithmen für geographische Informationssysteme
  Seminar Algorithmen für Programmierwettbewerbe (inkl. Konzeption)
WS16 Seminar Algorithmen zur Extraktion von Daten aus alten Landkarten
SS16 Vorlesung Algorithmen für geographische Informationssysteme
SS15 Vorlesung Algorithmen für geographische Informationssysteme
WS14  Seminar Visualisierung von geografischen Netzwerken
SS14  Vorlesung Algorithmen für geographische Informationssysteme
WS13  Übungen zu Approximationsalgorithmen
WS12  Übungen zu Algorithmen für geografische Informationssysteme
SS12  Übungen zu Exakte Algorithmen

Veröffentlichungen

2020[ to top ]
  • Bundled Crossings Revisited. Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; Park, Ji-Won; Ravsky, Alexander; Wolff, Alexander. In Journal of Graph Algorithms \& Applications, p. 35 pages. 2020.
2019[ to top ]
  • Algorithmically-Assisted Metro Map Design. van Dijk, Thomas C. In Proc. 2nd Schematic Mapping Workshop (SMW 2019), M. Roberts, M. Nöllenburg (eds.). 2019.
  • Bundled Crossings Revisited. Chaplick, Steven; van Dijk, Thomas C.; Kryven, Myroslav; won Park, Ji; Ravsky, Alexander; Wolff, Alexander. In 35th European Workshop on Computational Geometry (EuroCG 19). 2019.
  • Practical Topologically Safe Rounding of Geographic Networks. van Dijk, Thomas C.; Löffler, Andre. In Proceedings of the 27th {ACM} {SIGSPATIAL} International Conference on Advances in Geographic Information Systems, F. B. Kashani, G. Trajcevski, R. H. Güting, L. Kulik, S. D. Newsam (eds.), pp. 239–248. {ACM}, 2019.
2018[ to top ]
  • Stabbing Rectangles by Line Segments – How Decomposition Reduces the Shallow-Cell Complexity. Chan, Timothy M.; van Dijk, Thomas C.; Fleszar, Krzysztof; Spoerhase, Joachim; Wolff, Alexander. In Proc. 29th Ann. Int. Symp. Algorithms Comput. (ISAAC’18), Vol. 123 of LIPIcs, pp. 61:1–61:13. Schloss Dagstuhl -- Leibniz-Zentrum f{ü}r Informatik, 2018.
  • Realtime linear cartograms and metro maps. van Dijk, Thomas C.; Lutz, Dieter. In SIGSPATIAL/GIS, F. Banaei-Kashani, E. G. Hoel, R. H. Güting, R. Tamassia, L. Xiong (eds.), pp. 488–491. ACM, 2018.
  • Putting User Reputation on the Map: Unsupervised Quality Control for Crowdsourced Historical Data. Barz, Björn; van Dijk, Thomas C.; Spaan, Bert; Denzler, Joachim. In 2nd ACM SIGSPATIAL Workshop on Geospatial Humanities. 2018.
  • Aktives Lernen f{ü}r Informationsextraktion aus historischen Karten. van Dijk, Thomas C. In Flächennutzungsmonitoring X, Vol. 76 of IOER, G. Meinel, U. Schumacher, M. Behnisch, T. Kr{ü}ger (eds.), pp. 181–186. RHOMBOS, 2018.
  • Wüpstream: efficient enumeration of upstream features (GIS cup). van Dijk, Thomas C.; Greiner, Tobias; den Heijer, Bas; Henning, Nadja; Klesen, Felix; Löffler, Andre. In SIGSPATIAL/GIS, F. Banaei-Kashani, E. G. Hoel, R. H. Güting, R. Tamassia, L. Xiong (eds.), pp. 626–629. ACM, 2018.
2017[ to top ]
  • Algorithmically-Guided User Interaction. van Dijk, Thomas C.; Wolff, Alexander. In SIGSPATIAL’17 Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, E. Hoel, S. D. Newsam, S. Ravada, R. Tamassia, G. Trajcevski (eds.), pp. 11:1–11:4. ACM, 2017.
  • Journeys of the Past: A Hidden Markov Approach to Georeferencing Historical Itineraries. Budig, Benedikt; van Dijk, Thomas C. In GIR’17 Proceedings of the 11th Workshop on Geographic Information Retrieval, C. B. Jones, R. S. Purves (eds.), pp. 7:1–7:10. ACM, 2017.
  • Computing Storyline Visualizations with Few Block Crossings. van Dijk, Thomas C.; Lipp, Fabian; Markfelder, Peter; Wolff, Alexander. In Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization, F. Frati; K.-L. Ma (eds.). 2017.
  • Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alexander; Suri, Subhash; Wolff, Alexander. In Journal of Graph Algorithms \& Applications, 21(5), Y. Hu; M. Nöllenburg (eds.), pp. 873–913. 2017.
2016[ to top ]
  • Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing. Budig, Benedikt; van Dijk, Thomas C.; Wolff, Alexander. In Transactions on Spatial Algorithms and Systems. 2016.
  • Block Crossings in Storyline Visualizations. van Dijk, Thomas C.; Fink, Martin; Fischer, Norbert; Lipp, Fabian; Markfelder, Peter; Ravsky, Alex; Suri, Subhash; Wolff, Alexander. In Proc. 24nd Int. Sympos. Graph Drawing. 2016.
  • Glyph Miner: A System for Efficiently Extracting Glyphs from Early Prints in the Context of OCR. Budig, Benedikt; van Dijk, Thomas C.; Kirchner, Felix. In Proceedings of the 16th ACM/IEEE-CS on Joint Conference on Digital Libraries, of JCDL ’16, N. R. Adam, L. (Boots) Cassel, Y. Yesha, R. Furuta, M. C. Weigle (eds.), pp. 31–34. ACM, 2016.
  • Snapping Graph Drawings to the Grid Optimally. Löffler, Andre; van Dijk, Thomas C.; Wolff, Alexander. In Proc. 24nd Int. Sympos. Graph Drawing. 2016.
  • Location-dependent generalization of road networks based on equivalent destinations. van Dijk, Thomas C.; Haunert, Jan-Henrik; Oehrlein, Johannes. In Comput. Graph. Forum, 35(3), pp. 451–460. 2016.
2015[ to top ]
  • There and Back Again: Using Fréchet-Distance Diagrams to Find Trajectory Turning Points. Beckmann, Lukas; Budig, Benedikt; van Dijk, Thomas C.; Schamel, Johannes. In Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015), pp. 238–241. ACM, 2015.
  • Active Learning for Classifying Template Matches in Historical Maps. Budig, Benedikt; Dijk, Thomas C. van. In Discovery Science, Vol. 9356 of Lecture Notes in Computer Science, N. Japkowicz, S. Matwin (eds.), pp. 33–47. Springer International Publishing, 2015.
2014[ to top ]
  • Interactive focus maps using least-squares optimization. van Dijk, Thomas C.; Haunert, Jan-Henrik. In International Journal of Geographical Information Science, 28(10), pp. 2052–2075. 2014.
  • Improved Approximation Algorithms for Box Contact Representations. Bekos, Michael A.; van Dijk, Thomas C.; Fink, Martin; Kindermann, Philipp; Kobourov, Stephen G.; Pupyrev, Sergey; Spoerhase, Joachim; Wolff, Alexander. In Proc. 22th Annual European Symposium on Algorithms (ESA’14), pp. 87–99. 2014.
  • Matching Labels and Markers in Historical Maps: an Algorithm with Interactive Postprocessing. Budig, B.; van Dijk, T. C.; Wolff, A. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on MapInteraction. 2014.
  • Map Schematization with Circular Arcs. van Dijk, Thomas C.; van Goethem, Arthur; Haunert, Jan-Henrik; Meulemans, Wouter; Speckmann, Bettina. In Geographic Information Science, 8728, M. Duckham; E. Pebesma; K. Stewart; A. Frank (eds.), pp. 1–17. Springer International Publishing, 2014.
  • An Automated Method for Circular-Arc Metro Maps. van Dijk, T. C.; van Goethem, A.; Haunert, J.H.; Meulemans, W.; Speckmann, B. In Schematic Mapping. 2014.
  • How to Eat a Graph: Computing Selection Sequences for the Continuous Generalization of Road Networks. Chimani, M.; van Dijk, T. C.; Haunert, J.-H. In Proceedings of the 22st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Vol. 28, pp. 243–252. 2014.
  • Inclusion/Exclusion Meets Measure and Conquer. Nederlof, Jesper; van Rooij, Johan M.M.; van Dijk, Thomas C. In Algorithmica, 69(3), pp. 685–740. Springer US, 2014.
2013[ to top ]
  • Accentuating Focus Maps via Partial Schematization. van Dijk, Thomas C.; van Goethem, Arthur; Haunert, Jan-Henrik; Meulemans, Wouter; Speckmann, Bettina. In Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, of SIGSPATIAL’13, pp. 428–431. ACM, Orlando, Florida, 2013.
  • Road Segment Selection with Strokes and Stability. van Dijk, T. C.; Fleszar, K.; Haunert, J.-H.; Spoerhase, J. In Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction, of MapInteract ’13, pp. 72–77. ACM, Orlando, Florida, 2013.
  • A Probabilistic Model for Road Selection in Mobile Maps. van Dijk, Thomas C.; Haunert, Jan-Henrik. In Web and Wireless Geographical Information Systems, Vol. 7820, S. H. Liang, X. Wang, C. Claramunt (eds.), pp. 214–222. Springer Berlin Heidelberg, 2013.
2011[ to top ]
  • Optimizing Wireless Sensor Network Flow by Column Generation. van den Akker, J. M.; van Dijk, T. C.; Hoogeveen, J. A.; Toorop, T. In Conference of the European Chapter on Combinatorial Optimization. 2011.
2010[ to top ]
  • A Cubic Kernel for Feedback Vertex Set and Loop Cutset. Bodlaender, HansL.; van Dijk, ThomasC. In Theory of Computing Systems, 46(3), pp. 566–597. Springer-Verlag, 2010.
2009[ to top ]
  • Inclusion/Exclusion Meets Measure and Conquer. van Rooij, Johan M. M.; Nederlof, Jesper; van Dijk, Thomas C. In Algorithms - ESA 2009, Vol. 5757, A. Fiat, P. Sanders (eds.), pp. 554–565. Springer Berlin Heidelberg, 2009.
2008[ to top ]
  • Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint. Bodlaender, Hans; Tan, Richard; van Dijk, Thomas C.; van Leeuwen, Jan. In Algorithm Theory - SWAT 2008, Vol. 5124, J. Gudmundsson (ed.), pp. 102–113. Springer Berlin / Heidelberg, 2008.
2007[ to top ]
  • Kernelization for Loop Cutset. van Dijk, T. C. M. D. Edwin de Jong (ed.). 2007.