In this work, we introduce and study what we believe is an intriguing, and, to the best of our knowledge, previously unknown connection between two fundamental areas in computational topology, namely topological data analysis (TDA) and knot theory. Given a function from a topological space to \(\mathbb R\), TDA provides tools to simplify and study the importance of topological features: in particular, the \(l^{th}\)-dimensional persistence diagram encodes the topological changes (or \(l\)-homology) in the sublevel set as the function value increases into a set of points in the plane. Given a continuous one parameter family of such functions, we can combine the persistence diagrams into an object known as a vineyard, which tracks the evolution of points in the persistence diagram as the function changes. If we further restrict that family of functions to be periodic, we identify the two ends of the vineyard, yielding a closed vineyard. This allows the study of monodromy, which in this context means that following the family of functions for a period permutes the set of points in a non-trivial way. Recent work has studied monodromy in the directional persistent homology transform, demonstrating some interesting connections between an input shape and monodromy in the persistent homology transform for 0-dimensional homology embedded in \(\mathbb R^2\).

A fixed set of vertices in the plane may have multiple planar straight-line triangulations in which the degree of each vertex is the same. As such, the degree information does not completely determine the triangulation. We show that even if we know, for each vertex, the number of neighbors in each of the four cardinal directions, the triangulation is not completely determined. We show that counting such triangulations is #P-hard via a reduction from #3-regular bipartite planar vertex cover. pty

