Information

Welcome Reception

There is a welcome reception on Tuesday, March 20, starting at 18:00. It takes place at the conference venue (Takustr. 9, 14195 Berlin).

Registration

The registration desk is open during the welcome reception and the whole conference. In the morning it will open shortly before the conference starts.

Social event

If you chose to participate in the social event please make sure to bring warm and weather-proof clothing as the event takes place outside.

Schedule

Wednesday, March 21 Thursday, March 22 Friday, March 23
8:45–9:00 Welcome talk    
9:00–10:00 Session 1 (Invited Talk) 9:00–10:00 Session 5 (Invited Talk) 9:00–10:00 Session 8 (Invited Talk)
10:00–10:35 Fast Forward Session 10:00–10:20 Fast Forward Session 10:00–10:25 Fast Forward Session
10:35–11:05 Coffee Break 10:20–10:50 Coffee Break 10:25–10:50 Coffee Break
11:05–12:30 Sessions 2A and 2B 10:50–12:15 Sessions 6A and 6B 10:50–12:15 Sessions 9A and 9B
12:30–13:30 Lunch 12:15–13:30 Lunch 12:15–13:20 Lunch
13:30–14:55 Sessions 3A and 3B 13:30–14:55 Sessions 7A and 7B 13:20–15:00 Sessions 10A and 10B
14:55–15:20 Coffee Break 15:00–18:30 Social Event 15:00–15:30 Coffee Break
15:20–17:00 Sessions 4A and 4B  
17:05–18:00 Business Meeting 19:00–24:00 Conference Dinner

Sessions

The proceedings are available.

A collection of short abstracts is available to navigate the talks (version: 2018-03-14). Hardcopies of the short abstract booklet will be distributed at the conference.

Day 1 – Wednesday, March 21

Session 1 (invited talk) – Chair: Helmut Alt
Rigidity and Deformation
Nina Amenta
Session 2A – Chair: Rodrigo Silveira Session 2B – Chair: André van Renssen
Agglomerative Clustering of Growing Squares Altitude Terrain Guarding and Guarding Uni-Monotone Polygons
Thom Castermans, Bettina Speckmann, Frank Staals and Kevin Verbeek. Stephan Friedrichs, Valentin Polishchuk and Christiane Schmidt.
Combinatorial and Asymptotical Results on the Neighborhood Grid Data Structure Maximal Two-Guard Walks in a Polygon
Martin Skrodzki, Ulrich Reitebuch, Konrad Polthier and Shagnik Das. Franz Aurenhammer, Michael Steinkogler and Rolf Klein.
A Framework for Algorithm Stability and its Application to Kinetic Euclidean MSTs Combinatorics of Beacon-based Routing in Three Dimensions
Wouter Meulemans, Bettina Speckmann, Kevin Verbeek and Jules Wulms. Jonas Cleve and Wolfgang Mulzer.
Balanced Dynamic Loading and Unloading On Romeo and Juliet Problems: Minimizing Distance-to-Sight
Sándor Fekete, Sven von Höveling, Joseph Mitchell, Christian Rieck, Christian Scheffer, Arne Schmidt and James Zuber. Fabian Stehn, Hee-Kap Ahn, Eunjin Oh, Lena Schlipf and Darren Strash.
Approximate stabbing queries with sub-logarithmic local replacement. Guarding Monotone Polygons with Vertex Half-Guards is NP-Hard
Ivor Hoog V.D. and Maarten Löffler. Matt Gibson, Erik Krohn and Matthew Rayford.
Session 3A – Chair: Christiane Schmidt Session 3B – Chair: Maike Buchin
Data Gathering in Faulty Sensor Networks Using a Mule Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality
Stav Ashur. Andreas Haas.
Computing optimal shortcuts for networks The hardness of Witness puzzles
Delia Garijo, Alberto Márquez, Natalia Rodríguez and Rodrigo Silveira. Irina Kostitsyna, Maarten Löffler, Max Sondag, Willem Sonke and Jules Wulms.
Protecting a highway from fire A Fully Polynomial Time Approximation Scheme For the Smallest Diameter of Imprecise Points
Rolf Klein, David Kübel, Elmar Langetepe and Barbara Schwarzwald. Vahideh Keikha, Maarten Löffler and Ali Mohades.
Shape Recognition by a Finite Automaton Robot Properties of Minimal-Perimeter Polyominoes
Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph and Christian Scheideler. Gill Barequet and Gil Ben-Shachar.
Beam It Up, Scotty: Angular Freeze-Tag with Directional Antennas Short Plane Support Trees for Hypergraphs
Sándor Fekete and Dominik Krupke. Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg and Xiaoru Yuan.
Session 4A – Chair: Fabian Stehn Session 4B – Chair: Mikkel Abrahamsen
Maximizing Ink in Symmetric Partial Edge Drawings of k-plane Graphs Subquadratic Encodings for Point Configurations
Michael Höller, Fabian Klute, Soeren Nickel, Martin Nöllenburg and Birgit Schreiber. Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman and Aurélien Ooms.
The Partition Spanning Forest Problem Almost-equidistant sets
Philipp Kindermann, Boris Klemz, Ignaz Rutter, Patrick Schnider and André Schulz. Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel and Pavel Valtr.
Convexity-Increasing Morphs of Planar Graphs Minimal Geometric Graph Representations of Order Types
Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals and Darren Strash. Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber and Emo Welzl.
Efficient Algorithms for Ortho-Radial Graph Drawing A Note on Planar Monohedral Tilings
Benjamin Niedermann, Ignaz Rutter and Matthias Wolf. Oswin Aichholzer, Michael Kerber, Istvan Talata and Birgit Vogtenhuber.
Automatic Drawing for Tokyo Metro Map Computing Crossing-Free Configurations with Minimum Bottleneck
Masahiro Onda, Masaki Moriguchi and Keiko Imai. Sándor Fekete and Phillip Keldenich.
On the Weak Line Cover Number A Note on Flips in Diagonal Rectangulations
Oksana Firman, Alexander Ravsky and Alexander Wolff. Jean Cardinal, Vera Sacristán and Rodrigo Silveira.

