BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that {\sc Heegaard Genus ≤g}, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to g, is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem {\sc CNF-SAT} to {\sc Heegaard Genus ≤g}.
Let T be a triangulation of a set P of n points in the plane, and let e be an edge shared by two triangles in T such that the quadrilateral Q formed by these two triangles is convex. A {\em flip} of e is the operation of replacing e by the other diagonal of Q to obtain a new triangulation of P from T. The {\em flip distance} between two triangulations of P is the minimum number of flips needed to transform one triangulation into the other. The Flip Distance problem asks if the flip distance between two given triangulations of P is at most k, for some given k∈N. It is a fundamental and a challenging problem. We present an algorithm for the {\sc Flip Distance} problem that runs in time O(n+k⋅ck), for a constant c≤2⋅1411, which implies that the problem is fixed-parameter tractable. We extend our results to triangulations of polygonal regions with holes, and to labeled triangulated graphs.
This workshop about triangulations of manifolds in computational geometry and topology was held at the 2014 CG-Week in Kyoto, Japan. It focussed on computational and combinatorial questions regarding triangulations, with the goal of bringing together researchers working on various aspects of triangulations and of fostering a closer collaboration within the computational geometry and topology community. Triangulations are highly suitable for computations due to their clear combinatorial structure. As a consequence, they have been successfully employed in discrete algorithms to solve purely theoretical problems in a broad variety of mathematical research areas (knot theory, polytope theory, 2- and 3-manifold topology, geometry, and others). However, due to the large variety of applications, requirements vary from field to field and thus different types of triangulations, different tools, and different frameworks are used in different areas of research. This is why today closely related research areas are sometimes largely disjoint leaving potential reciprocal benefits unused. To address these potentials a workshop on Triangulations was held at Oberwolfach Research Institute in 2012. Since then many new collaborations between researchers of different mathematical communities have been established. Regarding the computational geometry community, the theory of manifolds continues to contribute to advances in more applied areas of the field. Many researchers are interested in fundamental mathematical research about triangulations and thus will benefit from a broad set of knowledge about different research areas using different techniques. We hope that this workshop brought together researchers from many different fields of computational geometry to have fruitful discussions which will lead to new interdisciplinary collaborations and solutions.
We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, i.e., an essential curve in the boundary of X bounding a disk in S3∖X with length bounded by a computable function of the number of tetrahedra of X.
We consider two systems of curves (α1,...,αm) and (β1,...,βn) drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism of M; more precisely, we seek a homeomorphism ϕ:M→M fixing the boundary of M pointwise such that the total number of crossings of the αi with the ϕ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h≥0 boundary components ("holes"), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g, we obtain an O((m+n)4) upper bound, again independent of h and g. The proofs rely, among others, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov.
We show that a strongly irreducible and boundary-strongly irreducible surface can be isotoped to be almost normal in a triangulated 3-manifold.
Let M be a 3-manifold with torus boundary components T1 and T2. Let ϕ:T1→T2 be a homeomorphism, Mϕ the manifold obtained from M by gluing T1 to T2 via the map ϕ, and T the image of T1 in Mϕ. We show that if ϕ is "sufficiently complicated" then any incompressible or strongly irreducible surface in Mϕ can be isotoped to be disjoint from T. It follows that every Heegaard splitting of a 3-manifold admitting a "sufficiently complicated" JSJ decomposition is an amalgamation of Heegaard splittings of the components of the JSJ decomposition.
We show that after generic filling along a torus boundary component of a 3-manifold, no two closed, 2-sided, essential surfaces become isotopic, and no closed, 2-sided, essential surface becomes inessential. That is, the set of essential surfaces (considered up to isotopy) survives unchanged in all suitably generic Dehn fillings. Furthermore, for all but finitely many non-generic fillings, we show that two essential surfaces can only become isotopic in a constrained way.
We show that every thin position for a connected sum of small knots is obtained in an obvious way: place each summand in thin position so that no two summands intersect the same level surface, then connect the lowest minimum of each summand to the highest maximum of the adjacent summand below.
Let M be a closed, irreducible, genus two 3-manifold, and F a maximal collection of pairwise disjoint, closed, orientable, incompressible surfaces embedded in M. Then each component manifold M_i of M-F has handle number at most one, i.e. admits a Heegaard splitting obtained by attaching a single 1-handle to one or two components of boundary M_i. This result also holds for a decomposition of M along a maximal collection of incompressible tori.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.