Salman Parsa
Current Address:
Ritter Hall
Deopartment of Computer Science
Saint Louis University, Saint Louis, MO. USA.
Welcome to my personal homepage!
Here are my research projects with published results (in Arxiv or peer-reviewed) in reverse chronological order:
How to Morph Graphs on the Torus 
with Erin Wolf Chambers, Jeff Erickson, Patrick 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.

On embeddability of joins and their `factors'
with A. Skopenkov
  We present a short and clear proof of the following particular case of a 2006 unpublished result of Melikhov-Schepin. Let K be a k-dimensional simplicial complex and K ∗ [3] the union of three cones over K along their common bases.  If 2d ≥ 3k + 3 and K ∗ [3] embeds into R^(d+2), then K embeds into R^d . We also present a generalization of this theorem. The proofs are based on the HaefligerWeber ‘configuration spaces’ embeddability criterion, equivariant suspension theorem and simple properties of joins and cones. 
On the Smith classes, the van Kampen obstruction and
 embeddability of [3]∗K 

In this survey-research paper, we first introduce the theory of Smith 
classes of complexes with fixed-point free, periodic maps on them. 
These classes, when defined for the deleted product of a simplicial 
complex K, are the same as the embedding classes of K. Embedding 
classes, in turn, are generalizations of the van Kampen obstruction 
class for embeddability of a d-dimensional complex K into the Euclidean 2d-space. All of these concepts will be introduced in simple 
terms.  Second, we use the theory introduced in the first part to relate the 
embedding classes (or the special Smith classes) of the the complex 
[3] ∗ K with the embedding classes of K. Here [3] ∗ K is the join of K 
with a set of three points. Specifically, we prove that if the m-th embedding class of K is nonzero, then the (m+2)-nd embedding class of [3]∗K is non-zero. We also prove some of the consequences of this theorem for the embeddability of [3] ∗ K.

Hardness of Contigous SAT and Visibility with Uncertain Obstacles
with Sh. Alipour

Consider SAT with the following restrictions. An input formula is in CNF form, and, there exists an ordering of the clauses in which clauses containing any fixed literal appear contiguously. We call this restricted SAT CONTIGUOUS SAT.  We also define the related problem SEGMENT COVER. In SEGMENT COVER, we are given a set of uncertain segments, each uncertain segment defined to be a random interval, chosen from two possible sub-intervals of the unit interval. Then, SEGMENT COVER asks if the probability of covering the entire unit interval is non-zero. We prove that SEGMENT COVER and hence CONTIGUOUS SAT are NP-hard. We further show that we can assume all intervals of SEGMENT COVER to be of equal lengths, this proves another problem called BCU to be NP-hard in dimension 1. Moreover, we also deduce hardness of approximation for CONTIGUOUS SAT and show it cannot have a PTAS, unless P= NP.
Deciding Contractibility Of Curves on Boundary of 3-Manifolds 
with É. Colin de Verdière. 
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:
Bounding the Number of d-Simplices of Embeddable Complexes  
In this research, the objects of study are simplicial complexes that are embeddable into Euclidean space. It is a well-known fact that if a graph (i.e. a 1-d simplicial complex) embeds into the plane, then it can have at most a linear number of edges, in terms of number of vertices. The first higher dimensional analog would be the problem of upper bounding the number of triangles in 2-dimensional simplicial complexes that embed into the four dimensional Euclidean space. It is a conjecture by many, including B. Gruenbaum and G. Kalai that the correct asymptotic upper bound is the number vertices to the power of 2. In a more concice statement the conjecture is that the upper bound is 4 tiems the number of edges. This problem seems far from resolved. 
In this work, I have given a critorion that the each intersection of link-complexes of three disjoint vertices of an embeddable complex must satisfy. This triple intersection is a subgraph of the 1-skeleton of given 2-complex. This graph has to be planar. In the paper I have also a weaker general statement for general dimension that is proved by means of elementary algebraic topology.  
This result is published in: 
S. Parsa, “On the Links of Vertices in Simplicial d-Complexes Embeddable in the Euclidean 2d-Space”, Discrete Comput Geom (2017).
Embedding Homotopy Types of 2-Complexes into 4-Space 
In this research, I have shown by a new proof that each homotopy type of a 2-dimensional simplicial complex has a member simplicial complex that embeds into 4-space. In particular, any finitely presented group appears as a fundamental group of a 2-complex PL embeded into 4-space. These result had been known before, and I have independently proven them. These embeddings can be built in linear time, that implies, knowing that a 2-complex is embeddable in 4-space does not help with regard to efficiency of algorithmic problems related to its fundamental group.  
The paper can be downloaded from here: 
“Small Model 2-Complexes in 4-space and Applications.” ArXiv e-prints, 1512.05152, 2015 
The Computational Complexity of Betti Numbers:
Reductions  from  Matrix Rank

with H. Edelsbrunner. 
n this paper we have shown that computing the betti numbers of 2-dimensional simplicial complexes is essentially equivalent to computing the rank of sparse matrices. In general, we reduced computing the rank of a matrix to computing the second betti number of a 2-complex, which can be even embeddable into 4-space.  
H. Edelsbrunner, S. Parsa, “On the computational complexity of Betti numbers: reductions from matrix rank”, Proceedings of the twenty-fifth annual ACM-SIAM Symposium On Discrete Algorithms. 2014, 152-160.

Dynamic Reeb Graphs 
In my PhD thesis I have given a general framework for an algorithm to update a Reeb graph under a change in the order of the vertices of the complex. However, it turns out that this problem cannot have a polylogarithmic algorithm, due to the fact that one can (almost!) model a dynamic graph connectiity problem using it. You can access my PhD thesis from the link below. 

An Efficient Algorithm for the Reeb Graph 
In this work, I gave an O(m log m) algorithm for computing the Reeb graph. Here m is the total number of simplices in the given simplicial complex. The input can be of arbitrary dimension. 
S. Parsa, “A Deterministic O ( m log m ) Time Algorithm for the Reeb Graph” . Discrete & Computational Geometry 49(4): 864-878 (2013) [ First version in SOCG 2012]. 
Please contact me if you need the code for this project.
An Efficient Algorithm for Raytracing 
with A. Shishegar. 
This is my first paper. It discusses a technique to accelerate the raytracing procedure where the environment is static. 
“A Ray Tracing Acceleration Technique for Wave Propagation Modeling”, Proc. IEEE Asia–Pacific Microwave Conference , 2009.