Day 2 – Thursday, March 22

Session 5 (invited talk) – Chair: Wolfgang Mulzer
Online Competitive Routing on Delaunay Triangulations and their Variants
Prosenjit Bose
Session 6A – Chair: Kevin Buchin Session 6B – Chair: Elena Khramtcova

Optimal Algorithms for Compact Linear Layouts

A New Lower Bound on the Maximum Number of Plane Graphs using Production Matrices
Wouter Meulemans, Willem Sonke, Bettina Speckmann, Eric Verbeek and Kevin Verbeek. Clemens Huemer, Alexander Pilz and Rodrigo Silveira.
Drawing Connected Planar Clustered Graphs on Disk Arrangements Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter and Nina Zimbel. Bahareh Banyassady, Luis Barba and Wolfgang Mulzer.
Augmenting a tree to a k-arbor-connected graph with pagenumber k Bottleneck Bichromatic Non-crossing Matchings using Orbits
Toru Hasunuma. Marko Savić and Milos Stojakovic.
1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area A combinatorial measure of closeness in point sets
Steven Chaplick, Fabian Lipp, Alexander Wolff and Johannes Zink. Patrick Schnider and Alexander Pilz.
NP-Completeness of Max-Cut for Segment Intersection Graphs Rollercoasters: Long Sequences without Short Runs
Oswin Aichholzer, Wolfgang Mulzer, Patrick Schnider and Birgit Vogtenhuber. Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka and Jeffrey Shallit.
Session 7A – Chair: Evanthia Papadopoulou Session 7B – Chair: Vera Sacristan
The Topology of Skeletons and Offsets Group Diagrams for Representing Trajectories
Stefan Huber. Maike Buchin and Bernhard Kilgus.
On Merging Straight Skeletons The k-Fréchet distance of polygonal curves
Franz Aurenhammer and Michael Steinkogler. Maike Buchin and Leonie Ryvkin.
Coxeter triangulations have good quality Progressive Simplification of Polygonal Curves
Siargey Kachanovich, Mathijs Wintraecken and Aruni Choudhary. Kevin Buchin, Maximilian Konzack and Wim Reddingius.

Integer and Mixed Integer Tverberg Numbers

Probabilistic embeddings of the Frechet distance
Jesus De Loera, Thomas Hogan, Frederic Meunier and Nabil Mustafa. Anne Driemel and Amer Krivosija.
On the Topology of Walkable Environments On Optimal Polyline Simplification using the Hausdorff and Fréchet Distance
Benjamin Burton, Arne Hillebrand, Maarten Löffler, Saul Schleimer, Dylan Thurston, Stephan Tillmann and Wouter van Toll. Marc Van Kreveld, Maarten Löffler and Lionov Wiratma.