on Computational Geometry (SoCG'23) was held at The University of Texas at Dallas, USA, from June 12 to 15, 2023, as part of Computational Geometry Week (CG Week).This special issue of Discrete & Computational Geometry features a selection of papers presented at the symposium.Out of 175 submissions to SoCG'23, 61 were accepted for presentation.From these, seven particularly outstanding papers were selected for inclusion in this issue.The papers span diverse areas in computational geometry and topology, including graph drawing, topological data analysis, approximation algorithms, and parameterized complexity.Each paper was submitted, reviewed, and revised in accordance with the journal's high standards.We are grateful to the anonymous referees for their time and effort in verifying and improving these contributions.We also thank the authors for their thoughtful revisions and careful polishing of their work.The papers in this special issue appear in alphabetical order according to the names of the first authors.In the remainder of this foreword, we briefly introduce all accepted papers.Our first paper is "Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets", by Ángel Javier Alonso and Michael Kerber.In this work, the authors study zero-dimensional persistence modules, giving a decomposition based at the level of sets rather than vector spaces.This formalization allows for a more combinatorial study of the problem, and they are able to identify intervals in persistence that correspond to clusters of points.Using this framework, they give a lower bound for the number of intervals for density-Rips filtrations in Euclidean space, allowing for new and exciting practical insights into the behavior of these commonly used data sets.

Abstract. We describe algorithms to efficiently compute minimum [Formula: see text]-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph [Formula: see text] with [Formula: see text] vertices embedded on an orientable surface of genus [Formula: see text], our algorithms can solve either problem in [Formula: see text] or [Formula: see text] time, whichever is better. When [Formula: see text] is a constant, our [Formula: see text] time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given [Formula: see text]-homology class, and we give efficient algorithms for this latter problem as well. If [Formula: see text] is embedded on a surface with genus [Formula: see text] and [Formula: see text] boundary components, these algorithms run in [Formula: see text] and [Formula: see text] time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing that it is likely impossible to improve upon the exponential dependencies on [Formula: see text] for this latter problem.

Homology features of spaces which appear in applications, for instance 3D meshes, are among the most important topological properties of these objects. Given a non-trivial cycle in a homology class, we consider the problem of computing a representative in that homology class which is optimal. We study two measures of optimality, namely, the lexicographic order of cycles (the lex-optimal cycle) and the bottleneck norm (a bottleneck-optimal cycle). We give a simple algorithm for computing the lex-optimal cycle for a 1-homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3-manifolds of size n² in the Euclidean 3-space, the problem of finding a bottleneck optimal cycle cannot be solved more efficiently than solving a system of linear equations with an n × n sparse matrix. From this reduction, we deduce several hardness results. Most notably, we show that for 3-manifolds given as a subset of the 3-space of size n², persistent homology computations are at least as hard as rank computation (for sparse matrices) while ordinary homology computations can be done in O(n² log n) time. This is the first such distinction between these two computations. Moreover, it follows that the same disparity exists between the height persistent homology computation and general sub-level set persistent homology computation for simplicial complexes in the 3-space.

This paper is motivated by a practical problem: many U.S. states have public hearings on "communities of interest" as part of their redistricting process, but no state has as yet adopted a concrete method of spatializing and aggregating community maps in order to take them into account in the drawing of new boundaries for electoral districts. Below, we describe a year-long project that collected and synthesized thousands of community maps through partnerships with grassroots organizations and/or government offices. The submissions were then aggregated by geographical clustering with a modified Hausdorff distance; then, the text from the narrative submissions was classified with semantic labels so that short runs of a Markov chain could be used to form semantic sub-clusters. The resulting dataset is publicly available, including the raw data of submitted community maps as well as post-processed community clusters and a scoring system for measuring how well districting plans respect the clusters. We provide a discussion of the strengths and weaknesses of this methodology and conclude with proposed directions for future work.

Abstract We present a method for removing unwanted topological features (e.g., islands, handles, cavities) from a sequence of shapes where each shape is nested in the next. Such sequences can be found in nature, such as a multi‐layered material or a growing plant root. Existing topology simplification methods are designed for single shapes, and applying them independently to shapes in a sequence may lose the nesting property. We formulate the nesting‐constrained simplification task as an optimal labelling problem on a set of candidate shape deletions (“cuts”) and additions (“fills”). We explored several optimization strategies, including a greedy heuristic that sequentially propagates labels, a state‐space search algorithm that is provably optimal, and a beam‐search variant with controllable complexity. Evaluation on synthetic and real‐world data shows that our method is as effective as single‐shape simplification methods in reducing topological complexity and minimizing geometric changes, and it additionally ensures nesting. Also, the beam‐search strategy is found to strike the best balance between optimality and efficiency.

In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the complexity of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve γ, and a collection of disjoint normal curves Δ, there is a polynomial-time algorithm to decide if γ lies in the normal subgroup generated by components of Δ in the fundamental group of the surface after attaching the curves to a basepoint.

In this paper, we introduce an extension of smoothing on Reeb graphs, which we call truncated smoothing; this in turn allows us to define a new family of metrics which generalize the interleaving distance for Reeb graphs. Intuitively, we "chop off" parts near local minima and maxima during the course of smoothing, where the amount cut is controlled by a parameter $τ$. After formalizing truncation as a functor, we show that when applied after the smoothing functor, this prevents extensive expansion of the range of the function, and yields particularly nice properties (such as maintaining connectivity) when combined with smoothing for $0 \leq τ\leq 2\varepsilon$, where $\varepsilon$ is the smoothing parameter. Then, for the restriction of $τ\in [0,\varepsilon]$, we have additional structure which we can take advantage of to construct a categorical flow for any choice of slope $m \in [0,1]$. Using the infrastructure built for a category with a flow, this then gives an interleaving distance for every $m \in [0,1]$, which is a generalization of the original interleaving distance, which is the case $m=0$. While the resulting metrics are not stable, we show that any pair of these for $m,m' \in [0,1)$ are strongly equivalent metrics, which in turn gives stability of each metric up to a multiplicative constant. We conclude by discussing implications of this metric within the broader family of metrics for Reeb graphs.

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in O(n1+ω/2) time, where ω is the matrix multiplication exponent, and the computed morph consists of O(n) parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairns' original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte's spring embedding theorem to torus graphs.

We present a novel algorithm for simplifying the topology of a 3D shape, which is characterized by the number of connected components, handles, and cavities. Existing methods either limit their modifications to be only cutting or only filling, or take a heuristic approach to decide where to cut or fill. We consider the problem of finding a globally optimal set of cuts and fills that achieve the simplest topology while minimizing geometric changes. We show that the problem can be formulated as graph labelling, and we solve it by a transformation to the Node-Weighted Steiner Tree problem. When tested on examples with varying levels of topological complexity, the algorithm shows notable improvement over existing simplification methods in both topological simplicity and geometric distortions.

While we celebrate the dramatic increase in women's undergraduate enrollment at computer science programs around the country, to see this surge translate into career-long outcomes, we cannot ignore ongoing gendered and racialized disparities in computing, particularly as they relate to a student's sense of belonging. Even in times of high enrollment, fostering a sense of belonging cannot occur just through ad-hoc methods, the goodwill of a few faculty, or a standalone mentoring program. Policies and structures must be put into place and enacted holistically. We report on a multi-phase, 10-year case study of undergraduate student experiences at the University of Illinois (2007, n=61; 2017, n=339). Our 2017 study explores the policies and structures enacted over a decade and their impact on departmental culture. We report on three areas: i) Inclusive classroom experiences; ii) Quality of mentorship opportunities; iii) Student sense of identity. While there have been significant departmental improvements, there are some cultural, policy, and structural issues to be addressed in order to foster a sense of belonging and success for all students.

