From: asimov@durban.berkeley.edu (Daniel Asimov)
Newsgroups: sci.math.research
Subject: Higher-Dimensional Version of Graph Planarity Criterion???
Date: 18 Sep 1996 18:05:03 GMT

According to Kuratowski, a finite graph (nodes and edges) can be topologically
embedded in the plane if and only if  it does not contain either of two
"forbidden" subgraphs (the complete graph on 5 vertices, and the water-gas-
electricity graph).

Now instead suppose we have a simplicial complex K that is the union of
2-simplices.  Does there exist a similar theorem giving conditions for when
|K| can be topologically embedded in R^3 ???

In generality, let K be a simplicial complex that is the union of p-simplices.
Are there criteria for when |K| can be topologically embedded in R^n ???

Any references to the literature would be appreciated.

--Dan Asimov
==============================================================================

From: greg@math.math.ucdavis.edu (Greg Kuperberg)
Newsgroups: sci.math.research
Subject: Re: Higher-Dimensional Version of Graph Planarity Criterion???
Date: 19 Sep 1996 01:02:30 GMT

In article <51pdkf$agc@agate.berkeley.edu> asimov@durban.berkeley.edu
(Daniel Asimov) writes:
>Now instead suppose we have a simplicial complex K that is the union of
>2-simplices.  Does there exist a similar theorem giving conditions for when
>|K| can be topologically embedded in R^3 ???

Yes and no.  It's extremely unlikely that there will ever be a pithy
condition analogous to Kuratowski's theorem.  The status of an
interesting special case illustrates why.

The link of any vertex in K is some graph which has to be planar for
for such an embedding to exist.  Suppose for simplicity that this
embedding is unique for all vertices.  Then you know the cyclic
ordering of faces coming into each edge, and if these cyclic orderings
are consistent, you can thicken K to get a 3-manifold with boundary.
So far everything is easy to check.

Now suppose for simplicity that when you thicken K, all boundary
components are spheres.  Plugging the holes, you are reduced to
deciding whether a given triangulated 3-manifold is S^3.  Until a few
years ago, it was not known whether this question is recursive, i.e.
whether there exists any algorithm at all to decide whether you have
S^3.  (In fact it's a theorem that there is no algorithm to recognize
S^5.)  But now there is an algorithm due to Hyam Rubinstein that fits
the bill.

Sketch of the algorithm:  A surface in a triangulated 3-manifold is
normal if and only if it intersects each tetrahedron in triangles and
quadrilaterals.  It is almost normal if in one simplex there is an
octagon which meets each face twice.  The algorithm dictates that you
should first look for a maximal collection of disjoint, non-parallel
normal spheres.  The manifold is a 3-sphere if and only if each region
bounded by exactly two normal spheres possesses an almost normal
sphere.

Reference:  Thompson, Thin position and Rubinstein's solution to the
recognition problem for S3, Mathematical Research Letters, 1, (1994)
-- 
   /\   Greg Kuperberg
  /  \  Department of Mathematics, UC Davis
  \  /  greg@math.ucdavis.edu
   \/   http://www.math.ucdavis.edu/~greg