Day 3 – Friday, March 23

Session 8 (invited talk) – Chair: Günter Rote
Geometric Issues for Self-Driving Cars
Raúl Rojas
Session 9A – Chair: Christian Knauer Session 9B – Chair: Lena Schlipf
L(2,1)-labeling of disk intersection graphs Non-Monochromatic and Conflict-Free Colorings in Tree Spaces
Konstanty Junosza-Szaniawski and Joanna Sokół. Boris Aronov, Mark de Berg, Aleksandar Markovic and Gerhard J. Woeginger.
Stabbing pairwise intersecting disks by five points Arrangements of Pseudocircles: On Circularizability
Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir and Max Willert. Stefan Felsner and Manfred Scheucher.
Finding the Girth in Disk Graphs and a Directed Triangle in Transmission Graphs Sequences of spanning trees for L-Delaunay triangulations
Haim Kaplan, Katharina Klost, Wolfgang Mulzer and Liam Roditty. Pilar Cano, Prosenjit Bose and Rodrigo I. Silveira.
QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs 3D-Disk-Packing
Edouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski and Florian Sikora. Helmut Alt, Otfried Cheong, Ji-Won Park and Nadja Scharf.
Geometric clustering in normed planes Lower bounds for coloring of the plane
Pedro Martín and Diego Yáñez. Konstanty Junosza-Szaniawski and Krzysztof Węsek.
Session 10A – Chair: Panos Giannopoulos Session 10B – Chair: Rolf Klein
Reconstructing a convex polygon from its ω-cloud An FPTAS for an Elastic Shape Matching Problem with Cyclic Neighborhoods
Prosenjit Bose, Jean-Lou De Carufel, Elena Khramtcova and Sander Verdonschot. Christian Knauer, Luise Sommer and Fabian Stehn.
On Convex Polygons in Cartesian Products A Polynomial Algorithm for Balanced Clustering via Graph Partitioning
Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba Tóth and Sander Verdonschot. Luis Evaristo Caraballo de La Cruz, José Miguel Díaz Báñez and Nadine Kroher.
Mitered offsets and straight skeletons for circular arc polygons Deletion in abstract Voronoi diagrams in expected linear time
Bastian Weiß, Bert Jüttler and Franz Aurenhammer. Kolja Junginger and Evanthia Papadopoulou.
Generalized kernels of polygons under rotation Fair Voronoi Split-Screen for N-Player Games
David Orden, Leonidas Palios, Carlos Seara and Pawel Zylinski. Tobias Lenz.
Generalized Visibility Kernel A new algorithm for finding polygonal voids in Delaunay triangulations and its parallelization
Eyup Serdar Ayaz and Alper Ungor. Nancy Hitschfeld, José Ojeda and Rodrigo Alonso.
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain On Primal-Dual Circle Representations
Man-Kwun Chiu, Elena Khramtcova, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen and Marcel Roeloffzen. Stefan Felsner and Günter Rote.

List of accepted papers

No Paper Authors

1

