NDLI: Linkless and flat embeddings in 3-space and the unknot problem

Please wait, while we are loading the content...

Optimal partition trees

Discrete geometric structures for architecture

Better bounds on the union complexity of locally fat objects

Adding one edge to planar graphs makes crossing number hard

Visualizing 3D Euler spirals

A geometric approach to collective motion

Output-sensitive algorithm for the edge-width of an embedded graph

A traveller's problem

The complexity of the normal surface solution space

Klee's measure problem on fat boxes in time $∂(n^{(d+2)/3})$

The tidy set: a minimal simplicial set for computing homology of clique complexes

On degrees in random triangulations of point sets

Manifold reconstruction using tangential Delaunay complexes

Improving the first selection lemma in $R^{3}$

Applications of geometry and topology for quadrilateral meshprocessing and verifiable visualization

Computing planar Voronoi diagrams in double precision: a further example of degree-driven algorithm design

Incidences in three dimensions and distinct distances in the plane

Consistent digital line segments

On the complexity of sets of free lines and line segments among balls in three dimensions

Planar visibility: testing and counting

Shape approximation using k-order alpha-hulls

Kinetic stable Delaunay graphs

Finding shortest non-trivial cycles in directed graphs on surfaces

A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane

Distance k-sectors exist

An improved algorithm for computing the volume of the union of cubes

A randomized O(m log m) time algorithm for computing Reeb graphs of arbitrary simplicial complexes

Acute triangulations of polyhedra and the Euclidean space

Optimal reconstruction might be hard

Points with large quadrant-depth

3D Euler spirals for 3D curve completion

Tangencies between families of disjoint regions in the plane

The geometry of flocking

Lines avoiding balls in three dimensions revisited

The 2-center problem in three dimensions

Constructing Reeb graphs using cylinder maps

A kinetic triangulation scheme for moving points in the plane

Approximating loops in a shortest homology basis from point data

New constructions of SSPDs and their applications

Zone diagrams in Euclidean spaces and in other normed spaces

Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements

Topological inference via meshing

Dynamic well-spaced point sets

Reconstructing shapes with guarantees by unions of convex sets

Approximating the Fréchet distance for realistic curves in near linear time

I/O-efficient computation of water flow across a terrain

Steinitz theorems for orthogonal polyhedra

Tight lower bounds for halfspace range searching

Linkless and flat embeddings in 3-space and the unknot problem

Convexification of polygons by length preserving transformations

A dynamic data structure for approximate range searching

Geometric tomography with topological guarantees

Computing similarity between piecewise-linear functions

Geometric methods for multi-agent collision avoidance

Linkless and flat embeddings in 3-space and the unknot problem

Content Provider	ACM Digital Library
Author	Kawarabayashi, Ken-ichi Mohar, Bojan Kreutzer, Stephan
Abstract	We consider piecewise linear embeddings of graphs in 3-space $ℜ^{3}.$ Such an embbeding is linkless if every pair of disjoint cycles forms a trivial link (in the sense of knot theory). Robertson, Seymour and Thomas [47] showed that a graph has a linkless embedding in $ℜ^{3}$ if, and only if, it does not contain as a minor any of seven graphs in Petersen's family (graphs obtained from $K_{6}$ by a series of YΔ and ΔY operations). They also showed that a graph is linklessly embeddable in $ℜ^{3}$ if, and only if, it admits a flat embedding into $ℜ^{3},$ i.e. an embedding such that for every cycle C of G there exists a closed 2-disk D ⊆ $ℜ^{3}$ with D ∩ G = ∂D = C. Clearly, every flat embeddings is linkless, but the converse is not true. We first consider the following algorithmic problem associated with embeddings in $ℜ^{3}:$ Flat Embedding: For a given graph G, either detect one of Petersen's family graphs as a minor in G or return a flat (and hence linkless) embedding in $ℜ^{3}.$ The first outcome is a certificate that G has no linkless and no flat embeddings. Our first main result is to give an $O(n^{2})$ algorithm for this problem. While there is a known polynomial-time algorithm for constructing linkless embeddings [20], this is the first polynomial time algorithm for constructing flat embeddings in 3-space and we thereby settle a problem proposed by Lovasz [29]. We also consider the following classical problem in topology. The Unknot Problem: Decide if a given knot is trivial or not. This is a fundamental problem in knot theory and low dimensional topology, whose time complexity is unresolved. It has been extensively studied by researchers working in computational geometry. A related problem is: The Link Problem: Decide if two given knots form a link. Hass, Lagarias and Pippenger [16] observed that a polynomial time algorithm for the link problem yields a polynomial time algorithm for the unknot problem. We relate the link problem to the following problem that was proposed independently by Lovasz and by Robertson et al. Conjecture. (Lovasz [29]; Robertson, Seymour and Thomas [48]) There is a polynomial time algorithm to decide whether a given embedding of a graph in the 3-space is linkless. Affirming this conjecture would clearly yield a polynomial-time solution for the link problem. We prove that the converse is also true by providing a polynomial-time solution for the above conjecture, if we are given a polynomial time oracle for the link problem.
Starting Page	97
Ending Page	106
Page Count	10
File Format	PDF
ISBN	9781450300162
DOI	10.1145/1810959.1810975
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-13
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Flat embedding Knot Unknot Linkless embedding
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in