Salman Parsa

Current Address:

Ritter Hall

Deopartment of Computer Science

Saint Louis University, Saint Louis, MO. USA.

email: salman.parsa@slu.edu

Ritter Hall

Deopartment of Computer Science

Saint Louis University, Saint Louis, MO. USA.

email: salman.parsa@slu.edu

Welcome to my personal homepage!

with E. Chambers, F. Lazarus, A. de Mesmay

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.

Accepted to SoCG 2021

with E. Chambers, J. Erickson, P. Lin

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.

Accepted to SODA 2021

In this project, we presented an exponential time algorithm for deciding the contractibilty of a closed curve with self-intersections on the boundary of a 3-manifold. The main idea is to extract the computational content of the proof of the Loop Theorem.

Preliminary version of the result is published in:

É. Colin de Verdière, S. Parsa, “Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold”, Proceedings of the twenty-eighth annual ACM-SIAM Symposium On Discrete Algorithms. 2017, 2691-2704

The journal version of the paper. This is a totally rewritten improved version: