Accepted Papers of SoCG 2025

The accepted paper list has now been posted on the conference website: https://socg25.github.io/socg.html#accepted_list

• Rapid mixing of the flip chain over non-crossing spanning trees

Konrad Anand (School of Informatics, University of Edinburgh); Weiming Feng (ETH Zürich); Graham Freifeld, Heng Guo (School of Informatics, University of Edinburgh); Mark Jerrum (Queen Mary, University of London); Jiaheng Wang (University of Regensburg)

• An 11/6-Approximation Algorithm for Vertex Cover on String Graphs

Édouard Bonnet (CNRS); Paweł Rzążewski (Warsaw University of Technology)

• On the Twin-Width of Smooth Manifolds
  Édouard Bonnet (CNRS, ENS de Lyon); Kristóf Huszár (Graz University of Technology)

• Certifying that a knot is composite

Alexander He (Oklahoma State University); Eric Sedgwick (DePaul University); Jonathan Spreer (The University of Sydney)

• When alpha-complexes collapse onto codimension-1 submanifolds
  Dominique Attali (Gipsa lab and CNRS); Mattéo Clémot (LIRIS and CNRS); Bianca Boeira Dornelas (Graz University of Technology - TU Graz); André Lieutier

• Simplification of Trajectory Streams

Siu-Wing Cheng, Haoqiang Huang (Hong Kong University of Science and Technology); Le Jiang (University of Science and Technology of China)

• A PTAS for TSP with Neighbourhoods Over Parallel Line Segments

Benyamin Ghaseminia, Mohammad R. Salavatipour (University of Alberta)

• A Sparse Multicover Bifiltration of Linear Size

Ángel Javier Alonso (Graz University of Technology)

• On Spheres with k Points Inside        

Herbert Edelsbrunner (Institute of Science and Technology Austria); Alexey Garber (University of Texas Rio Grande Valley); Morteza Saghafian (Institute of Science and Technology Austria)

• On Approximability of ℓp2 Min-Sum Clustering
  Karthik C. S. (Rutgers University); Euiwoong Lee (University of Michigan); Yuval Rabani (Hebrew University); Chris Schwiegelshohn (Aarhus University); Samson Zhou (Texas A&M University)

• Signotopes with few plus signs        

Helena Bergold (FU Berlin); Lukas Egeling (ETH Zurich); Hung Hoang (TU Wien)

• Small triangulations of 4-manifolds: Introducing the 4-manifold census

Rhuaidi Antonio Burke, Benjamin Burton (The University of Queensland); Jonathan Spreer (The University of Sydney)

• Recognizing 2-Layer and Outer k-Planar Graphs        

Yasuaki Kobayashi (Hokkaido University); Yuto Okada (Nagoya University); Alexander Wolff (Universität Würzburg)

• A Minor-Testing Approach for Coordinated Motion Planning with Sliding Robots

Eduard Eiben (Royal Holloway, University of London); Robert Ganian (TU Wien); Iyad Kanj (DePaul University); M. S. Ramanujan (University of Warwick)

• Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings

Mikkel Abrahamsen (University of Copenhagen); Kevin Buchin (TU Dortmund); Maike Buchin (Ruhr University Bochum); Linda Kleist (Universität Potsdam); Maarten Löffler (Utrecht University); Lena Schlipf (Universität Tuebingen); Andre Schulz (University of Hagen); Jack Stade (University of Copenhagen)

• Snap Rounding: A Cautionary Tale        

John Hershberger (Siemens)

• A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation        

Timothy M. Chan (UIUC); Isaac M. Hair (UCSB)

• Banana Trees for the Persistence in Time Series Experimentally        

Lara Ost (University of Vienna); Sebastiano Cultrera di Montesano (Broad Institute of MIT and Harvard); Herbert Edelsbrunner (Institute of Science and Technology Austria)

• Finding a Shortest Curve that Separates Few Objects from Many        

Therese Biedl (University of Waterloo); Éric Colin de Verdière (CNRS, Laboratoire d'Informatique Gaspard Monge, Marne-la-Vallée); Fabrizio Frati (Università di Roma Tre); Anna Lubiw (University of Waterloo); Günter Rote (Freie Universität Berlin)

• Uniform Bounds on Product Sylvester-Gallai Configurations        

Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo)