In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves γ1 and γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between γ1 and γ2 where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Fréchet Distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.

Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.

An important task in trajectory analysis is defining a meaningful representative for a cluster of similar trajectories. Formally defining and computing such a representative r is a challenging problem. We propose and discuss two new definitions, both of which use only the geometry of the input trajectories. The definitions are based on the homotopy area as a measure of similarity between two curves, which is a minimum area swept by all possible deformations of one curve into the other. In the first definition we wish to minimize the maximum homotopy area between r and any input trajectory, whereas in the second definition we wish to minimize the sum of the homotopy areas between r and the input trajectories. For both definitions computing an optimal representative is NP-hard. However, for the case of minimizing the sum of the homotopy areas, an optimal representative can be found efficiently in a natural class of restricted inputs, namely, when the arrangement of trajectories forms a directed acyclic graph.

While playing a fundamental role in shape understanding, the medial axis is known to be sensitive to small boundary perturbations. Methods for pruning the medial axis are usually guided by some measure of significance. The majority of significance measures over the medial axes of 3D shapes are locally defined and hence unable to capture the scale of features. We introduce a global significance measure that generalizes in 3D the classical Erosion Thickness (ET) measure over the medial axes of 2D shapes. We give precise definition of ET in 3D, analyze its properties, and present an efficient approximation algorithm with bounded error on a piece-wise linear medial axis. Experiments showed that ET outperforms local measures in differentiating small boundary noise from prominent shape features, and it is significantly faster to compute than existing global measures. We demonstrate the utility of ET in extracting clean, shape-revealing and topology-preserving skeletons of 3D shapes.

Abstract Calculating and categorizing the similarity of curves is a fundamental problem which has generated much recent interest. However, to date there are no implementations of these algorithms for curves on surfaces with provable guarantees on the quality of the measure. In this paper, we present a similarity measure for any two cycles that are homologous, where we calculate the minimum area of any homology (or connected bounding chain) between the two cycles. The minimum area homology exists for broader classes of cycles than previous measures which are based on homotopy. It is also much easier to compute than previously defined measures, yielding an efficient implementation that is based on linear algebra tools. We demonstrate our algorithm on a range of inputs, showing examples which highlight the feasibility of this similarity measure.

Let $G$ be a directed graph with n vertices embedded on an orientable surface of genus g with two designated vertices s and t. We show that counting the minimum (s,t)-cuts in G is fixed parameter tractable in g. Specially, we give a 2O(g) n2 time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are few prior results that are fixed parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample a minimum cut uniformly at random in O(gn) time per sample.

Measuring the similarity of curves is a fundamental problem arising in many application fields. There has been considerable interest in several such measures, both in Euclidean space and in more general setting such as curves on Riemannian surfaces or curves in the plane minus a set of obstacles. However, so far, efficiently computable similarity measures for curves on general surfaces remain elusive. This paper aims at developing a natural curve similarity measure that can be easily extended and computed for curves on general orientable 2-manifolds. Specifically, we measure similarity between homotopic curves based on how hard it is to deform one curve into the other one continuously, and define this "hardness" as the minimum possible surface area swept by a homotopy between the curves. We consider cases where curves are embedded in the plane or on a triangulated orientable surface with genus $g$, and we present efficient algorithms (which are either quadratic or near linear time, depending on the setting) for both cases.

