Additional Materials

WADS Open Problem Session

The notes from the WADS open problem session can be accessed here.

CCCG Open Problem Session

The notes from the CCCG open problem session can be accessed here.

Photos from the Conferences

Click on this link to access a gallery of photos from WADS & CCCG 2023.

Presentations of Invited Speakers

The Dynamic Connectivity Problem. Valerie King

Approximation Algorithms for Some Geometric Packing and Covering Problems. Joseph S.B. Mitchell

Studying information-computation gaps via “reductions between algorithms”. Tselil Schramm

Reconfiguration Algorithms. Diane Souvaine

WADS Presentations

Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent. Ofek Gila, Michael Goodrich and Robert Tarjan

Quick Minimization of Tardy Processing Time on a Single Machine. Baruch Schieber and Pranav Sitaraman

Differentially Private Range Query on Shortest Paths. Chengyuan Deng, Jie Gao, Jalaj Upadhyay and Chen Wang

Tight analysis of the lazy algorithm for open online dial-a-ride. Julia Baligacs, Yann Disser, Farehe Soheil and David Weckbecker

General Space-Time Tradeoffs via Relational Queries. Shaleen Deep, Xiao Hu and Paraschos Koutris

A Parameterized Approximation Scheme for Generalized Partial Vertex Cover. Sayan Bandyapadhyay, Zachary Friggstad and Ramin Mousavi

Finding Diameter-Reducing Shortcuts in Trees. Davide Bilò, Luciano Gualà, Stefano Leucci and Luca Pepè Sciarria

Efficient k-center algorithms for planar points in convex position. Jongmin Choi, Jaegun Lee and Hee-Kap Ahn

Compact Distance Oracles with Large Sensitivity and Low Stretch. Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann and Martin Schirneck

Tight Approximation Algorithms for Ordered Covering. Jatin Batra, Syamantak Das and Agastya Vibhuti Jha

Approximating the discrete center line segment in linear time. Yuan Sha and Joachim Gudmundsson

Faster Algorithms for Cycle Hitting Problems on Disk Graphs. Shinwoo An, Kyungjin Cho and Eunjin Oh

Online Interval Scheduling with Predictions. Joan Boyar, Lene M. Favrholdt, Shahin Kamali and Kim S. Larsen

Geometric Spanning Trees Minimizing the Wiener Index. A. Karim Abu-Affash, Paz Carmi, Ori Luwisch and Joseph Mitchell

Approximate Minimum Sum Colorings and Maximum k-Colorable Subgraphs of Chordal Graphs. Ian DeHaan and Zachary Friggstad

3-Coloring C_4 or C_3-free Diameter Two Graphs. Tereza Klimošová and Vibha Sahlot

Socially Fair Matching: Exact and Approximation Algorithms. Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar, Fahad Panolan and Kirill Simonov

Adaptive Data Structures for 2D Dominance Colored Range Counting. Younan Gao

Fully dynamic clustering and diversity maximization in doubling metrics. Paolo Pellizzoni, Andrea Pietracaprina and Geppino Pucci

Revisiting Graph Persistence for Updates and Efficiency. Tamal Dey, Tao Hou and Salman Parsa

Colored Constrained Spanning Tree on Directed Graphs. Hung-Yeh Lee, Hsuan-Yu Liao and Wing-Kai Hon

From Curves to Words and Back Again: Geometric Computation of Minimum-Area Homotopy. Bradley McCoy, Hsien-Chih Chang, Brittany Terese Fasy, David L. Millman and Carola Wenk

Reconfiguration of Time-Respecting Arborescences. Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-Ichi Maezawa and Akira Suzuki

On Length-Sensitive Fréchet Similarity. Kevin Buchin, Seyed Erfan Hosseini Sereshgi, Brittany Terese Fasy and Carola Wenk

Density Approximation for Moving Groups. Max van Mulken, Bettina Speckmann and Kevin Verbeek

Space-Efficient Functional Offline-Partially-Persistent Trees with Applications to Planar Point Location. Jens Kristian Refsgaard Schou, Gerth Stølting Brodal, Casper Moldrup Rysgaard and Rolf Svenning

Dominator Coloring and CD Coloring in Almost Cluster Graphs. Aritra Banik, Prahlad Narasimhan Kasthurirangan and Venkatesh Raman

Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon. Prosenjit Bose, Anthony D’Angelo and Stephane Durocher

Online TSP with Known Locations. Evripidis Bampis, Bruno Escoffier, Niklas Hahn and Michalis Xefteris