• Incremental Planar Nearest Neighbor Queries with Optimal Query Time        

John Iacono (Université libre de Bruxelles); Yakov Nekrich (Michigan Technological University)

• Hard diagrams of split links        

Corentin Lunel (Inria d'Université Côte d'Azur); Arnaud de Mesmay (CNRS, LIGM, Université Gustave Eiffel); Jonathan Spreer (The University of Sydney)

• The Fréchet Distance Unleashed: Approximating a Dog with a Frog
  Sariel Har-Peled (University of Illinois at Urbana-Champaign); Benjamin Raichel (University of Texas at Dallas); Eliot Robson (University of Illinois Urbana-Champaign)

• Tracking the Persistence of Harmonic Chains: Barcode and Stability        

Tao Hou (University of Oregon); Salman Parsa (DePaul University); Bei Wang (University of Utah)

• Tiling with Three Polygons is Undecidable        

Erik Demaine (MIT); Stefan Langerman (Universite libre de Bruxelles (ULB))

• On Zarankiewicz's Problem for Intersection Hypergraphs of Geometric Objects

Timothy M. Chan (UIUC); Chaya Keller (Ariel University); Shakhar Smorodinsky (Ben Gurion University of the NEGEV)

• Steinhaus Filtration and Stable Paths in the Mapper
  Dustin L Arendt (Pacific Northwest National Laboratory); Matthew Broussard (TD Bank USA); Bala Krishnamoorthy (Washington State University); Nathaniel Saul (Stripe USA); Amber Thrall (Washington State University)

• The Erdős-Szekeres Conjecture revisited
  Martin Balko (Charles University); Jineon Baek (University of Michigan)

• Lipschitz Decompositions of Finite ℓp​ Metrics
  Robert Krauthgamer, Nir Petruschka (Weizmann Institute of Science)

• Single-Source Shortest Path Problem in Weighted Disk Graphs
  Shinwoo An, Eunjin Oh (POSTECH); Jie Xue (NYU Shanghai)

• On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
  Arnold Filtser (Bar-Ilan University)

• Levels in arrangements: linear relations, the g-matrix, and applications to crossing numbers

Elizaveta Streltsova, Uli Wagner (Institute of Science and Technology Austria (ISTA))

• When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
  Matthias Bentert, Fedor Fomin, Petr A. Golovach (University of Bergen); M. S. Ramanujan (University of Warwick); Saket Saurabh (IMSc)

• Range Counting Oracles for Geometric Problems
  Anne Driemel (University of Bonn); Morteza Monemizadeh (Eindhoven University of Technology); Eunjin Oh (POSTECH); Frank Staals (Utrecht University); David P. Woodruff (Carnegie Mellon University)

• Sparsification of the Generalized Persistence Diagrams for Scalability through Gradient Descent
  Mathieu Carrière (Centre Inria d´Universite Cote d´Azur); Seunghyun Kim, Woojin Kim (KAIST)

• Super-Polynomial Growth of the Generalized Persistence Diagram
  Donghan Kim, Woojin Kim, Wonjun Lee (KAIST)

• The maximum number of digons formed by pairwise intersecting pseudocircles
  Eyal Ackerman (University of Haifa); Gábor Damásdi, Balázs Keszegh (ELTE, Alfréd Rényi Institute of Mathematics); Rom Pinchasi (Technion - Israel Institute of Technology, EPFL); Rebeka Raffay (EPFL)

• Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework
  Sang Won Bae (Kyonggi University); Nicolau Oliver (Università  della Svizzera italiana,); Evanthia Papadopoulou (Università  della Svizzera italiana)

• The Point-Boundary Art Gallery Problem is ∃R-hard
  Jack Stade (University of Copenhagen)

• Optimal Motion Planning for Two Square Robots in a Rectilinear Environment
  Pankaj K Agarwal (Duke University); Mark de Berg (Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands); Benjamin Holmgren, Alex Steiger (Department of Computer Science, Duke University); Martijn Struijs (TU Eindhoven)

• k-dimensional transversals for fat convex sets
  Attila Jung, Dömötör Pálvölgyi (ELTE Eötvös Loránd University)