Let $G$ be a directed graph with $n$ vertices and nonnegative weights in its directed edges, embedded on a surface of genus $g$, and let $f$ be an arbitrary face of $G$. We describe a randomized algorithm to preprocess the graph in $O(gn \log n)$ time with high probability, so that the shortest-path distance from any vertex on the boundary of $f$ to any other vertex in $G$ can be retrieved in $O(\log n)$ time. Our result directly generalizes the $O(n\log n)$-time algorithm of Klein [Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of $f$. As an application of our algorithm, we describe algorithms to compute a shortest noncontractible or nonseparating cycle in embedded, undirected graphs in $O(g^2 n\log n)$ time with high probability. Our high-probability time bounds hold in the worst case for generic edge weights or with an additional $O(\log n)$ factor for arbitrary edge weights.

We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given a graph embedded on a surface of genus $g$, with two specified vertices $s$ and $t$ and integer edge capacities that sum to $C$, our algorithm computes a maximum $(s,t)$-flow in $O(g^8 n\log^2 n\log^2 C)$ time. We also present a combinatorial algorithm that takes $g^{O(g)} n^{3/2}$ arithmetic operations. Except for the special case of planar graphs, for which an $O(n\log n)$-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. For graphs of any fixed genus, our algorithms improve these time bounds by roughly a factor of $\sqrt{n}$. Our key insight is to optimize the homology class of the flow, rather than directly optimizing the flow itself; two flows are in the same homology class if their difference is a weighted sum of directed facial cycles. A dual formulation of our algorithm computes the minimum-cost circulation in a given (real or integer) homology class.

Abstract Thinning is a commonly used approach for computing skeleton descriptors. Traditional thinning algorithms often have a simple, iterative structure, yet producing skeletons that are overly sensitive to boundary perturbations. We present a novel thinning algorithm, operating on objects represented as cell complexes, that preserves the simplicity of typical thinning algorithms but generates skeletons that more robustly capture global shape features. Our key insight is formulating a skeleton significance measure, calledmedial persistence, which identify skeleton geometry at various dimensions (e.g., curves or surfaces) that represent object parts with different anisotropic elongations (e.g., tubes or plates). The measure is generally defined in any dimensions, and can be easily computed using a single thinning pass. Guided by medial persistence, our algorithm produces a family of topology and shape preserving skeletons whose shape and composition can be flexible controlled by desired level of medial persistence.

We describe the first algorithms to compute minimum cuts in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a minimum (s,t)-cut in gO(g) n log n time. Except for the special case of planar graphs, for which O(n log n)-time algorithms have been known for more than 20 years, the best previous time bounds for finding minimum cuts in embedded graphs follow from algorithms for general sparse graphs. A slight generalization of our minimum-cut algorithm computes a minimum-cost subgraph in every Z2-homology class. We also prove that finding a minimum-cost subgraph homologous to a single input cycle is {NP}-hard.

We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s,t)-flow in O(g7 n log2 n log2 C) time for integer capacities that sum to C, or in (g log n)O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

A Roman dominating function of a graph G is a labeling $f\colon\,V(G)\to\{0,1,2\}$ such that every vertex with label 0 has a neighbor with label 2. The Roman domination number $\gamma_R(G)$ of G is the minimum of $\sum_{v\in V(G)}f(v)$ over such functions. Let G be a connected n-vertex graph. We prove that $\gamma_R(G)\leq4n/5$, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for $\gamma_R(G)+\gamma_R(\overline{G})$ and $\gamma_R(G)\gamma_R(\overline{G})$, improving known results for domination number. We prove that $\gamma_R(G)\leq8n/11$ when $\delta(G)\geq2$ and $n\geq9$, and this is sharp.

The (Vietoris-)Rips complex of a discrete point-set P is an abstract simplicial complex in which a subset of P defines a simplex if and only if the diameter of that subset is at most 1. We describe an efficient algorithm to determine whether a given cycle in a planar Rips complex is contractible. Our algorithm requires O(m log n) time to preprocess a set of n points in the plane in which m pairs have distance at most 1; after preprocessing, deciding whether a cycle of k Rips edges is contractible requires O(k) time. We also describe an algorithm to compute the shortest non-contractible cycle in a planar Rips complex in O(n2log n + mn) time.

The Fréchet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Fréchet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over the obstacles ("trees"). We describe a polynomial-time algorithm to compute the homotopic Fréchet distance between two given polygonal curves in the plane minus a given set of obstacles, which are either points or polygons.

Computer science is seeing a decline in enrollment at all levels of education. One key strategy for reversing this decline is to improve methods of student retention. This paper, based on a 10-month case study at the Department of Computer Science at the University of Illinois at Urbana-Champaign, examines two aspects of student retention at both the graduate and undergraduate levels: community identity and community relationships. Our data shows that students feel isolated from each other, faculty, and members of the greater computer science community. Given our findings, we highlight existing programs and propose new programs which improve student-community interactions. While the lessons learned might not apply at every institution, they constitute a valuable case study for improving conditions for students at large research universities.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.