This seminar is offered for students enrolled in the Mathematics Master as module S4C1 as well as students enrolled in the Computer Science Master as module MA-INF 1205. The full title of the module is Graduate Seminar Discrete Optimization – Abstract Voronoi Diagrams and Planar Distance Oracles. The seminar is organized and held by Prof. Dr. Anne Driemel.

The goal of the seminar is for each participant to:

• Study a scientific paper (see references below)
• Present the main ideas of the paper in a talk (45 Minutes)
• Participate in discussions on the topic of the seminar
• Submit a written report (in own words) (10 pages)

The first meeting for the seminar will take on Friday October 15, 2021, at 2:15 pm in room 2.050 (Informatik V, 2. OG) . The meeting room is located in the computer science building at Friedrich Hirzebruch Allee 8. The assignment of topics and the schedule of talks will be decided in or shortly after the first meeting. If you are interested to participate in the seminar and want to receive updates, please contact Prof. Dr. Anne Driemel. There is also a course page in eCampus.

The topic of the seminar is centered around abstract Voronoi diagrams and how they can be used to obtain better distance oracles for planar graphs. A distance oracle is a data structure that stores a graph and that can answer queries for the shortest path distance between vertices. In general, for any data structure, we are interested in the preprocessing time, space and the query time that is achieved by the data structure. For distance oracles, this question is also related to fundamental graph questions, such as, how fast can we compute the diameter of a graph. Recent complexity theoretic result suggest that this problem cannot be solved in strongly subquadratic time in the number of vertices of the graph. In this seminar we will take a closer look at some recent results that make use of abstract Voronoi diagrams. This approach was first suggested by Cabello in 2017. Abstract Voronoi diagrams have been known much longer. They were introduced by Klein in 1987.

1. Rolf Klein, Elmar Langetepe, and Zahra Nilforoushan. “Abstract Voronoi diagrams revisited.” Computational Geometry 42.9 (2009): 885-902.
2. Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004–1022, 1987.
3. Cabello, Sergio, and Erin W. Chambers. “Multiple source shortest paths in a genus g graph.” Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. 2007.
4. Cabello, Sergio. “Many distances in planar graphs.” Algorithmica 62.1 (2012): 361-381.
5. Timothy M. Chan. 2012. All-pairs shortest paths for unweighted undirected graphs in o(mn) time. ACM Trans. Algorithms 8, 4, Article 34 (September 2012), 17 pages.
6. Arge, Lars, Freek van Walderveen, and Norbert Zeh. “Multiway simple cycle separators and I/O-efficient algorithms for planar graphs.” Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2013.
7. Sergio Cabello. “Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs.” ACM Transactions on Algorithms (TALG) 15.2 (2018): 1-38.
8. Cohen-Addad, Vincent, Søren Dahlgaard, and Christian Wulff-Nilsen. “Fast and compact exact distance oracle for planar graphs.” 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.
9. Paweł Gawrychowski, Shay Mozes, Oren Weimann, and Christian Wulff-Nilsen. “Better tradeoffs for exact distance oracles in planar graphs.” Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.
10. Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. “Almost optimal distance oracles for planar graphs.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019.
11. Long, Yaowei, and Seth Pettie. “Planar Distance Oracles with Better Time-Space Tradeoffs.” Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2021.
12. Oren Weimann and Raphael Yuster. 2015. Approximating the Diameter of Planar Graphs in Near Linear Time. ACM Trans. Algorithms 12, 1, Article 12 (February 2016), 13 pages.
13. Chan, Timothy M., and Dimitrios Skrepetos. “Faster approximate diameter and distance oracles in planar graphs.” Algorithmica 81.8 (2019): 3075-3098.
14. David Eppstein, “Subgraph Isomorphism in planar graphs and related problems”, Journal of Graph Algorithms and Applications, vol. 3, no. 3, pp. 1–27 (1999).