Maximal Two-Guard Walks in a Polygon Franz Aurenhammer, Michael Steinkogler and Rolf Klein.
2 Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain Man-Kwun Chiu, Elena Khramtcova, Aleksandar Markovic, Yoshio Okamoto, Aurélien Ooms, André van Renssen and Marcel Roeloffzen.
3 Geometric clustering in normed planes Pedro Martín and Diego Yáñez.
4 Coxeter triangulations have good quality Siargey Kachanovich, Mathijs Wintraecken and Aruni Choudhary.
5 A combinatorial measure of closeness in point sets Patrick Schnider and Alexander Pilz.
6 An FPTAS for an Elastic Shape Matching Problem with Cyclic Neighborhoods Christian Knauer, Luise Sommer and Fabian Stehn.
7 Group Diagrams for Representing Trajectories Maike Buchin and Bernhard Kilgus.
8 Agglomerative Clustering of Growing Squares Thom Castermans, Bettina Speckmann, Frank Staals and Kevin Verbeek.
9 A New Lower Bound on the Maximum Number of Plane Graphs using Production Matrices Clemens Huemer, Alexander Pilz and Rodrigo Silveira.
10 Optimal Algorithms for Compact Linear Layouts Wouter Meulemans, Willem Sonke, Bettina Speckmann, Eric Verbeek and Kevin Verbeek.
11 A Framework for Algorithm Stability and its Application to Kinetic Euclidean MSTs Wouter Meulemans, Bettina Speckmann, Kevin Verbeek and Jules Wulms.
12 Guarding Monotone Polygons with Vertex Half-Guards is NP-Hard Matt Gibson, Erik Krohn and Matthew Rayford.
13 Progressive Simplification of Polygonal Curves Kevin Buchin, Maximilian Konzack and Wim Reddingius.
14 Drawing Connected Planar Clustered Graphs on Disk Arrangements Tamara Mchedlidze, Marcel Radermacher, Ignaz Rutter and Nina Zimbel.
15 Arrangements of Pseudocircles: On Circularizability Stefan Felsner and Manfred Scheucher.
16 On Romeo and Juliet Problems: Minimizing Distance-to-Sight Fabian Stehn, Hee-Kap Ahn, Eunjin Oh, Lena Schlipf and Darren Strash.
17 The Topology of Skeletons and Offsets Stefan Huber.
18 Balanced Dynamic Loading and Unloading Sándor Fekete, Sven von Höveling, Joseph Mitchell, Christian Rieck, Christian Scheffer, Arne Schmidt and James Zuber.
19 Almost-equidistant sets Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel and Pavel Valtr.
20 Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality Andreas Haas.
21 Minimal Geometric Graph Representations of Order Types Oswin Aichholzer, Martin Balko, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber and Emo Welzl.
22 Beam It Up, Scotty: Angular Freeze-Tag with Directional Antennas Sándor Fekete and Dominik Krupke.
23 Computing Crossing-Free Configurations with Minimum Bottleneck Sándor Fekete and Phillip Keldenich.
24 Properties of Minimal-Perimeter Polyominoes Gill Barequet and Gil Ben-Shachar.
25 On Optimal Polyline Simplification using the Hausdorff and Fréchet Distance Marc Van Kreveld, Maarten Löffler and Lionov Wiratma.
26 Probabilistic embeddings of the Frechet distance Anne Driemel and Amer Krivosija.
27 Augmenting a tree to a k-arbor-connected graph with pagenumber k Toru Hasunuma.
28 1-Bend RAC Drawings of NIC-Planar Graphs in Quadratic Area Steven Chaplick, Fabian Lipp, Alexander Wolff and Johannes Zink.
29 Stabbing pairwise intersecting disks by five points Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir and Max Willert.
30 Combinatorial and Asymptotical Results on the Neighborhood Grid Data Structure Martin Skrodzki, Ulrich Reitebuch, Konrad Polthier and Shagnik Das.
31 A Note on Planar Monohedral Tilings Oswin Aichholzer, Michael Kerber, Istvan Talata and Birgit Vogtenhuber.
32 NP-Completeness of Max-Cut for Segment Intersection Graphs Oswin Aichholzer, Wolfgang Mulzer, Patrick Schnider and Birgit Vogtenhuber.
33 Non-Monochromatic and Conflict-Free Colorings in Tree Spaces Boris Aronov, Mark de Berg, Aleksandar Markovic and Gerhard J. Woeginger.
34 Fair Voronoi Split-Screen for N-Player Games Tobias Lenz.
35 Short Plane Support Trees for Hypergraphs Thom Castermans, Mereke van Garderen, Wouter Meulemans, Martin Nöllenburg and Xiaoru Yuan.
36 Integer and Mixed Integer Tverberg Numbers Jesus De Loera, Thomas Hogan, Frederic Meunier and Nabil Mustafa.
37 Deletion in abstract Voronoi diagrams in expected linear time Kolja Junginger and Evanthia Papadopoulou.
38 Data Gathering in Faulty Sensor Networks Using a Mule Stav Ashur.
39 On Convex Polygons in Cartesian Products Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba Tóth and Sander Verdonschot.
40 Rollercoasters: Long Sequences without Short Runs Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka and Jeffrey Shallit.
41 Altitude Terrain Guarding and Guarding Uni-Monotone Polygons Stephan Friedrichs, Valentin Polishchuk and Christiane Schmidt.
42 On Merging Straight Skeletons Franz Aurenhammer and Michael Steinkogler.
43 The k-Fréchet distance of polygonal curves Maike Buchin and Leonie Ryvkin.
44 Reconstructing a convex polygon from its $\omega$-cloud Prosenjit Bose, Jean-Lou De Carufel, Elena Khramtcova and Sander Verdonschot.
45 Computing optimal shortcuts for networks Delia Garijo, Alberto Márquez, Natalia Rodríguez and Rodrigo Silveira.
46 A Note on Flips in Diagonal Rectangulations Jean Cardinal, Vera Sacristan and Rodrigo Silveira.
47 3D-Disk-Packing Helmut Alt, Otfried Cheong, Ji-Won Park and Nadja Scharf.
48 Combinatorics of Beacon-based Routing in Three Dimensions Jonas Cleve and Wolfgang Mulzer.
49 Sequences of spanning trees for $L_\infty$-Delaunay triangulations Pilar Cano, Prosenjit Bose and Rodrigo I. Silveira.
50 Maximizing Ink in Symmetric Partial Edge Drawings of k-plane Graphs Michael Höller, Fabian Klute, Soeren Nickel, Martin Nöllenburg and Birgit Schreiber.
51 Time-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees Bahareh Banyassady, Luis Barba and Wolfgang Mulzer.
52 Mitered offsets and straight skeletons for circular arc polygons Bastian Weiß, Bert Jüttler and Franz Aurenhammer.
53 The Partition Spanning Forest Problem Philipp Kindermann, Boris Klemz, Ignaz Rutter, Patrick Schnider and André Schulz.
54 Protecting a highway from fire Rolf Klein, David Kübel, Elmar Langetepe and Barbara Schwarzwald.
55 A Fully Polynomial Time Approximation Scheme For the Smallest Diameter of Imprecise Points Vahideh Keikha, Maarten Löffler and Ali Mohades.
56 A new algorithm for finding polygonal voids in Delaunay triangulations and its parallelization Nancy Hitschfeld, José Ojeda and Rodrigo Alonso.
57 L(2,1)-labeling of disk intersection graphs Konstanty Junosza-Szaniawski and Joanna Sokół.
58 A Polynomial Algorithm for Balanced Clustering via Graph Partitioning Luis Evaristo Caraballo de La Cruz, José Miguel Díaz Báñez and Nadine Kroher.
59 Approximate stabbing queries with sub-logarithmic local replacement. Ivor Hoog V.D. and Maarten Löffler.
60 Subquadratic Encodings for Point Configurations Jean Cardinal, Timothy M. Chan, John Iacono, Stefan Langerman and Aurélien Ooms.
61 QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs Edouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski and Florian Sikora.
62 Automatic Drawing for Tokyo Metro Map Masahiro Onda, Masaki Moriguchi and Keiko Imai.
63 On the Weak Line Cover Number Oksana Firman, Alexander Ravsky and Alexander Wolff.

