Embedded Files
CCCG & WADS 2025
Program
York University, Toronto
Talks
Each talk is allocated 25 minutes, which includes setup, presentation, and Q&A.
Note for speakers: We recommend copying your presentation files (e.g., via USB or email) to the room computer before your session to ensure a smooth transition and avoid any delays. If you prefer to use your laptop, we will do our best to accommodate all systems.
Volunteers will be available in each room to assist with setup and technical issues. We kindly request that all presenters to test their setup in advance.
We will hold an Open Problem session at both WADS and CCCG. If you have an open problem to share, please prepare a brief explanation—we would be very pleased to welcome you to present it.
Some colleagues are unable to attend the conferences due to visa issues. In such cases, they have provided a pre-recorded video of their talk, which will be played during their scheduled time slot, followed by a live Q&A session. In the conference program, the remote talks are marked with a pink note.
Note to authors: If your talk does not have a pink note, we will assume that one of the authors will present the paper in person. Please let us know as soon as possible if this is not the case.Unfortunately, the WADS Best Paper session has been canceled due to an accident involving the presenter.
Proceedings
WADS – The official proceedings have not yet been published; however, a preliminary version is now available and shared via email.
CCCG – To view individual papers, click on the provided links to access the PDF files.
The complete set of indexed papers can be found here:
https://cccg-wads-2025.eecs.yorku.ca/cccg-all-papers.pdf
Locations and Social Events
All talks will take place in the Accolade East Building (ACE) at York University's Keele Campus.
Registration & Coffee Breaks – Ground floor of ACE.
Talks – Lower level, rooms ACE 001, ACE 003, and ACE 005.
Reception (Tuesday evening) – Schulich Executive Dining Room, located across the street from the ACE building.
Banquet (Wednesday evening) – McMichael Canadian Art Collection. Buses will transport attendees from the conference venue to McMichael. See the program for banquet details.
Game Nights & Pizza (Monday and Thursday evening) – Hosted by volunteer students in the Lassonde Building, Room 3033 (York University EECS building).
Monday, August 11
(WADS Day 1)
Monday, August 11
(WADS Day 1)
8:00 AM - 8:45 AM
Registration
Registration
ACE Ground Floor
8:45 AM - 9:00 AM
WADS Welcome and Opening Remarks
ACE 001
WADS Welcome and Opening Remarks
ACE 001
9:00 AM - 10:40 AM
WADS Session 1A
WADS Session 1A
Parametrized Algorithms
chair: Pat Morin
ACE 001
Repairing Schedules by Removing Waiting Times: A Parameterized Complexity Analysis
Niels Grüttemeier and Klaus HeegerThe Parameterized Landscape of Labeled Graph Contractions
Manuel Lafond and Bertrand MarchandFantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
Niels Grüttemeier, Nils Morawietz and Frank SommerApproximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii
Sayan Bandyapadhyay and Eli Mitchell
WADS Session 1B
Geometry I: Coverage & Packing
WADS Session 1B
Geometry I: Coverage & Packing
chair: Michiel Smid
ACE 003
Convolution and Knapsack in Higher Dimensions
Kilian Grage, Klaus Jansen and Björn Schumacher
On geodesic disks enclosing many points
Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo Silveira and Tyler Tuttle.Sweeping a Domain with Line-of-Sight Between Covisible Agents
Kien Huynh, Joseph Mitchell and Valentin Polishchuk
(remote – Video talk + Q&A)An Improved Guillotine Cut for Squares
Parinya Chalermsook, Axel Kugelmann, Ly Orgo, Sumedha Uniyal and Minoo Zarsav.
10:40 AM - 11:00 AM
Break
Break
ACE Ground Floor
11:00 AM - 12:00 PM
WADS Invited Talk
WADS Invited Talk
Dr. Prosenjit Bose, Carleton University
Title: Constructing and Routing on Geometric Spanners
chair: Ian Munro
ACE 001
Abstract: pdf link
12:00 PM - 2:00 PM
Lunch - on your own
Lunch - on your own
2:00 PM - 3:15 PM
WADS Session 2A
WADS Session 2A
Dynamic Streaming Algorithms for Geometric Independent Set
Timothy M. Chan and Yuancheng YuParameterized Streaming Algorithms for Topological Sorting
Ho-Lin Chen, Peng-Ting Lin and Meng-Tsung TsaiStreaming Algorithms for Conflict-free Coloring
Rogers Mathew, Fahad Panolan and Seshikanth Varma
(remote – video talk + Q&A)
WADS Session 2B
Graphs I: Distance & Routing
WADS Session 2B
Graphs I: Distance & Routing
chair: David Mount
ACE 003
Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
Vikrant Ashvinkumar, Rezaul Chowdury, Jie Gao, Mayank Goswami, Joseph Mitchell and Valentin PolishchukRouting Few Robots in a Crowded Network
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko and Ramanujan M. SridharanAlgorithms for Distance Problems in Continuous Graphs
Sergio Cabello, Delia Garijo, Antonia Kalb, Fabian Klute, Irene Parada and Rodrigo Silveira
Testing whether a subgraph is convex or isometric
Sergio Cabello
This talk has been cancelled due to an accident involving the presenter.
3:15 PM - 3:45 PM
Break
Break
ACE Ground Floor
3:45 PM - 5:00 PM
WADS Session 3A
WADS Session 3A
Geometry II: Geometric Distance
chair: Eunjin Oh
ACE 001
A near-linear time exact algorithm for the L1 geodesic Fréchet distance between two curves on the boundary of a simple polygon
Thijs van der Horst, Marc van Krevel, Tim Ophelders and Bettina SpeckmannLink diameter, radius and 2-point link distance queries in polygonal domains
Mart Hagedoorn and Valentin Polishchuk
On the Complexity of Minimising the Moving Distance for Dispersing Objects
Nicolás Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka and Hirotaka Ono
WADS Session 3B
WADS Session 3B
Data Structures
chair: Gill Barequet
ACE 003
Fast Kd-trees for the Kullback--Leibler Divergence and other Decomposable Bregman Divergences
Tuyen Pham and Hubert WagnerGrand-children weight-balanced binary search trees
Vincent JugéB-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load
Roodabeh Safavi and Martin P. Seybold
Tuesday, August 12
(WADS Day 2)
Tuesday, August 12
(WADS Day 2)
8:30 AM - 9:15 AM
Registration
Registration
ACE Ground Floor
9:15 AM - 10:30 AM
WADS Session 4A
Graphs II: Structures and Testing
WADS Session 4A
Graphs II: Structures and Testing
chair: Eunjin Oh
ACE 001
Succinct Data Structures for Chordal Graph with Bounded Leafage or Vertex Leafage
Meng He and Kaiyu WuLinear Layouts of Graphs with Priority Queues
Emilio Di Giacomo, Walter Didimo, Henry Förster, Torsten Ueckerdt and Johannes ZinkScheduling on Identical Machines with Setup Time and Unknown Execution Time
Yasushi Kawase, Vinh Long Phan, Kazuhisa Makino and Hanna Sumita
WADS Session 4B
WADS Session 4B
Geometry III: Crossing & Drawing
chair: Therese Biedl
ACE 003
On Planar Straight-Line Dominance Drawings
Patrizio Angelini, Michael Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli and Giacomo OrtaliOn Minimizing Wiggle in Stacked Area Charts
Alexander Dobler and Martin NöllenburgCrossing and Independent Families among Polygons
Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute and Irene Parada
10:30 AM - 11:00 AM
Break
Break
ACE Ground Floor
11:00 AM - 12:00 PM
WADS Invited Talk
WADS Invited Talk
Dr. Hsien-Chih Chang, Dartmouth College
Title: Unintuitive Facts about Distances on Planar Graphs
Chair: Eunjin Oh
ACE 001
Abstract:
Conventional wisdom told us that planar graphs are essentially edge-weighted grids, with more or less equal side-lengths. An $n$-node $n^{1/2} \times n^{1/2}$ square grid has treewidth $\Theta(n^{1/2})$; and if we want to preserve shortest-path distances between every pair of boundary nodes, intuitively we have to keep all the $n^{1/2}$ column and row paths, which together create $n$ ``crossings’’ that cannot be removed. This seems to suggest that planar graphs are incompressible and not tree-like. Or does it?
In this talk, we will discuss three unintuitive, and perhaps surprising, facts about planar metrics in the $(1 + \varepsilon)$-approximation regime.
First, we demonstrate how to construct emulators for planar graphs that preserve all-pairs distances between $k$ terminals, and have size $\widetilde{O}_{\varepsilon}(k)$. (This implies, for the grid example above, the resulting emulator has size $\widetilde{O}(n^{1/2})$.)
Second, planar metrics can be covered using constantly (!) many trees, in the sense that we can construct $O(1)$ trees independent of the input graph size that never shrink distances, so that given any pair of nodes $x$ and $y$, there is one tree $T$ that contains both $x$ and $y$ whose distance on $T$ is stretched by at most a $(1 + \varepsilon)$ factor. Along the way, we will introduce a novel structure on planar metrics — the gridtrees — that enables such tree covers, as well as its applications in the resolution to the Steiner point removal problem, and in constructing embeddings of planar graphs into polylog-treewidth graphs with $(1 + \varepsilon)$-distortion. (Which means, if we are willing to distort the distance by a small amount, planar metrics are very much tree-like.)
Finally, we will discuss the issue of spanning. Both results above rely on the fact that the emulator and the tree cover use Steiner nodes, which are nodes not present in the original input graph. Maybe this is cheating, and the distance compression is only possible because of these nodes that appear out of nowhere? Our goal is to convince you otherwise: we can, in fact, construct emulators for planar graphs that are minors, which only use paths and edges from the input planar graph; and in the case of tree covers, we are one or two new structures away from enforcing the trees to be spanning, that is, the edges in the trees come from the input graph as well.
12:00 PM - 1:30 PM
Lunch - on your own
Lunch - on your own
1:30 PM - 2:45 PM
WADS Session 5A
WADS Session 5A
Counting & Enumeration
chair: Aaron Williams
ACE 001
Tight Bounds on the Number of Closest Pairs in Vertical Slabs
Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung, Jean-Lou De Carufel, John Iacono, Anil Maheshwari, Saeed Odak, Michiel Smid and Csaba TothOn the enumeration of signatures of XOR-CNF’s
Nadia Creignou, Oscar Defrain, Frédéric Olive and Simon VilminEnumerating minimal dominating sets and variants in chordal bipartite graphs
Emanuel Castelo, Oscar Defrain and Guilherme Gomes
WADS Session 5B
Geometry IV: Noise and Motion
WADS Session 5B
Geometry IV: Noise and Motion
chair: Michael Goodrich
ACE 003
Computational Geometry with Probabilistically Noisy Primitive Operations
Vinesh Sridhar, Michael T. Goodrich and David Eppstein.Evolving Distributions Under Local Motion
Aditya Acharya and David MountSupport Vector Machines in the Hilbert Geometry
Aditya Acharya, Auguste Gezalyan, Julian Vanecek and David Mount
2:45 PM - 3:15 PM
Break
Break
ACE Ground Floor
3:15 PM - 4:30 PM
WADS Session 6A
WADS Session 6A
Graphs III: Separators and Spanners
chair: Birgit Vogtenhuber
ACE 001
A WSPD, Separator and Small Tree Cover for c-packed Graphs
Lindsey Deryckere, Joachim Gudmundsson, Yuan Sha, Sampson Wong and André van Renssen
Novel Complexity Results for Temporal Separators with Deadlines
Riccardo Dondi and Manuel LafondSpanner for the $0/1/\infty$ weighted region problem
Joachim Gudmundsson, Zijin Huang, André van Renssen and Sampson Wong
WADS Session 6B
WADS Session 6B
Dynamic Programming & Encoding
chair: David Eppstein
ACE 003
On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms
Lorenzo De Stefani and Vedant GuptaQuantum Speedups for Polynomial-Time Dynamic Programming Algorithms
Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael Goodrich and Martin NöllenburgSkipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations
Vincent Pilaud and Aaron Williams
4:30 PM - 5:00 PM
Break
Break
ACE Ground Floor
Wednesday, August 13
(WADS Day 3, CCCG Day 1)
Wednesday, August 13
(WADS Day 3, CCCG Day 1)
8:00 AM - 8:45 AM
Registration
Registration
ACE Ground Floor
8:45 AM - 9:00 AM
CCCG Welcome and Opening Remarks
ACE 001
CCCG Welcome and Opening Remarks
ACE 001
9:00 AM - 10:40 AM
WADS Session 7
WADS Session 7
Online and Scheduling Algorithms
Online and Scheduling Algorithms
chair: Zachary Friggstad
ACE 003
Lower bounds for several standard bin packing algorithms in the random order model
Leah Epstein and Asaf LevinOnline Routing in Directed $\vec{\text{Yao}_4^\infty}$ Graphs
John Stuart, Prosenjit Bose and Jean-Lou De CarufelAn efficient polynomial time approximation scheme for minimizing the total weighted completion time on uniformly related machines
Leah Epstein and Asaf Levin
CCCG Session 1
Graph Embeddings & Layout Constraints
CCCG Session 1
Graph Embeddings & Layout Constraints
chair: Avery Miller
ACE 001
On Upward Book Embeddability of DAGs
Rustem Kakimov, Xing TanSweeping $x$-monotone pseudolines
Therese Biedl, Erin Chambers, Irina Kostitsyna, Günter RoteStraight-line Orthogonal Drawing of Complete Ternary Tree Requires $O(n^{1.032})$ Area
Hong Duc Bui
CancelledOn Upward Planar Embeddings of Paths with Partially Fixed Vertices
Stephane Durocher, Myroslav Kryven, Tamara Mchedlidze
10:40 AM - 11:00 AM
Break
Break
ACE Ground Floor
11:00 AM - 12:00 PM
Abstract:
Reranking is a popular approach to information retrieval. It proceeds in two stages. In the first stage, a "quick-and-dirty" data structure retrieves a shortlist of r points closest to the query, where the length of the shortlist r is larger than the desired output k. In the second stage, the shortlist is post-processed to identify k<<r points that satisfy the desired objective. For example, the postprocessing could identify the k most "diverse" points in the shortlist or use a "slower-but-accurate" distance metric to identify the best answers. Despite its popularity, it has various drawbacks; notably the quality of the output is limited by the accuracy of the first stage.
In this talk, I will discuss an alternative to reranking, which fuses the two stages into a single search procedure. The new approach crucially uses recent developments in graph-based algorithms for high-dimensional similarity search, as well the tools developed to analyze such algorithms.
12:00 PM - 1:30 PM
Lunch - on your own
Lunch - on your own
1:30 PM - 2:45 PM
WADS Session 8
WADS Session 8
Approximation Algorithms
Approximation Algorithms
chair: Da Wei (David) Zheng
ACE 001
Approximation Algorithms for the Generalized Point-to-Point Problem
Zachary Friggstad, Mohammad Salavatipour and Hao SunA QPTAS for Facility Location on Unit Disk Graphs
Zachary Friggstad, Mohsen Rezapour, Mohammad Salavatipour and Hao SunDeterministic $(2/3 - \varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
Tatsuya Terao
CCCG Session 2
Noise, Entropy, and Dynamics
CCCG Session 2
Noise, Entropy, and Dynamics
chair: Denis Pankratov
ACE 005
Optimal Parallel Algorithms for Convex Hulls in 2D and 3D under Noisy Primitive Operations
Michael T. Goodrich, Vinesh SridharEntropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan, Claire A. ToPTAS for Stabbing Unit Squares and Variants
Tanmay Inamdar, Sounak Modak, Kushal Singanporia
(remote – video talk + Q&A)
2:45 PM - 3:10 PM
Break
Break
ACE Ground Floor
3:10 PM - 4:50 PM
WADS Session 9
Clustering and Center Problems
WADS Session 9
Clustering and Center Problems
chair: Rahnuma Islam Nishat
ACE 001
Clustering Point Sets Revisited
Md. Billal Hossain and Benjamin RaichelFarthest-point Voronoi Diagrams in the Hilbert Metric
Minju Song, Mook Kwon Jung and Hee-Kap AhnOn the Complexity of Finding 1-Center Spanning Trees
Pin-Hsian Lee, Meng-Tsung Tsai and Hung-Lung Wang
CCCG Session 3
Polygons, Polyhedra, and Polyominos
CCCG Session 3
Polygons, Polyhedra, and Polyominos
chair: Gill Barequet
ACE 005
Inside-Out Dissections of Polygons and Polyhedra
Reymond Akpanya, Adi Rivkin, Frederick StockQuasigeodesics on the Cube
Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Thomas C. Hull, Anna Lubiw, Jayson Lynch, Klara Mundilova, Chie Nara, Joseph O'Rourke, Frederick Stock, Josef Tkadlec, Ryuhei UeharaDecremental Greedy Polygons and Polyhedra Without Sharp Angles
David EppsteinOn $t$-fold Totally-Concave Polyominoes
Gill Barequet, Neal Madras, Johann Peters
4:50 PM - 10:00 PM
WADS/CCCG Banquet
WADS/CCCG Banquet
McMichael Canadian Art Collection
5:00 PM – Buses depart York University for McMichael
~5:30 - 5:45 PM – Arrive at McMichael (traffic-dependent)
~ 5:30- 5:50 – Group photo
5:50 – 7:45 PM – Gallery open for attendees
6:30 PM – Bar opens
~7:30 PM – Dinner served
9:30 PM – Bar closes
9:45 PM – Buses depart McMichael for return to Toronto (with a stop at Vaughan area)
Thursday, August 14
(CCCG Day 2)
Thursday, August 14
(CCCG Day 2)
8:30 AM - 9:00 AM
Registration
Registration
ACE Ground Floor
9:00 AM - 10:40 AM
CCCG Session 4A
Visibility and Guarding
CCCG Session 4A
Visibility and Guarding
chair: Therese Biedl
ACE 001
Guarding Polygons With Mutually Visible π-Guards
Arash Ahadi, Ahmad Biniaz, Mohammad Hashemi, Ali NakhaeisharifMultiple Watchman Routes in Staircase Polygons
Anna Brötzner, Bengt J. Nilsson, Christiane SchmidtOn Super-Guarding Convex and Star-Shaped Polygons
Gabriel Aldous, Seth Barber, Alper UngorThe VC-Dimension of Limited Visibility on the Boundary of a Simple Polygon
Matt Gibson-Lopez, Erik Krohn, Zhongxiu Yang
CCCG Session 4B
Transformations and Metric Extensions
CCCG Session 4B
Transformations and Metric Extensions
chair: Neal Madras
ACE 003
The Number of Non-overlapping Unfoldings in Convex Polyhedra
Takumi Shiota, Yudai Enomoto, Masashi Gorobe, Takashi Horiyama, Tonan Kamata, Toshiki Saitoh, Ryuhei UeharaOn the Diameters of Reconfiguration Graphs and ZDD-Based BFS-Algorithm for Optimal Reconfiguration Problems of Optimal Ladder Lotteries
Shoon Mineyoshi, Kazuhisa Seto, Takashi HoriyamaFast Approximate Lipschitz Extensions in Doubling Metrics
Donald SheehyHausdorff Edit Distance
Jonathan Perry, Benjamin Raichel
10:40 AM - 11:00 AM
Break
Break
ACE Ground Floor
11:00 AM - 12:00 PM
CCCG Invited Talk
Godfried Toussaint Memorial Talk
CCCG Invited Talk
Godfried Toussaint Memorial Talk
chair: Ian Munro
ACE 001
Dept. of Computer Science and Institute for Advanced Computer Studies,
University of Maryland
Title: Computational Geometry from a Non-Euclidean Perspective
Title: Computational Geometry from a Non-Euclidean Perspective
Abstract:
The field of discrete and computational geometry has been immensely successful in enhancing the understanding of efficient algorithms and data structures for problems that involve geometric inputs. The vast majority of work in this field has focused on Euclidean geometry and its close relatives in normed spaces, such as L_1 and L_infinity. Recently, there has been growing interest in non-Euclidean geometries, including hyperbolic geometry, Hilbert geometry, and alternative notions of distance, such as Bregman divergences. In this talk, we will explore the reasons behind the increased interest in these geometries, survey recent developments, and demystify the somewhat arcane mathematics that underlies these systems. Finally, we will present many open problems that are inspired by this non-Euclidean viewpoint.
12:00 PM - 1:30 PM
Lunch - on your own
Lunch - on your own
1:30 PM - 2:00 PM
CCCG- Best PhD Dissertation Presentation
CCCG- Best PhD Dissertation Presentation
chair: David Eppstein
ACE 001
Thesis: From Geometry to Graphs and Back: Geometric Range Searching and Algorithms in Structured Graphs
Author: Da Wei (David) Zheng, UIUC
Abstract
This thesis is split into two parts. The first part is on geometric data structures related to range searching with ranges whose boundaries consist of lines, line segments, or can be described by algebraic equations. These data structures are fundamental components of geometric algorithms such as for nearest neighbors, Euclidean minimum spanning tree, and computing Voronoi diagrams.
The second part of the thesis is focused on developing algorithms for problems like computing the diameter for structured classes of graphs such as planar graphs, minor-free graphs, and geometric intersection graphs. The algorithms involve techniques including: low dimensional decomposition of graphs, VC-dimension, and geometric range searching data structures.
2:00 PM - 3:40 PM
CCCG Session 5A
Tree and Center Problems
CCCG Session 5A
Tree and Center Problems
chair: Michiel Smid
ACE 001
Minimum Anchored Steiner Trees with Removable Obstacles
Stephane Durocher, Arman Heydari, J. Mark Keil, Debajyoti MondalApproximate and Exact Geometric Generalized Minimum Spanning Trees
Majid Mirzanezhad, Arash RafieyFault-Tolerant Euclidean k-Centres
Stephane Durocher, Sahar Lamey, Pak Ching LiThe Orthogonal Two-Line Center Problem
Taehoon Ahn, Sang Won Bae, Sang Duk Yoon
CCCG Session 5B
CCCG Session 5B
Puzzles & Complexity
chair: Rahnuma Islam Nishat
ACE 003
Covert Computation in the Prebuilt aTAM
Timothy Gomez, Robert Schweller, Tim WyliePartitioning Colored Points into Monochromatic Islands is NP-Complete
Steven van den Broek, Marc van Kreveld, Soeren TerziadisPuzzles are hard enough just by rotations
Takeshi Yamada, Tom van der Zanden, Ryuhei UeharaInput-Sensitive Reconfiguration of Sliding Cubes
Hugo A. Akitaya, Matias Korman, Frederick Stock
3:40 PM -4:00 PM
Break
Break
ACE Ground Floor
Friday, August 15
(CCCG Day 3)
Friday, August 15
(CCCG Day 3)
8:30 AM - 9:00 AM
Registration
Registration
ACE Ground Floor
9:00 AM - 10:40 AM
CCCG Session 6A
CCCG Session 6A
Probing Geometry & Query Optimization
chair: Aditya Potukuchi
ACE 001
Approximating Metric Depth Queries
Shuhao Tan, David MountReconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
Chirag Kaudan, Amir NayyeriThe Marco Polo Problem: A Combinatorial Approach to Geometric Localization
Ofek Gila, Michael Goodrich, Zahra Hadizadeh, Daniel Hirschberg, Shayan TaherijamThe Rectilinear Marco Polo Problem
Ofek Gila, Michael Goodrich, Zahra Hadizadeh, Daniel Hirschberg, Shayan Taherijam
CCCG Session 6B
Graphs and Approximation
CCCG Session 6B
Graphs and Approximation
Chair: Myroslav Kryven
ACE 003
Approximating 2-Clique in Unit Disk Graphs
Karim Abu Affash, Paz Carmi, Iliya LisinComputing Maximum Cliques in Unit Disk Graphs
Anastasiia Tkachenko, Haitao WangApproximation and Hardness of Polychromatic TSP
Thomas Schibler, Subhash Suri, Jie XueMinimum Selective Subset on Some Graph Classes
Bubai Manna
(remote – video talk + Q&A)
10:40 AM - 11:00 AM
Break
Break
ACE Ground Floor
11:00 AM - 12:00 PM
CCCG Invited Talk
Ferran Hurtado Memorial Talk
CCCG Invited Talk
Ferran Hurtado Memorial Talk
chair: Stephane Durocher
ACE 001
Dr. Birgit Vogtenhuber
Graz University of Technology
Title: Combinatorial Reconfiguration: Flipping Non-Crossing Spanning Trees
abstract pdf
Abstract:
Flipping edges in non-crossing geometric graphs has been one of the core research topics of Ferran Hurtado, which is witnessed by the fact that he chose this topic for his invited talk at CCCG 2003. In this talk, I will report on flips in non-crossing spanning trees.
For a set P of n points in the plane, a non-crossing (geometric) spanning tree is a spanning tree of the points in which every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. In its most general form, an edge flip in a non-crossing spanning tree T of P is the operation of removing one edge from T and adding another edge such that the resulting structure is again a non-crossing spanning tree of P. Besides this edge flip, several more restricted flip operations have been considered for spanning trees. Most notably these include compatible edge flips (where the exchanged edges are non-crossing), rotations (where the exchanged edges share an endpoint), and edge slides (where the exchanged edges together with some third edge form an uncrossed triangle).
The problem of transforming one non-crossing spanning tree into another one via a sequence of flip operations of some type has been widely studied. As already reported by Ferran in 2003, such a transformation is always possible with a finite number of flips even for the case of edge slides, which is the most restricted of the flip operations. We will review recent results concerning bounds on the number of flips that are sometimes required and always sufficient. We will close with possible properties of shortest flip sequences, the algorithmic question of finding such sequences, and some open problems.
12:00 PM - 1:30 PM
Lunch - on your own
Lunch - on your own
1:30 PM - 3:10 PM
CCCG Session 7A
Motion Planning and Robotics
CCCG Session 7A
Motion Planning and Robotics
chair: Tim Wylie
ACE 001
Motion Planning of Disk and Rectangular Robots
Eduard Eiben, Iyad Kanj, Salman ParsaOptimal Delivery with a Faulty Drone
Jared Coleman, Evangelos Kranakis, Danny Krizanc, Oscar Morales-PonceEfficient Reconfiguration of Tile Arrangements by a Single Active Robot
Aaron T. Becker, Sándor P. Fekete, Jonas Friemel, Ramin Kosfeld, Peter Kramer, Harm Kube, Christian Rieck, Christian Scheffer, Arne SchmidtImproved Wake-Up Time For Euclidean Freeze-Tag Problem
(remote – video talk + Q&A)
Sharareh Alipour, Arash Ahadi, Kajal Baghestani
CCCG Session 7B
CCCG Session 7B
Geometric Covering and Packing
chair: Stephane Durocher
ACE 003
Minimum-Weight Half-plane Hitting Set
Gang Liu, Haitao WangCovering Radii of 3-Zonotopes and the Shifted Lonely Runner Conjecture
David Alcántara, Francisco Criado, Francisco SantosSquare Packing with Asymptotically Smallest Waste Only Needs Good Squares
Hong Duc Bui
change: (remote – video talk + Q&A)Reverse Rush Hour is NP-Complete
Jonathan Gabor, Aaron Williams,
3:10 PM - 3:40 PM
CCCG- Best Paper Presentation
CCCG- Best Paper Presentation
chair: Shahin Kamali
ACE 001
Title: The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
Authors: Elizabeth Munch, Elena Xinyi Wang, Carola Wenk
3:40 PM
Conclusions and End of Program
Conclusions and End of Program
Sponsored by:
The Centre for Innovation in Computing at Lassonde (IC@L), York University
Research and Innovation, York University
Lassonde School of Engineering, York University
Department of Electrical Engineering and Computer Science (EECS), York University
Page updated
Google Sites
Report abuse