Here are the proceedings of SoCG 2025.
The slots are 20 minutes for SoCG and 15 minutes for CG:YRF. Please plan with a talk length of 18 minutes for SoCG and 13 minutes for CG:YRF, allowing 2 minutes for questions, discussion, and the change of speaker.
SoCG student speakers are labeled with .
Please submit your feedback for SoCG student presentations through this link.
Your feedback will be used to determine the SoCG Best Student Presentation Award. Thank you in advance!
Time | ||||||
---|---|---|---|---|---|---|
15:00-19:00 | Registration |
Time | ||||||
---|---|---|---|---|---|---|
09:00-09:10 |
Opening (Room A) |
|||||
09:10-09:40 |
SoCG Best Paper (Room A) Timothy M. Chan and A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation [DOI] Chair: Haitao Wang |
|||||
09:40-10:00 |
Fast-Forward Session for CG:YRF (Room A) Chair: Eunjin Oh |
|||||
10:00-10:25 | Coffee Break | |||||
10:25-11:25 |
SoCG Session 1A (Room B) Chair: Kristóf Huszár |
SoCG Session 1B (Room C) Chair: Chih-Hung Liu |
||||
10:25-10:45 | Tao Hou, Salman Parsa, and Bei Wang Tracking the Persistence of Harmonic Chains: Barcode and Stability [DOI] |
John Iacono and Yakov Nekrich Incremental Planar Nearest Neighbor Queries with Optimal Query Time [DOI] |
||||
10:45-11:05 | A Theory of Sub-Barcodes [DOI] |
Sublinear Data Structure for Nearest Neighbor in Ultra High Dimensions [DOI] |
||||
11:05-11:25 | Dustin L Arendt, Matthew Broussard, Bala Krishnamoorthy, Nathaniel Saul, and Steinhaus Filtration and Stable Paths in the Mapper [DOI] |
Nearest Neighbor Searching in a Dynamic Simple Polygon [DOI] |
||||
11:25-11:30 | Short Break | |||||
11:30-12:30 |
SoCG Session 2A (Room B) Chair: Jie Xue |
SoCG Session 2B (Room C) Chair: Jeff Phillips |
||||
11:30-11:50 | Eduard Eiben, Robert Ganian, Iyad Kanj, and M. S.
Ramanujan A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots [DOI] |
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris
Schwiegelshohn, and Samson Zhou On Approximability of ℓ22 Min-Sum Clustering [DOI] |
||||
11:50-12:10 | Pankaj K Agarwal, Mark de
Berg, Benjamin
Holmgren, Alex Steiger, and Optimal Motion Planning for Two Square Robots in a Rectilinear Environment [DOI] |
Ivor van der Hoog, Lara Ost, Eva Rotenberg, and Efficient Greedy Discrete Subtrajectory Clustering [DOI] |
||||
12:10-12:30 | Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena
Schlipf, Andre Schulz, and
Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings [DOI] |
Sang Won Bae, Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework [DOI] |
||||
12:30-13:50 |
Lunch Break |
|||||
13:50-14:15 |
SoCG Best Student Paper (Room A) A Sparse Multicover Bifiltration of Linear Size [DOI] Chair: Haitao Wang |
|||||
14:15-14:20 |
Short Break |
|||||
14:20-15:40 |
SoCG Session 3A (Room B) Chair: Jonathan Spreer |
SoCG Session 3B (Room C) Chair: Hsien-Chih Chang |
||||
14:20-14:40 | Édouard Bonnet and Kristóf Huszár On the Twin-Width of Smooth Manifolds [DOI] |
Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Tóth, and Sujoy Bhore Sparse Bounded Hop-Spanners for Geometric Intersection Graphs [DOI] |
||||
14:40-15:00 | Dominique Attali, Mattéo Clémot, Bianca Boeira Dornelas, and André Lieutier When Alpha-Complexes Collapse onto Codimension-1 Submanifolds [DOI] |
Computing Oriented Spanners and Their Dilation [DOI] |
||||
15:00-15:20 | Small triangulations of 4-manifolds: Introducing the 4-manifold census [DOI] |
Kevin Buchin, Carolin Rehs, and Geometric Spanners of Bounded Tree-Width [DOI] |
||||
15:20-15:40 | Colleen Delaney, Clément Maria, and Eric Samperton An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number [DOI] |
Robert Krauthgamer and Lipschitz Decompositions of Finite ℓp Metrics [DOI] |
||||
15:40–16:00 |
Coffee Break |
|||||
16:00–17:45 | CG:YRF Session A (Room A) Chair: Frank Staals |
CG:YRF Session B (Room B) Chair: Eunjin Oh |
CG:YRF Session C (Room C) Chair: Woojin Kim |
|||
16:00-16:15 | Peyman Afshani, Maike Buchin, Anne Driemel, Marena Richter, and Sampson Wong Property Testing of Curve Similarity |
Brennon Treadwell and Amir Nayyeri Strong k-Metric Embeddings |
Erin Chambers, Shankha Shubhra Mukherjee, and Katharine Turner The Reeb Transform |
|||
16:15-16:30 | Lindsey Deryckere, Joachim Gudmundsson, Yuan Sha, Sampson Wong, and André van Renssen Separation Anxiety: A Well-Separated Pair Decomposition and Separator for c-packed Graphs |
Todor Antić, Guillermo Gamboa Quintero, and Jelena Glišić Reconfigurations of Plane Caterpillars and Paths |
Erin Wolf Chambers, Mathijs Wintraecken, Christopher Fillmore, and Elizabeth Stephenson Braiding Vineyards |
|||
16:30-16:45 | Jiaqi Zheng and Tiow-Seng Tan Smallest Intersecting and Enclosing Balls |
Simon D. Fink, Matthias Pfretzschner, and Peter Stumpf Segment Intersection Representations and Constrained Level Planarity |
Ekaterina Ivshina, Galit Anikeeva, and Ling Zhou Detecting Toroidal Structure in Data: Implementation and Applications of Persistent Cup-Length |
|||
16:45-17:00 | Guanlin Mo, Shihong Song, Qingyuan Yang, and Hu Ding Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-Sparse Wasserstein Barycenter Problems |
Cameron Strachan and Konrad Swanepoel Edge Isoperimetry of Lattices |
Loïc Dubois Computing the Intrinsic Delaunay Triangulation of a Closed Orientable Polyhedral Surface |
|||
17:00-17:15 | Kien Huynh, Joseph Mitchell, Anurag Murty, and Valentin Polishchuk Geodesic k-center in a Simple Polygon with Sites on the Boundary |
Jakub Leśkiewicz, Michał Lipiński, and Bartosz Furmanek Topological Simplification Guided by the Depth Poset |
Mattie Ji and Daiyuan Li Realizing Coordinates of the Second Integral Cohomology Group |
|||
17:15-17:30 | Katharina Klost, Kristin Knorr, and Wolfgang Mulzer Robust Algorithms for Finding Triangles and Computing the Girth in Disk and Transmission Graphs |
Debajyoti Kar, Arindam Khan, and Malin Rau Improved Approximation Algorithms for Three-Dimensional Bin Packing |
Koki Furukawa Big Polytopes or Rich Hyperplanes |
|||
17:30-17:45 | Sathish Govindarajan, Mayuresh Patle, and Siddhartha Sarkar Minimum Ply Geometric Set Cover in the Continuous Setting |
Nicolas Honorato-Droguett, Kazuhiro Kurita, Tesshu Hanaka, and Hirotaka Ono On the Complexity of Minimising the Moving Distance for Dispersing Objects |
||||
18:00-19:00 | Discussion Forum |
Time | ||||||
---|---|---|---|---|---|---|
09:00-10:00 | Invited Talk: Meirav Zehavi (Ben-Gurion University of the Negev) - Parameterized Computational Geometry: Visibility Problems, Geometric Intersection Graphs and Graph Drawing (Room A) Chair: Haitao Wang |
|||||
10:00-10:10 | Short Break | |||||
10:10–11:10 | SoCG Session 4A (Room B) Chair: Michael Hoffmann |
SoCG Session 4B (Room C) Chair: Francis Lazarus |
||||
10:10-10:30 | Klaus Jansen, Improved Approximation Algorithms for Three-Dimensional Knapsack [DOI] |
Dmitriy Morozov and Primoz Skraba Persistent (Co)Homology in Matrix Multiplication Time [DOI] |
||||
10:30-10:50 | Karl Bringmann, Kasper Green Larsen, André Nusser, Eva Rotenberg, and Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation [DOI] |
Luis Scoccola and Dmitriy Morozov Computing Betti Tables and Minimal Presentations of Zero-Dimensional Persistent Homology [DOI] |
||||
10:50-11:10 | Subhash Suri, Jie Xue, Dynamic Maximum Depth of Geometric Objects [DOI] |
Magnus B. Botnan and Extremal Betti Numbers and Persistence in Flag Complexes [DOI] |
||||
11:10-11:40 | Coffee Break | |||||
11:40–12:40 | SoCG Session 5A (Room B) Chair: Yoshio Okamoto |
SoCG Session 5B (Room C) Chair: Siu-Wing Cheng |
||||
11:40-12:00 | J. Mark Keil and Debajyoti Mondal The Maximum Clique Problem in a Disk Graph Made Easy [DOI] |
Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction [DOI] |
||||
12:00-12:20 | Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak,
Structure and Independence in Hyperbolic Uniform Disk Graphs [DOI] |
Peyman Afshani, Frank Staals, and Yakov Nekrich Convexity Helps Iterated Search in 3D [DOI] |
||||
12:20-12:40 | Timothy M. Chan, Chaya Keller, and Shakhar Smorodinsky On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects [DOI] |
k-Dimensional Transversals for Fat Convex Sets [DOI] |
||||
12:40-14:10 | Lunch Break | |||||
14:10-15:30 | SoCG Session 6A (Room B) Chair: Jie Gao |
SoCG Session 6B (Room C) Chair: Takeshi Tokuyama |
||||
14:10-14:30 | Herbert Edelsbrunner, Alexey Garber, and Morteza Saghafian On Spheres with k Points Inside [DOI] |
Helena Bergold, Lukas Egeling, and Hung Hoang Signotopes with Few Plus Signs [DOI] |
||||
14:30-14:50 | James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs [DOI] |
Abhibhav Garg, Rafael Oliveira, and Akash Kumar Sengupta Uniform Bounds on Product Sylvester-Gallai Configurations [DOI] |
||||
14:50-15:10 | Andrew Suk and Ethan White A Note on the No-(d+2)-on-a-Sphere Problem [DOI] |
Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers [DOI] |
||||
15:10-15:30 | Jeff Erickson and Shelling and Sinking Graphs on the Sphere [DOI] |
Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles [DOI] |
||||
15:30-15:50 | Coffee Break | |||||
15:50-16:40 | CG:MEDIA (Room A) |
15:50-17:50 |
Combinatorial Structures in Geometric Topology (Room B) |
|||
15:50-16:00 | Auguste Gezalyan, Nithin Parepally, Klint Faber, Adam Martinson, Aniruddh Mutnuru, Mihil Sreenilayam, Ryan Parker, Aram Zaprosyan, and David Mount French Onion Soup, Ipelets for Points and Polygons |
15:50-16:50 | Satoshi Murai An Introduction into Stanley Reisner Theory |
|||
16:00-16:10 | Simon D. Fink and Dominik Peters Incremental and Interactive PQ- and PC-trees |
|||||
16:10-16:20 | Auguste Gezalyan, Nithin Parepally, Megan Hunleth, Sarah Hwang, Lucy Wang, Olya Golovatskaia, Carmen Day, and Hridhaan Banerjee Software for the Thompson and Funk Polygonal Geometry |
|||||
16:20-16:30 | Uml Modular Robotics Group, Hugo Akitaya, Andrew Clements, Sam Downey, Jonathan Eisenbies, Saba Molaei, Soham Samanta, Gabriel Shahrouzi, and Frederick Stock Finding Shortest Reconfiguration Sequences for Modular Robots |
|||||
16:30-16:40 | Matthias Artmann, Tobias Maurer, Andreas Padalkin, Daniel Warner, and Christian Scheideler AmoebotSim 2.0: A Visual Simulation Environment for the Amoebot Model with Reconfigurable Circuits and Joint Movements |
|||||
16:40-17:40 | CG:Challenge (Room A) |
16:50-17:50 | Anastasiia Tsvietkova Algorithmic Knot Theory |
|||
|
||||||
17:50-19:20 | Business Meeting (Room A) | |||||
19:30- | Dinner |
Time | ||||||
---|---|---|---|---|---|---|
09:00-10:00 | Invited Talk: Tomohiro Tachi (The University of Tokyo) - Computational Origami for Art, Science, and Industry (Room A) Chair: Haitao Wang |
|||||
10:00-10:10 | Short Break | |||||
10:10–11:10 | SoCG Session 7A (Room B) Chair: Sang Won Bae |
SoCG Session 7B (Room C) Chair: Maarten Löffler |
||||
10:10-10:30 | Konrad Anand, Weiming Feng, Rapid Mixing of the Flip Chain over Non-Crossing Spanning Trees [DOI] |
Yasuaki Kobayashi, Recognizing 2-Layer and Outer k-Planar Graphs [DOI] |
||||
10:30-10:50 | Martin Balko and Jineon Baek The Erdős-Szekeres Conjecture Revisited [DOI] |
Embedding Graphs as Euclidean kNN-Graphs [DOI] |
||||
10:50-11:10 | David Eppstein Non-Euclidean Erdős–Anning Theorems [DOI] |
Matthias Bentert, Fedor Fomin, Petr A. Golovach, M. S. Ramanujan, and Saket
Saurabh When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations [DOI] |
||||
11:10-11:40 | Coffee Break | |||||
11:40–12:40 | SoCG Session 8A (Room B) Chair: Takeshi Tokuyama |
SoCG Session 8B (Room C) Chair: Tim Ophelders |
||||
11:40-12:00 | Tamal K. Dey, Decomposing Multiparameter Persistence Modules [DOI] |
Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D [DOI] |
||||
12:00-12:20 | Donghan Kim, Woojin Kim, and Super-Polynomial Growth of the Generalized Persistence Diagram [DOI] |
Sariel Har-Peled, Benjamin Raichel, and
The Fréchet Distance Unleashed: Approximating a Dog with a Frog [DOI] |
||||
12:20-12:40 | Mathieu Carrière, Seunghyun Kim, and Woojin Kim Sparsification of the Generalized Persistence Diagrams for Scalability through Gradient Descent [DOI] |
Siu-Wing Cheng, Haoqiang Huang, and Le Jiang Simplification of Trajectory Streams [DOI] |
||||
12:40-14:10 | Lunch Break | |||||
14:10–15:30 | SoCG Session 9A (Room B) Chair: Sujoy Bhore |
SoCG Session 9B (Room C) Chair: Francis Lazarus |
||||
14:10-14:30 | The Point-Boundary Art Gallery Problem is ∃R-hard [DOI] |
John Hershberger Snap Rounding: A Cautionary Tale [DOI] |
||||
14:30-14:50 | Ahmad Biniaz, Anil Maheshwari, Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems [DOI] |
Luca Castelli Aleardi, Eric
Fusy, Jyh-Chwen KO, and Razvan Stefan Puscasu Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice [DOI] |
||||
14:50-15:10 | A PTAS for TSP with Neighbourhoods Over Parallel Line Segments [DOI] |
Tim Ophelders, Anna Schenfisch, Willem Sonke, and Bettina Speckmann Computing Geomorphologically Salient Networks via Discrete Morse Theory [DOI] |
||||
15:10-15:30 | Erik Demaine and Stefan Langerman Tiling with Three Polygons is Undecidable [DOI] |
Sándor Fekete, Phillip Keldenich, and Michael Perk Exact Algorithms for Minimum Dilation Triangulation [DOI] |
||||
15:30-15:50 | Coffee Break | |||||
15:50-18:50 | Computational Geometry Washa-Washa (Room A) |
Geometric and Topological Graph Theory (Room B) |
Computational Polyhedral Geometry (Room C) |
|||
15:50-17:20 |
Connecting Artifacts Talk and Discussions
|
15:50-16:05 | Atsuyuki Miyashita Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem |
15:50-16:35 | Skip Jordan Projections, Redundancy and Parallelism in lrslib |
|
16:05-16:20 | Yuta Inoue Three-edge-coloring cubic graphs on the torus |
|||||
16:20-16:35 | Kengo Enami Embeddings of a graph into a surface with different weak chromatic numbers |
|||||
16:40-16:55 | Yoshio Okamoto Rerouting curves on the plane and other surfaces |
16:35-17:00 | Akiyoshi Tsuchiya Codegree of stable set polytopes |
|||
16:55-17:25 | Solomon Lo Minors of non-hamiltonian graphs |
17:00-17:25 | Germain Poullot The length of coherent monotone paths on polytopes admits a central limit theorem |
|||
17:20-18:50 | Networking "Washawasha" | 17:30-17:45 | Masuda Atsunori Minors and subdivisions in optimal 1-embedded graphs |
17:35-18:20 | Yue Ren Nonarchimedean optimization |
|
17:45-18:00 | Kenta Noguchi Face sizes and the connectivity of the dual |
|||||
18:05-18:20 | Henry Adams Nonexistence of Borsuk graph homomorphisms |
|||||
18:20-18:50 | Sean Dewar Erdős distance theory on graphs |
18:20-18:45 | Günter Rote Computing optimal lattice polygons |
Time | ||||||
---|---|---|---|---|---|---|
09:00-10:20 | SoCG Session 10A (Room B) Chair: Yoshio Okamoto |
SoCG Session 10B (Room C) Chair: Patrick Schnider |
||||
09:00-09:20 | Marzieh Eidi and Sayan Mukherjee Higher Order Bipartiteness vs Bi-Partitioning in Simplicial Complexes [DOI] |
Michael Hoffmann, Patrizio Angelini, Sabine
Cornelsen, Carolina Haase, Eleni Katsanou, Fabrizio Montecchiani, Raphael Steiner, and Antonios Symvonis Geometric Realizations of Dichotomous Ordinal Graphs [DOI] |
||||
09:20-09:40 | Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle Geometric Bipartite Matching Based Exact Algorithms for Server Problems [DOI] |
Jacob Fox, Janos Pach, and Andrew Suk Immersions and Albertson's Conjecture [DOI] |
||||
09:40-10:00 | Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, and David P. Woodruff Range Counting Oracles for Geometric Problems [DOI] |
Arnold Filtser On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications [DOI] |
||||
10:00-10:20 | Pankaj K Agarwal, Boris Aronov, Olivier Devillers, Christian Knauer, and Guillaume Moroz A Subquadratic Algorithm for Computing the L1-Distance between Two Terrains [DOI] |
Ahmad Biniaz, Jean-Lou De
Carufel, Anil Maheshwari, Michiel Smid, Shakhar Smorodinsky, and
Milos Stojakovic Polychromatic Coloring of Tuples in Hypergraphs [DOI] |
||||
10:20-10:50 | Coffee Break | |||||
10:50-12:10 | SoCG Session 11A (Room B) Chair: Birgit Vogtenhuber |
SoCG Session 11B (Room C) Chair: Bei Wang |
||||
10:50-11:10 | Therese Biedl, Éric
Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote Finding a Shortest Curve that Separates Few Objects from Many [DOI] |
Corentin Lunel, Arnaud de Mesmay, and Jonathan Spreer Hard Diagrams of Split Links [DOI] |
||||
11:10-11:30 | Shinwoo An, Eunjin Oh, and Jie Xue Single-Source Shortest Path Problem in Weighted Disk Graphs [DOI] |
Alexander He, Eric Sedgwick, and Jonathan Spreer A Practical Algorithm for Knot Factorisation [DOI] |
||||
11:30-11:50 | Timothy M. Chan and Zhengcheng Huang Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique [DOI] |
Tamal K. Dey, Tao Hou, and Dmitriy Morozov Apex Representatives [DOI] |
||||
11:50-12:10 | Édouard Bonnet and Paweł Rzążewski An 11/6-Approximation Algorithm for Vertex Cover on String Graphs [DOI] |
Lara Ost, Sebastiano Cultrera di
Montesano, and Herbert Edelsbrunner Banana Trees for the Persistence in Time Series Experimentally [DOI] |
||||
12:10–12:15 |
Short Break |
|||||
12:15-12:50 | Awards Ceremony and Closing (Room A) |
|||||
12:15-12:25 | ???: Test of Time Award Announcement | |||||
12:25-12:35 | ???: Test of Time Award Winner Comments | |||||
12:35-12:40 | ???: Best Student Presentation Award Announcement | |||||
12:40-12:50 | ???: Closing Words | |||||
12:50–14:10 |
Lunch Break |
|||||
14:10-17:10 | Combinatorial Structures in Geometric Topology (Room B) |
Uncertainty in Computational Geometry (Room C) |
||||
14:10-15:00 | Hidetoshi Masai Renormalized Volume of Hyperbolic 3-manifolds |
14:10-14:15 | Introduction | |||
14:15-14:55 | Tetsuo Asano Transportation Problem Using Localized Transportations |
|||||
15:00-15:50 | Stephan Tillmann Shortest Loops on Convex Projective Surfaces |
15:00-15:40 | Bei Wang Visualizing Structural Uncertainty of Ensemble Data: from Neuron Morphology to Asteroid Trajectories |
|||
15:50-16:20 | Eric Samperton TQFT Invariants of 3-manifolds |
16:00-16:20 | Bradley McCoy Imprecise Watchtowers |
|||
16:20-16:50 | Clément Maria Computational Hardness of Quantum 3-manifold Invariants |
16:20-16:40 | David Mount Algorithms for Processing Evolving Geometric Data |
|||
16:50-17:10 | Manuel Radons Topological features for author attribution |
16:40-17:00 | Sarah Wajsbrot Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization |
|||
??:??–??:?? |
Closing |