Author name cluster

Eric Sedgwick

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

SODA Conference 2018 Conference Paper

Embeddability in ℝ 3 is NP-hard

Arnaud de Mesmay
Yo'av Rieck
Eric Sedgwick
Martin Tancer

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ 3 is NP -hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ 3 like unknot or 3-sphere recognition which are in NP ∩ co- NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

Details

SODA Conference 2018 Conference Paper

Tightening Curves on Surfaces via Local Moves

Hsien-Chih Chang
Jeff Erickson 0001
David Letscher
Arnaud de Mesmay
Saul Schleimer
Eric Sedgwick
Dylan Thurston
Stephan Tillmann

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω( n 2 ) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O ( n 2 ) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O ( n 4 ) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Details

STOC Conference 2002 Conference Paper

Recognizing string graphs in NP

Marcus Schaefer 0001
Eric Sedgwick
Daniel Stefankovic

A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP . The recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph [18, 20]. These results implied that the recognition problem lies in NEXP . In the present paper we improve this by showing that the recognition problem for string graphs is in NP , and therefore NP -complete, since Kratochvíl [12] showed that the recognition problem is NP -hard. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.

Details