Program
The list of accepted papers can be found here.
We will stream the invited talks, the business meeting and the talks (starting with Session 1) as scheduled below. You are also invited to join our Discord channel in parallel for discussions.
Link to Youtube stream.
Link to Discord channel.
The Best Video Award was won by Maarten Löffler and Martin Nöllenburg für their contribution "Labeling Nonograms".
Tuesday
- 10 – 11: Monique Teillaud: "Triangulations in CGAL: To Non-Euclidean Spaces... and Beyond!" [abstract] [slides]
- 11 – 12: Business meeting
- Local organizer report
- EuroCG 2021: St. Petersburg
- Bid for EuroCG 2022: Perugia
- Bid for EuroCG 2022: Prague
- There was a vote which decided in favor of Perugia. So Perugia will host EuroCG 2022.
- There was a straw vote regarding the question whether future editions of EuroCG should insist on full proofs (57 in favor) or shouldn't insist on full proofs (16 in favor). 9 abstained.
- 12 – 19:40: Streaming of contributed talks I (Sessions 1a–4b)
- 12:15: Session 1a: Routing
- 13:10: Session 1b: Trajectories and Curves
- 14:15: Session 2a: Matchings and Spanning Trees
- 14:50: Session 2b: Voronoi and Delaunay
- 15:15: Session 3a: Graph Drawing
- 16:20: Session 3b: Point Sets
- 17:25: Session 4a: Packing and Covering
- 18:10: Session 4b: Topology and Geometry
Wednesday
- 10 – 11: Maarten Löffler: "Location & Information" [abstract] [slides] [video]
- 11 – 15: Streaming of contributed talks II (Sessions 5a–7a)
- 11:00: Session 5a: Graph Algorithms
- 11:45: Session 5b: Polyominoes and Shapes
- 12:45: Session 6a: Similarity Measures
- 13:30: Session 6b: Polygons
- 14:20: Session 7a: Crossings and Scheduling
- 15 – 16: Erin Wolf Chambers: "Quantifying Shape Using the Medial Axis" [abstract] [slides] [video]
- 16 – 20: Streaming of contributed talks III (Sessions 7a–9b)
- 16:00: Session 7a: Crossings and Scheduling (continued)
- 16:50: Session 7b: Robots
- 17:30: Session 8a: Graph Representations and Schematization
- 18:15: Session 8b: Complexity and Combinatorics
- 18:40: Session 9a: Algorithm Engineering
- 19:15: Session 9b: Approximation Algorithms
- 20:00: EuroCG 2020 ends!
Thursday & Friday
The PhD School will also be streamed. The schedule can be found here.
Sessions
The (old) detailled program including the sessions can be seen below and can be downloaded as a pdf here. Papers presented by students have a green background. Registered workshop participants will be asked to vote for a Best Video Presentation Award via mail.
| Invited Talk 1 | |
| Triangulations in CGAL: To Non-Euclidean Spaces... and Beyond! [abstract] [slides] |
|
| Monique Teillaud | |
| Session 1a | Session 1b |
| Routing | Trajectories and Curves |
| Chair: Sabine Storandt [playlist] | Chair: Helmut Alt [playlist] |
| Expected Complexity of Routing in Theta6 and Half-Theta6 Graphs [paper] [slides] [video] |
Fréchet Distance Between Uncertain Trajectories: Computing Expected Value and Upper Bound [paper] [slides] [video] |
| Prosenjit Bose, Jean-Lou De Carufel and Olivier Devillers. | Kevin Buchin, Maarten Löffler, Aleksandr Popov and Marcel Roeloffzen. |
| Sometimes Reliable Spanners of Almost Linear Size [paper] [video] |
Probing a Set of Trajectories to Maximize Captured Movement [paper] [slides] [video] |
| Kevin Buchin, Sariel Har-Peled and Dániel Oláh. | Sándor Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph Mitchell, Ojas Parekh and Cynthia Phillips. |
| Headerless Routing in Unit Disk Graphs [paper] [slides] [video] |
Improved space bounds for Fréchet distance queries [paper] [video] |
| Wolfgang Mulzer and Max Willert. | Maike Buchin, Ivor van der Hoog, Tim Ophelders, Rodrigo Silveira, Lena Schlipf and Frank Staals. |
| Spanners for Transmission Graphs Using the Path-Greedy [paper] [slides] [video] |
Computing the cut distance of two curves [paper] [slides] [video] |
| Stav Ashur and Paz Carmi. | Maike Buchin, Leonie Ryvkin and Jerome Urhausen. |
| Local Routing in a Tree Metric 1-Spanner [paper] [slides] |
On the complexity of the middle curve problem [paper] [slides] [video] |
| Milutin Brankovic, Joachim Gudmundsson and André van Renssen. | Maike Buchin, Nicole Funk and Amer Krivosija. |
| Bitonicity of Euclidean TSP in Narrow Strips [paper] [slides] |
Homotopic Curve Shortening and the Affine Curve-Shortening Flow [paper] [slides] [video] |
| Henk Alkema, Mark de Berg and Sándor Kisfaludi-Bak. | Sergey Avvakumov and Gabriel Nivasch. |
| Session 2a | Session 2b |
| Matchings and Spanning Trees | Voronoi and Delaunay |
| Chair: Michael Hoffmann [playlist] | Chair: Wouter Meulemans [playlist] |
| The Very Best of Perfect Non-crossing Matchings [paper] [slides] |
On Implementing Multiplicatively Weighted Voronoi Diagrams [paper] [slides] [video] |
| Ioannis Mantas, Marko Savić and Hendrik Schrezenmaier. | Martin Held and Stefan de Lorenzo. |
| Augmenting Polygons with Matchings [paper] [slides] [video] |
On the Number of Delaunay Triangles occurring in all Contiguous Subsequences [paper] [slides] |
| Alexander Pilz, Jonathan Rollin, Lena Schlipf and André Schulz. | Stefan Funke and Felix Weitbrecht. |
| Disjoint tree-compatible plane perfect matchings [paper] [slides] [video] |
Flips in higher order Delaunay triangulations [paper] [slides] [video] |
| Oswin Aichholzer, Julia Obmann, Pavel Paták, Daniel Perz and Josef Tkadlec. | Elena Arseneva, Prosenjit Bose, Pilar Cano and Rodrigo I. Silveira. |
| A better approximation for longest noncrossing spanning trees [paper] [slides] [video] |
Diverse Voronoi Partitions of 1D Colored Points [paper] [video] |
| Sergio Cabello, Aruni Choudhary, Michael Hoffmann, Katharina Klost, Meghana M. Reddy, Wolfgang Mulzer, Felix Schröder and Josef Tkadlec. | Marc Van Kreveld, Bettina Speckmann and Jérôme Urhausen. |
| Session 3a | Session 3b |
| Graph Drawing | Point Sets |
| Chair: Sabine Cornelsen [playlist] | Chair: Maarten Löffler [playlist] |
| On the edge-length ratio of 2-trees [paper] [slides] [video] |
Holes and islands in random point sets [paper] [slides] [video*] |
| Václav Blažej, Jiří Fiala and Giuseppe Liotta. | Martin Balko, Manfred Scheucher and Pavel Valtr. |
| Monotone Arc Diagrams with few Biarcs [paper] [slides] [video] |
The Tree Stabbing Number is not Monotone [paper] [video] |
| Steven Chaplick, Henry Förster, Michael Hoffmann and Michael Kaufmann. | Johannes Obenaus and Wolfgang Mulzer. |
| Graph Planarity Testing with Hierarchical Embedding Constraints [paper] [slides] [video] |
Empty Rainbow Triangles in k-colored Point Sets [paper] [slides] [video] |
| Giuseppe Liotta, Ignaz Rutter and Alessandra Tappini. | Ruy Fabila-Monroy, Daniel Perz and Ana Laura Trujillo. |
| Rotational symmetric flexible placements of graphs [paper] [video] |
Minimum Convex Partition of Degenerate Point Sets is NP-Hard [paper] [slides] [video] |
| Sean Dewar, Georg Grasegger and Jan Legerský. | Nicolas Grelier. |
| Simple Topological Drawings of k-Planar Graphs [paper] [slides] [video] |
On Hard Instances of the Minimum-Weight Triangulation Problem [paper] [slides] [video] |
| Chih-Hung Liu, Csaba D Toth and Meghana M. Reddy. | Sándor Fekete, Andreas Haas, Yannic Lieder, Eike Niehs, Michael Perk, Victoria Sack and Christian Scheffer. |
| Business Meeting | |
| Invited Talk 2 | |
| Location & Information [abstract] [slides] [video] |
|
| Maarten Löffler | |
| Session 4a | Session 4b |
| Packing and Covering | Topology and Geometry |
| Chair: Lena Schlipf [playlist] | Chair: Bettina Speckmann [playlist] |
| Packing Squares into a Disk with Optimal Worst-Case Density [paper] [video] |
On the Average Complexity of the k-Level [paper] [slides] [video] |
| Sándor Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist and Christian Scheffer. | Man Kwun Chiu, Stefan Felsner, Manfred Scheucher, Patrick Schnider, Raphael Steiner and Pavel Valtr. |
| Worst-Case Optimal Covering of Rectangles by Disks [paper] [video] |
Topological Drawings meet Classical Theorems from Convex Geometry [paper] [slides] [video*] |
| Sándor Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer and Sahil Shah. | Helena Bergold, Stefan Felsner, Manfred Scheucher, Felix Schröder and Raphael Steiner. |
| Covering a set of line segments with a few squares [paper] [slides] |
Topologically correct PL-approximations of isomanifolds [paper] [video] |
| Joachim Gudmundsson, Mees van de Kerkhof, Andre van Renssen, Frank Staals, Lionov Wiratma and Sampson Wong. | Jean-Daniel Boissonnat and Mathijs Wintraecken. |
| Efficiently stabbing convex polygons and variants of the Hadwiger- Debrunner (p, q)-theorem [paper] [slides] [video] |
Enumerating isotopy classes of tilings of triply-periodic minimal surfaces [paper] [slides] [video] |
| Justin Dallant and Patrick Schnider. | Benedikt Kolbe and Myfanwy Evans. |
| Approximating the Packing of Unit Disks into Simple Containers [paper] [video] |
Geometric bistellar moves relate triangulations of Euclidean, hyperbolic and spherical manifolds [paper] [slides] [video] |
| Helmut Alt and Nadja Seiferth. | Tejas Kalelkar and Advait Phanse. |
| Smallest Universal Covers for Families of Triangles [paper] [slides] |
Weighted Epsilon-Nets [paper] [slides] [video] |
| Ji-won Park and Otfried Cheong. | Daniel Bertschinger and Patrick Schnider. |
| Session 5a | Session 5b |
| Graph Algorithms | Polyominoes and Shapes |
| Chair: André Schulz [playlist] | Chair: Benjamin Niedermann [playlist] |
| Edge Guarding Plane Graphs [paper] [slides] [video] |
Shape Formation in a Three-dimensional Model for Hybrid Programmable Matter [paper] [slides] [video] |
| Paul Jungeblut and Torsten Ueckerdt. | Kristian Hinnenthal, Dorian Rudolph and Christian Scheideler. |
| A polynomial-time partitioning algorithm for weighted cactus graphs [paper] [slides] [video] |
Labeling Nonograms [paper] [slides] [video] Best Video Award! |
| Maike Buchin and Leonie Selbach. | Maarten Löffler and Martin Nöllenburg. |
| Finding an Induced Subtree in an Intersection Graph is often hard [paper] [slides] [video] |
On Minimal-Perimeter Lattice Animals [paper] [slides] [video] |
| Hidefumi Hiraishi, Dejun Mao and Patrick Schnider. | Gill Barequet and Gil Ben-Shachar. |
| Balanced Independent and Dominating Sets on Colored Interval Graphs [paper] [slides] [video] |
Applications of Concatenation Arguments to Polyominoes and Polycubes [paper] [video] |
| Sujoy Bhore, Jan-Henrik Haunert, Fabian Klute, Guangping Li and Martin Nöllenburg. | Gill Barequet, Gil Ben-Shachar and Martha Osegueda. |
| Session 6a | Session 6b |
| Similarity Measures | Polygons |
| Chair: Sándor Fekete [playlist] | Chair: Linda Kleist [playlist] |
| Computing the Frechet distance of trees and graphs of bounded tree width [paper] [video] |
Targeted Drug Delivery: Advanced Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces [paper] [video] |
| Maike Buchin, Amer Krivosija and Alexander Neuhaus. | Aaron Becker, Sándor Fekete, Li Huang, Phillip Keldenich, Linda Kleist, Dominik Krupke, Christian Rieck and Arne Schmidt. |
| Between Two Shapes, Using the Hausdorff Distance [paper] [slides] [video] |
On the width of the monotone-visibility kernel of a simple polygon [paper] [video] |
| Marc van Kreveld, Till Miltzow, Tim Ophelders, Willem Sonke and Jordi Vermeulen. | David Orden, Leonidas Palios, Carlos Seara, Jorge Urrutia and Pawel Zylinski. |
| Scaling and compressing melodies using geometric similarity measures [paper] [video] |
Repulsion region in a simple polygon [paper] [video] |
| Luis Evaristo Caraballo de La Cruz, José-Miguel Díaz-Báñez, Fabio Rodríguez, Vanesa Sánchez-Canales and Inmaculada Ventura. | Arthur van Goethem, Irina Kostitsyna, Kevin Verbeek and Jules Wulms. |
| Distance Measures for Embedded Graphs - Optimal Graph Mappings [paper] [slides] [video] |
One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons [paper] [slides] [video] |
| Maike Buchin and Bernhard Kilgus. | Patrizio Angelini, Philipp Kindermann, Andre Löffler, Lena Schlipf and Antonios Symvonis. |
| Invited Talk 3 | |
| Quantifying Shape Using the Medial Axis [abstract] [slides] [video] |
|
| Erin Wolf Chambers | |
| Session 7a | Session 7b |
| Crossings and Scheduling | Robots |
| Chair: Birgit Vogtenhuber [playlist] | Chair: Frank Staals [playlist] |
| Simple Drawings of K_m,n Contain Shooting Stars [paper] [slides] [video] |
Connected Coordinated Motion Planning with Bounded Stretch [paper] [video] |
| Oswin Aichholzer, Alfredo García, Irene Parada, Birgit Vogtenhuber and Alexandra Weinberger. | Sándor Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck and Christian Scheffer. |
| Improved constant factor for the unit distance problem [paper] [slides] [video] |
Recognition and Reconfiguration of Lattice-Based Cellular Structures by Simple Robots [paper] [slides] [video] |
| Péter Ágoston and Dömötör Pálvölgyi. | Amira Abdel-Rahman, Aaron Becker, Daniel E. Biediger, Kenneth Cheung, Sándor Fekete, Benjamin Jenett, Eike Niehs, Christian Scheffer, Arne Schmidt and Mike Yanuzzi. |
| On the maximum number of crossings in star-simple drawings of K_n with no empty lens [paper] [slides] [video] |
Coordinated Particle Relocation Using Finite Static Friction with Boundary Walls [paper] [video] |
| Stefan Felsner, Michael Hoffmann, Kristin Knorr and Irene Parada. | Victor Baez, Aaron Becker, Sándor Fekete and Arne Schmidt. |
| The angular blowing-a-kiss problem [paper] [slides] [video] |
Scheduling drones to cover outdoor events [paper] [slides] |
| Kevin Buchin, Irina Kostitsyna, Roel Lambers and Martijn Struijs. | Oswin Aichholzer, Luis Evaristo Caraballo de La Cruz, José-Miguel Díaz-Báñez, Ruy Fabila-Monroy, Irene Parada, Inmaculada Ventura and Birgit Vogtenhuber. |
| The Complexity of Finding Tangles [paper] [slides] [video] |
Reconfiguring sliding squares in-place by flooding [paper] [video] |
| Oksana Firman, Stefan Felsner, Philipp Kindermann, Alexander Ravsky, Alexander Wolff and Johannes Zink. | Joel Moreno and Vera Sacristán. |
| Maximum Rectilinear Crossing Number of Uniform Hypergraphs [paper] [slides] [video] |
|
| Rahul Gangopadhyay and Saif Ayan Khan. | |
| Session 8a | Session 8b |
| Graph Representations and Schematization | Complexity and Combinatorics |
| Chair: Maike Buchin [playlist] | Chair: Elena Arseneva [playlist] |
| Representing Graphs by Polygons with Side Contacts in 3D [paper] [video] |
Smoothed Analysis of Resource Augmentation [paper] [video] |
| Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber and Alexander Wolff. | Jeff Erickson, Ivor van der Hoog and Till Miltzow. |
| Weak Unit Disk Contact Representations for Graphs without Embedding [paper] [slides] [video] |
The Multivariate Schwartz-Zippel Lemma [paper] [slides] |
| Jonas Cleve. | Mahmut Levent Doğan, Alperen Ergur, Elias Tsigaridas and Jake D. Mundo. |
| Tight Rectilinear Hulls of Simple Polygons [paper] [slides] [video] |
Colouring bottomless rectangles and arborescences [paper] [slides] [video] |
| Annika Bonerath, Jan-Henrik Haunert and Benjamin Niedermann. | Dömötör Pálvölgyi and Narmada Varadarajan. |
| Orthogonal Schematization with Minimum Homotopy Area [paper] [video] |
Computational Complexity of the α-Ham-Sandwich Problem [paper] [slides] [video] |
| Bram Custers, Jeff Erickson, Irina Kostitsyna, Wouter Meulemans, Bettina Speckmann and Kevin Verbeek. | Man Kwun Chiu, Aruni Choudhary and Wolfgang Mulzer. |
| Session 9a | Session 9b |
| Algorithm Engineering | Approximation Algorithms |
| Chair: Stefan Funke [playlist] | Chair: Rodrigo Silvera [playlist] |
| Computing Area-Optimal Simple Polygonalizations [paper] [slides] [video] |
Certified approximation algorithms for the Fermat point and k-ellipses [paper] [slides] [video] |
| Sándor Fekete, Andreas Haas, Phillip Keldenich, Michael Perk and Arne Schmidt. | Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland and Chee Yap. |
| Experimental Evaluation of Straight Skeleton Implementations Based on Exact Arithmetic [paper][slides] [video] |
A (1 + ε)-approximation for the minimum enclosing ball problem in R^d [paper] [slides] [video] |
| Günther Eder, Martin Held and Peter Palfrader. | Sang-Sub Kim and Barbara Schwarzwald. |
| On Generating Polygons: Introducing the Salzburg Database [paper] [slides] [video] |
Sparse Regression via Range Counting [paper] [video] |
| Günther Eder, Martin Held, Steinþór Jasonarson, Philipp Mayer and Peter Palfrader. | Jean Cardinal and Aurélien Ooms. |
| Invited Talk 4 (cancelled) | |
| The Saga of the Skyline Points [abstract] |
|
| Otfried Cheong | |
| Best Video Award & Closing |
|
* The password is "eurocg2020w".
Sponsors