65 Convexity-Increasing Morphs of Planar Graphs Linda Kleist, Boris Klemz, Anna Lubiw, Lena Schlipf, Frank Staals and Darren Strash.
66 On the Topology of Walkable Environments Benjamin Burton, Arne Hillebrand, Maarten Löffler, Saul Schleimer, Dylan Thurston, Stephan Tillmann and Wouter van Toll.
67 The hardness of Witness puzzles Irina Kostitsyna, Maarten Löffler, Max Sondag, Willem Sonke and Jules Wulms.
68 Finding the Girth in Disk Graphs and a Directed Triangle in Transmission Graphs Haim Kaplan, Katharina Klost, Wolfgang Mulzer and Liam Roditty.
69 Lower bounds for coloring of the plane Konstanty Junosza-Szaniawski and Krzysztof Węsek.
70 Bottleneck Bichromatic Non-crossing Matchings using Orbits Marko Savić and Milos Stojakovic.
71 Efficient Algorithms for Ortho-Radial Graph Drawing Benjamin Niedermann, Ignaz Rutter and Matthias Wolf.
72 On Primal-Dual Circle Representations Stefan Felsner and Günter Rote.
73 Shape Recognition by a Finite Automaton Robot Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph and Christian Scheideler.
74 Generalized kernels of polygons under rotation David Orden, Leonidas Palios, Carlos Seara and Pawel Zylinski.
75 Generalized Visibility Kernel Eyup Serdar Ayaz and Alper Ungor.