Block Crossings in One-Sided Tanglegrams. Alexander Dobler and Martin Nöllenburg

Improved Bounds for Discrete Voronoi Games. Mark de Berg and Geert van Wordragen

Online Minimum Spanning Trees with Weight Predictions. Magnus Berg, Joan Boyar, Lene Favrholdt and Kim S. Larsen

Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs. Simon Weber and Joel Widmer

Lower Bounds for Non-Adaptive Shortest Path Relaxation. David Eppstein

Verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small Subgraphs. Wing-Kai Hon, Meng-Tsung Tsai and Hung-Lung Wang

External-Memory Sorting with Comparison Errors. Michael Goodrich and Evrim Ozel

Linear Layouts of Bipartite Planar Graphs. Henry Förster, Michael Kaufmann, Laura Merker, Sergey Pupyrev and Chrysanthi Raftopoulou

CCCG Presentations

On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs. Bekos, Michael A.; Kaufmann, Michael; Pavlidi, Maria Eleni; Rieger, Xenia

On the Budgeted Hausdorff Distance Problem. Har-Peled, Sariel; Raichel, Benjamin

Overlapping of Lattice Unfolding for Cuboids. Shiota, Takumi; Kamata, Tonan; Uehara, Ryuhei

Convex Hulls and Triangulations of Planar Point Sets on the Congested Clique. Jansson, Jesper; Levcopoulos, Christos; Lingas, Andrzej J

A Parameterized Algorithm for Flat Folding. Eppstein, David

Universal convex covering problems under affine dihedral group actions. Jung, Mook Kwon; Yoon, Sang Duk; Ahn, Hee-Kap; Tokuyama, Takeshi

Super Guarding and Dark Rays in Art Galleries. O’Rourke, Joseph; Akitaya, Hugo; Demaine, Erik; Hesterberg, Adam; Lubiw, Anna; Lynch, Jayson; Stock, Frederick

Reducing Nearest Neighbor Training Sets Optimally and Exactly. Weber, Simon; Rohrer, Josiah

City Guarding with Cameras of Bounded Field of View. Biniaz, Ahmad; Hashemi, Mohammad

Geometric Graphs with Unbounded Flip-Width. Eppstein, David; McCarty, Rose

On Density Extrema for Digital $\ell_1$-Balls in 2D and 3D. G. Basu, Nilanjana; Majumder, Subhashis; Bhowmick , Partha Bhowmick, IIT Kharagpur

Improved Algorithms for Burning Planar Point Sets. Kamali, Shahin ; Shabanijou, Mohammadmasoud

Approximate Line Segment Nearest Neighbor Search amid Polyhedra in 3-Space. Daescu, Ovidiu; Teo, Ka Yaw

Dynamic Schnyder woods. Cano, Pilar; Bhore, Sujoy; Bose, Prosenjit ; Cardinal, Jean; Iacono, John

Square Hardness for Clustering with Neighborhoods. Klimenko, Georgiy; Raichel, Benjamin

Parallel Line Centers with Guaranteed Separation. Chung, Chaeyoon; Ahn, Taehoon; Bae, Sang Won; Ahn, Hee-Kap

Graph Mover’s Distance: An Efficiently Computable Distance Measure for Geometric Graphs. Majhi, Sushovan

CCOSKEG Discs in Simple Polygons. Bose, Prosenjit ; D’Angelo, Anthony; Durocher, Stephane

Reconfiguration of Linear Surface Chemical Reaction Networks with Bounded State Change. Alaniz, Robert; Coulombe, Michael ; Demaine, Erik; Fu, Bin; Knobel, Ryan; Gomez, Timothy; Grizzell, Elise; Rodriguez, Andrew; Schweller, Robert; Wylie, Timothy

Lower Bounds for the Thickness and the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs and (2,2)-Tight Graphs. Kawakami, Yuki; Takahashi, Shun; Seto, Kazuhisa; Horiyama, Takashi; Kobayashi, Yuki; Higashikawa, Yuya; Katoh, Naoki

On the complexity of embedding in graph products. Biedl, Therese; Eppstein, David; Ueckerdt, Torsten

Spanning Tree, Matching, and TSP for Moving Points: Complexity and Regret. Wachholz, Nathan; Suri, Subhash

Optimal Polyline Simplification under the Local Fréchet Distance in 2D in (Near-)Quadratic Time. Schäfer, Peter; Storandt, Sabine; Zink, Johannes

Every Combinatorial Polyhedron Can Unfold with Overlap. O’Rourke, Joseph