• A Subquadratic Algorithm for Computing the L1-distance between Two Terrains
  Pankaj K Agarwal (Duke University); Boris Aronov (New York University); Guillaume Moroz (Inria)

• Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
  Timothy M. Chan, Zhengcheng Huang (University of Illinois at Urbana-Champaign); Shakhar Smorodinsky (Ben Gurion University of the NEGEV); Csaba D. Tóth (California State University Northridge); Sujoy Bhore (Indian Institute of Technology Bombay)

• Computing Geomorphologically Salient Networks via Discrete Morse Theory
  Tim Ophelders (Utrecht University and TU Eindhoven); Anna Schenfisch, Willem Sonke, Bettina Speckmann (TU Eindhoven)

• An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number
  Colleen Delaney (Purdue University); Clément Maria (INRIA - Université Côte d'Azur); Eric Samperton (Purdue University)

• Persistent (Co)Homology in Matrix Multiplication Time
  Dmitriy Morozov (Lawrence Berkeley National Laboratory); Primoz Skraba (Queen Mary University of London)

• Embedding Graphs as Euclidean kNN-Graphs
  Thomas Schibler (University of California, Santa Barbara); Subhash Suri (University of California, Santa Barbara); Jie Xue (NYU Shanghai, China)

• Immersions and Albertson's conjecture
  Jacob Fox (Stanford University); Janos Pach (EPFL, Lausanne and Renyi Institute); Andrew Suk (UCSD)

• A note on the no-(d+2)-on-a-sphere problem
  Andrew Suk (UCSD); Ethan White (UIUC)

• Improved Approximation Algorithms for Three-Dimensional Knapsack
  Klaus Jansen (Kiel University); Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas (Indian Institute of Science, Bengaluru); Malte Tutas (Kiel University)

• Computing Betti tables and minimal presentations of zero-dimensional persistent homology
  Luis Scoccola (Centre de Recherches Mathématiques); Dmitriy Morozov (Lawrence Berkeley National Laboratory)

• Apex Representatives
  Tamal K. Dey (Purdue University); Tao Hou (University of Oregon); Dmitriy Morozov (Lawrence Berkeley National Laboratory)

• Shelling and Sinking Graphs on the Sphere
  Jeff Erickson, Christian Howard (University of Illinois Urbana-Champaign)

• Non-Euclidean Erdős–Anning Theorems
  David Eppstein (Univ. of California, Irvine)

• Polychromatic Coloring of Tuples in Hypergraphs
  Ahmad Biniaz (University of Windsor); Jean-Lou De Carufel (University of Ottawa); Anil Maheshwari, Michiel Smid (Carleton University); Shakhar Smorodinsky (Ben Gurion University of the NEGEV); Milos Stojakovic (University of Novi Sad)

• Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems
  Ahmad Biniaz (University of Windsor); Anil Maheshwari (Carleton University); Magnus Christian Ring Merrild (Aarhus University); Joseph Mitchell (Stony Brook University); Saeed Odak (University of Ottawa) ; Valentin Polishchuk (Linköping University); Eliot W. Robson (University of Illinois at Urbana-Champaign); Casper Moldrup Rysgaard (Aarhus University); Jens Kristian Refsgaard Schou (Aarhus University); Tom Shermer (Simon Fraser University); Rolf Svenning (Aarhus University); Jack Spalding-Jamieson (Independent); Da Wei Zheng (University of Illinois at Urbana-Champaign)

• Dynamic Maximum Depth of Geometric Objects
  Subhash Suri (University of California, Santa Barbara); Jie Xue, Xiongxin Yang, Jiumu Zhu (New York University Shanghai)

• Sublinear Data Structure for Nearest Neighbor in Ultra High Dimensions
  Zihang Wu, Martin G. Herold, Danupon Nanongkai (Max Planck Institute for Informatics, Saarland Informatics Campus); Joachim Spoerhase (University of Liverpool); Nithin Varma (University of Cologne)

• Structure and Independence in Hyperbolic Uniform Disk Graphs
  Thomas Bläsius, Jean-Pierre von der Heydt (Karlsruhe Institute of Technology); Sándor Kisfaludi-Bak (Aalto University); Marcus Wilhelm (Karlsruhe Institute of Technology); Geert van Wordragen (Aalto University)

• Extremal Betti Numbers and Persistence in Flag Complexes
  Magnus B. Botnan, Lies Beers (Vrije Universiteit Amsterdam)

• Efficient Greedy Discrete Subtrajectory Clustering
  Ivor van der Hoog (Technical University of Denmark); Lara Ost (University of Vienna); Eva Rotenberg (Technical University of Denmark); Daniel Rutschmann (Technical University of Denmark)

• Geometric Realizations of Dichotomous Ordinal Graphs
  Michael Hoffmann (Department of Computer Science, ETH Zürich, Switzerland); Patrizio Angelini (John Cabot University); Sabine Cornelsen (University of Konstanz); Carolina Haase (Trier University); Eleni Katsanou (NTU Athens); Fabrizio Montecchiani (University of Perugia); Raphael Steiner (ETH Zurich); Antonios Symvonis (NTU Athens)

• Exact Algorithms for Minimum Dilation Triangulation
  Sándor Fekete, Phillip Keldenich, Michael Perk (TU Braunschweig)

• Approximating Klee’s Measure Problem and a Lower Bound for Union Volume Estimation
  Karl Bringmann (Saarland University and Max Planck Institute for Informatics); Kasper Green Larsen (Aarhus University, Denmark); André Nusser (CNRS, Inria, Université Côte d'Azur, France); Eva Rotenberg (Technical University of Denmark, DTU); Yanheng Wang (Saarland University and Max Planck Institute for Informatics)

• Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D
  Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe (University of Bonn); André Nusser (CNRS, Inria, Université Côte d'Azur); Marena Richter (University of Bonn)

• Computing Oriented Spanners and their Dilation
  Antonia Kalb, Kevin Buchin (TU Dortmund); Anil Maheshwari (Carleton University); Saeed Odak (University of Ottawa); Carolin Rehs (TU Dortmund); Michiel Smid (Carleton University); Sampson Wong (University of Copenhagen)

• Nearest Neighbor Searching in a Dynamic Simple Polygon
  Sarita de Berg (Utrecht Utrecht); Frank Staals (Utrecht University)

• The Maximum Clique Problem in a Disk Graph Made Easy
  J. Mark Keil, Debajyoti Mondal (University of Saskatchewan)

• Computation of toroidal Schnyder woods made simple and fast: from theory to practice
  Luca Castelli Aleardi (LIX, Ecole Polytechnique); Eric Fusy (Laboratoire d'Informatique Gaspard Monge); Jyh-Chwen KO, Razvan Stefan Puscasu (LIX, Ecole Polytechnique)

• Higher Order Bipartiteness vs Bi-Partitioning in Simplicial Complexes
  Marzieh Eidi (Max Planck Institute for Mathematics in the Sciences); Sayan Mukherjee (MPI MIS, Duke University)

• Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
  Timothy M. Chan (UIUC); Zhengcheng Huang (University of Illinois at Urbana-Champaign)

• A Theory of Sub-Barcodes
  Oliver Chubet (North Carolina State University); Kirk Gardner (AFRL); Donald Sheehy (North Carolina State University)

• Geometric spanners of bounded tree-width
  Kevin Buchin, Carolin Rehs, Torben Scheele (TU Dortmund)

• Convexity Helps Iterated Search in 3D
  Peyman Afshani (Aarhus University); Frank Staals (Utrecht University); Yakov Nekrich (Michigan Technological University)

• Geometric Bipartite Matching Based Exact Algorithms for Server Problems
  Sharath Raghvendra (North Carolina State University); Pouyan Shirzadian (Virginia Tech); Rachita Sowle (Virginia Commonwealth University)

• Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
  Shion Fukuzawa, Michael Goodrich, Sandy Irani (University of California, Irvine)

• Decomposing Multiparameter Persistence Modules
  Tamal K. Dey (Purdue University); Jan Jendrysiak, Michael Kerber (TU Graz)

• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
  James Davies (University of Cambridge); Agelos Georgakopoulos (University of Warwick); Meike Hatzel (Institute of Basic Science); Rose McCarty (Georgia Institute of Technology)