Is there a polyhedron with a small number of vertices which is homeomorphic
to the gholed torus? Does it embed in R^3? Here is some correspondence
with [Permission pending] in which the respondent provides a program
to determine some of this [note that there are _no_ embeddings of nonorientable
surfaces in R^3, polyhedral or otherwise]. I include a literature review.
==============================================================================
Date: Sat, 11 Mar 1995 01:17:27 0800 (PST)
From: [Permission pending]
To: rusin@math.niu.edu
Subject: various minimal polyhedra
Dave,
I looked at the minimal number of vertices that you need to
form a polyhedron which is topologically a compact connected 2manifold.
It was rather surprising that you do not need many extra vertices to
get extra holes in your donuts, the number of vertices which is
given by the E <= V*(V1)/2 constraint seems to be enough for many more
negative Euler characteristics.
[sig deleted  djr]
Here are the minimal numbers of vertices needed:
Euler characteristic Orientable Nonorientable
2 4
1 6
0 7 8
1 9
2 10 9
3 9
4 10 10
5 10
6 11 11
==============================================================================
Date: Tue, 21 Mar 1995 09:45 PST
From: [Permission pending]
Subject: polyhedra
To: rusin@math.niu.edu
Dave,
I wrote a computer program which triangulates 2manifolds  I'm sending it
to you.
I sent a mail message about the minimal polyhedra to you, wasn't sure if you
got it.
I liked the 6vertex Boy surface. Does that triangulation seem as
suggestive of a Boy surface to you as it does to me?
Also it came up with a *three* hole 10vertex torus. I wonder if *that's*
embeddable.
...
[sig deleted  djr]
program triangle
c find triangulations given #vertices and Euler characteristic.
implicit none
integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge,
. Vertices, Nvertices, V,E,F, Nb_edges, orient,
. first_edge
logical dupl_edges, want_orientable
common / / simp (100, 3), Edges (100, 175, 2), Nedges(100),
. from(100), NF, NV, NE, vert, edge, dupl_edges,
. Vertices (100,100), Nvertices (100), V,E,F, Nb_edges,
. want_orientable, orient (100), first_edge (100,2)
character*1 choice
integer EC, I(100), J(100), K, L
integer cnt
c function definitions
logical checkface, trim_tree, orientable
vert = 1 !tags that keep track of your path in the tree.
edge = 2
write (6,*) 'Number of vertices?'
read (5,*) V
write (6,*) 'Euler characteristic?'
read (5,*) EC
write (6,*) 'Orientable? Y or N'
read (5,'(a)') choice
if (choice.eq.'Y'.or.choice.eq.'y') then
want_orientable = .true.
write (6,*) 'Will look for an orientable manifold'
else
want_orientable = .false.
write (6,*) 'Will look for a nonorientable manifold'
end if
write (6,*)
if (V.le.EC) stop 'No go'
if (V.lt.4) stop 'No go'
F = (VEC)*2
E = (VEC)*3
NF = 1 !also is level of recursion
NV = 3
simp (1,1) = 1
simp (1,2) = 2
simp (1,3) = 3
10 continue
c write (7,*) 'Simplex ', cnt+1
c if (cnt+1.eq.1999) then
c write (7,*) ((simp(K,L), L = 1,3), K = 1, NF1)
c pause
c end if
call boundary !sets Edges
c !array & finds #edges for
c !Euler char.
cnt = cnt + 1
c write (7,*) 'nf,ne,nv,nedges(nf), nvertices(nf), nb_edges'
c write (7,*) nf,ne,nv,nedges(nf), nvertices(nf), nb_edges
c write (7,'(a, 2i3)') 'first_edge ', (first_edge (NF, K), K = 1, 2)
c write (7,'(a,20(i3))') ' Simplex', (simp(nf,K), K=1,3)
c write (7,'(a,20(2i3,2x))')
c . ' Edges', ((edges(nf, K,L), L=1,2), K=1, nedges(nf))
c write (7,'(a,20(i3))')
c . ' Vertices', (Vertices(nf, K), K=1, nvertices(nf))
c write (7,*)
if ((.not.dupl_edges).and.
. NF.eq.F.and.NE.eq.E.and.NV.eq.V.and.Nedges(NF).eq.0) then
if (.not.want_orientable) then
orient(1) = 1
do K = 2, NF
orient (K) = 0
end do
if (orientable()) then
NF = NF  1
if (from(NF+1).eq.Vert) NV = NV  1
goto 20 !back in recursion
end if
end if
write (6,*) 'Triangulation:'
do K = 1, NF
write (6,'(3i3)') (simp (K, L), L= 1, 3)
end do
write ( 6,*) cnt, ' nodes of the tree were looked at'
stop
end if
c
if (trim_tree()) then
NF = NF  1
if (from(NF+1).eq.Vert) NV = NV  1
if (NF.eq.0) then
write (6,*) cnt, ' nodes of the tree were looked at'
stop 'No triangulation'
end if
goto 20 !back one recursion level
end if
c
c Loop through edges list and vertices list, make new simplexes.
J(NF) = 0 !loop index on vertices to connect to
21 continue !top of loop
J(NF) = J(NF) + 1
if (J(NF).gt.Nvertices(NF)) goto 29 !out of loop
if (checkface (first_Edge(NF, 1),
. first_EDGE (NF, 2),
. Vertices(NF, J(NF)))) goto 10
c !down one level of recursion
c checkface makes new simplex if everything is OK.
20 continue !returning from recursion
goto 21 !bottom of J(NF) loop
29 continue !exit from J(NF) loop
if (NF.gt.1) then !go back to node of tree you came from
NF = NF  1
if (from(NF+1).eq.Vert) NV = NV  1
goto 20 !back one recursion level
end if
c
write (6,*) 'No triangulation'
write (6,*) cnt, ' nodes of the tree were looked at'
stop
end
c
subroutine boundary
implicit none
integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge,
. Vertices, Nvertices, V,E,F, Nb_edges, orient,
. first_edge
logical dupl_edges, want_orientable
common / / simp (100, 3), Edges (100, 175, 2), Nedges(100),
. from(100), NF, NV, NE, vert, edge, dupl_edges,
. Vertices (100,100), Nvertices (100), V,E,F, Nb_edges,
. want_orientable, orient (100), first_edge (100,2)
integer t1, t2, t3, I, J, code_ij
integer code_edge (0:175*175)
dupl_edges = .false.
NE = 0
Nb_edges = 0
do I = 1, NV*NV
code_edge(I) = 0
end do
do I = 1, NF
t1 = simp(I,1) 1 + NV*(simp(I,2)1) !store edges in
!base NV code.
code_edge ( t1) = code_edge (t1) + 1 !simplexes have vertices
c !in ascending order
t2 = simp(I,1) 1 + NV*(simp(I,3)1)
code_edge (t2) = code_edge (t2) + 1
t3 = simp(I,2) 1 + NV*(simp(I,3)1)
code_edge (t3) = code_edge (t3) + 1
end do
Nedges(NF) = 0
do I = 1, NV*NV
if (code_edge(I).gt.2) then
dupl_edges = .true.
return
end if
if (code_edge(I).gt.0) NE = NE + 1
if (mod (code_edge (I), 2).ne.0) then
Nedges(NF) = Nedges(NF) + 1
Edges (NF, Nedges(NF), 1) = mod (I, NV) + 1
Edges (NF, Nedges(NF), 2) = I  Edges (NF, Nedges(NF), 1) + 1
Edges (NF, Nedges(NF), 2) = Edges (NF, Nedges(NF), 2)/ NV + 1
end if
end do
Nvertices (NF) = 0 !list of vertices on the edge
do I = 1, 100
Vertices(NF, I) = 0
end do
do I = 1, Nedges (NF)
do J = 1,2
Vertices(NF, Edges(NF, I,J)) =
. Vertices (NF, Edges(NF, I,J)) + 1
end do
end do
do I = 1, NV
if (Vertices (NF, I).eq.1)
. write (6,*) 'Sheesh! Vertex is at only one edge, nf is', nf
if (Vertices (NF,I).gt.0) then
Nvertices (NF) = Nvertices (NF) + 1
Vertices (NF,Nvertices(NF)) = I
end if
end do
first_edge (NF, 1) = Vertices (NF, 1)
first_edge (NF, 2) = V
do I = 1, Nedges (NF)
if (Edges (NF, I, 1).eq.Vertices (NF, 1))
. first_edge (NF, 2) = min (first_edge (NF, 2), Edges (NF, I, 2)) !find the "smallest" edge
end do
c Now check to see how many edges are between vertices on the
c boundary.for trimming the tree later.
do I = 1, Nvertices (NF)
do J = I+1, Nvertices (NF)
code_ij = Vertices(NF,I)1 +
. NV * (Vertices(NF,J)1)
if (Code_edge(code_ij).ne.0) nb_edges = nb_edges + 1
end do
end do
if (NV.lt.V) then
Nvertices (NF) = Nvertices (NF) + 1
Vertices (NF,Nvertices(NF)) = NV + 1
end if
return
end
logical function Checkface (v1,v2, v3)
implicit none
integer v1, v2, v3
integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge,
. Vertices, Nvertices, V,E,F, Nb_edges, orient,
. first_edge
logical dupl_edges, want_orientable
common / / simp (100, 3), Edges (100, 175, 2), Nedges(100),
. from(100), NF, NV, NE, vert, edge, dupl_edges,
. Vertices (100,100), Nvertices (100), V,E,F, Nb_edges,
. want_orientable, orient (100), first_edge (100,2)
integer s1, s2, s3, I, J, t1, t2
c a function.
logical pinch
checkface = .false.
if (v3.eq.v1.or.v3.eq.v2) return
c
if (v3.lt.v1) then !sort vertices
s1 = v3
s2 = v1
s3 = v2
elseif (v3.lt.v2) then
s1 = v1
s2 = v3
s3 = v2
else
s1 = v1
s2 = v2
s3 = v3
end if
c Is there already a face for these three vertices?
do I = 1, NF
if (simp(I,1).eq.s1.and.simp(I,2).eq.s2.and.simp(I,3).eq.s3)
. return
end do
c
c check to see if we'd be making a pinchpoint
if (pinch(v1,v2,v3)) then
c write (7,*) 'Pinchpoint'
c write (7,'(a,100(2i3,2x))')
c . 'Edges are', ((Edges(NF, I, J), J = 1, 2), I = 1, Nedges(NF))
c write (7,*) 'Pinchpoint at', v2
c write (7,*) 'Edge & vertex that''re being tossed out', v1,v2,v3
c write (7,*)
return
end if
if (pinch(v2,v1,v3)) then
c write (7,*) 'Pinchpoint'
c write (7,'(a,100(2i3,2x))')
c . 'Edges are', ((Edges(NF, I, J), J = 1, 2), I = 1, Nedges(NF))
c write (7,*) 'Pinchpoint at', v1
c write (7,*) 'Edge & vertex that''re being tossed out', v1,v2,v3
c write (7,*)
return
end if
if (pinch(v1,v3,v2)) then
c write (7,*) 'Pinchpoint'
c write (7,'(a,100(2i3,2x))')
c . 'Edges are', ((Edges(NF, I, J), J = 1, 2), I = 1, Nedges(NF))
c write (7,*) 'Pinchpoint at', v3
c write (7,*) 'Edge & vertex that''re being tossed out', v1,v2,v3
c write (7,*)
return
end if
c make a new face.
checkface = .true.
NF = NF + 1
simp (NF, 1) = s1
simp (NF, 2) = s2
simp (NF, 3) = s3
if (v3.eq.NV+1) then
NV = NV+1
from (NF) = vert
else
from (NF) = edge
end if
return
end
logical function trim_tree
implicit none
integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge,
. Vertices, Nvertices, V,E,F, Nb_edges, orient,
. first_edge
logical dupl_edges, want_orientable
common / / simp (100, 3), Edges (100, 175, 2), Nedges(100),
. from(100), NF, NV, NE, vert, edge, dupl_edges,
. Vertices (100,100), Nvertices (100), V,E,F, Nb_edges,
. want_orientable, orient (100), first_edge (100,2)
integer S1, S2, S3, S4, DV, DE, DF, Dedges
c function definition.
logical orientable
trim_tree = .true.
if (NF.eq.F) return
if (dupl_edges) return
if (nedges(nf).eq.0) return
c Now. There are 4 basic triangling operatings:
c S1: add vertex: NF > NF+1, NE > NE+2, NV > NV+1, Nedges >
c Nedges+1
c S2: add edge: NF > NF+1, NE > NE+2, Nedges > Nedges+1
c S3: fill in boundary: NF > NF+1, NE > NE+1, Nedges > Nedges1
c S4: fill in a triangle: NF > NF+1, Nedges > Nedges3
c
c This means that we can decide whether the current list of simplexes
c can lead to the desired triangulation.
DV = VNV
DE = ENE
DF = FNF
if (abs(DVDE+DF).gt.DF) return !Euler characteristic too much off
Dedges =  Nedges(NF)
S1 = DV !# of S1 operations
do S2 = 0, max (FLOAT(DFS1), (DE2*S1)/2.0)+1 !try values for S2
S3 = DE  2*S1  2*S2
if (S3.lt.0) goto 9
S4 = DF  S1  S2  S3
if (S4.lt.1) goto 9 !must have at least one of these.
goto 10
9 continue
end do
return !trim the tree
10 continue
c Now, are there enough exposed vertices left over to give you the
c necessary extra edges & faces?
if (Vertices(NF, Nvertices(NF)).eq.NV+1) then
DV = DV + Nvertices(NF)  1 !# of vertices on the boundary
else !plus unused ones.
DV = DV + Nvertices(NF)
end if
if ((DV*(DV1)/2) + NE  Nb_edges.lt.E) return !can only make
!new edges from
!these vertices
if (want_orientable.and..not.orientable()) return
trim_tree = .false.
return
end
logical function Pinch (v1,v2, v3)
implicit none
integer v1, v2, v3
integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge,
. Vertices, Nvertices, V,E,F, Nb_edges, orient,
. first_edge
logical dupl_edges, want_orientable
common / / simp (100, 3), Edges (100, 175, 2), Nedges(100),
. from(100), NF, NV, NE, vert, edge, dupl_edges,
. Vertices (100,100), Nvertices (100), V,E,F, Nb_edges,
. want_orientable, orient (100), first_edge (100,2)
integer s1,s2,s3, I, match, edge_cnt
integer edge_list(175,2)
logical edge_tag(175)
c This function tells if v2 would be a pinch point with this new
c triangulation.
pinch = .false.
c is (v2,v3) an edge on the boundary?
s2 = min (v2,v3)
s3 = max (v2,v3)
do I = 1, Nedges (NF)
if (Edges(NF,I,1).eq.s2.and.Edges(NF,I,2).eq.s3) goto 10
end do
return ! (v2,v3) is not on the boundary
10 continue
c
do I = 1, Nedges (NF)
if (Edges (NF,I,1).eq.v2.and.
. (Edges(NF,I,2).ne.v1.and.Edges(NF,I,2).ne.v3)) goto 15 !keep on
!looking.
if (Edges (NF,I,2).eq.v2.and.
. (Edges(NF,I,1).ne.v1.and.Edges(NF,I,1).ne.v3)) goto 15
end do
14 return !no pinch point
15 continue !keep on looking
c is (v1,v2) an edge on the boundary?
s1 = min (v1,v2)
s2 = max (v1,v2)
do I = 1, Nedges (NF)
if (Edges(NF,I,1).eq.s1.and.Edges(NF,I,2).eq.s2) goto 20
end do
return ! (v1,v2) is not on the boundary
20 continue
c
c Now are we forming a cycle of simplexes around v2?
edge_cnt = 0
do I = 1, NF
if (simp(I,1).eq.v2) then
edge_cnt = edge_cnt + 1
edge_list (edge_cnt,1) = simp(I,2)
edge_list (edge_cnt,2) = simp(I,3)
elseif (simp(I,2).eq.v2) then
edge_cnt = edge_cnt + 1
edge_list (edge_cnt,1) = simp(I,1)
edge_list (edge_cnt,2) = simp(I,3)
elseif (simp(I,3).eq.v2) then
edge_cnt = edge_cnt + 1
edge_list (edge_cnt,1) = simp(I,1)
edge_list (edge_cnt,2) = simp(I,2)
end if
end do
do I = 1, edge_cnt
edge_tag(I) = .true.
end do
c Now see if there's a cycle around v2. Starting with v1, can you get to
c v3?
match = v1
30 continue
do I = 1, edge_cnt
if (edge_tag(I)) then
if (edge_list(I,1).eq.match) then
match = edge_list (I,2)
edge_tag(I) = .false.
if (match.eq.v3) then !has to be a pinch point, we
!know some single edges with
!v2 remain.
pinch = .true.
return
end if
goto 30
elseif (edge_list(I,2).eq.match) then
match = edge_list (I,1)
edge_tag(I) = .false.
if (match.eq.v3) then
pinch = .true.
return
end if
goto 30
end if
end if
end do
return !no pinch point is being made
end
logical function orientable
implicit none
integer Edges, simp, Nedges, NF, NV, NE, from, vert, edge,
. Vertices, Nvertices, V,E,F, Nb_edges, orient,
. first_edge
logical dupl_edges, want_orientable
common / / simp (100, 3), Edges (100, 175, 2), Nedges(100),
. from(100), NF, NV, NE, vert, edge, dupl_edges,
. Vertices (100,100), Nvertices (100), V,E,F, Nb_edges,
. want_orientable, orient (100), first_edge (100,2)
integer bdry (100*100)
integer t1, t2, t3, I, J
orientable = .true.
if (NF.eq.1) then
orient (NF) = 1
return
end if
orient (NF) = 0 !unset this to reset in this function.
c first sum up the simplexes for which we already have orientation.
do I = 1, NV*NV
bdry (I) = 0
end do
do I = 1, NF
if (orient(I).eq.0) goto 9 !end of simplexes for
c !which orientation was
c !found
t1 = simp(I,1) 1 + NV*(simp(I,2)1) !store edges in
!base NV code.
bdry ( t1) = bdry (t1) + orient(I) !simplexes have vertices
c !in ascending order
t2 = simp(I,1) 1 + NV*(simp(I,3)1)
bdry (t2) = bdry (t2)  orient(I)
t3 = simp(I,2) 1 + NV*(simp(I,3)1)
bdry (t3) = bdry (t3) + orient(I)
end do
9 continue
do J = I, NF
if (orient(J).eq.0) then
c Now add on the J'th simplex
t1 = simp(J,1) 1 + NV*(simp(J,2)1)
t2 = simp(J,1) 1 + NV*(simp(J,3)1)
t3 = simp(J,2) 1 + NV*(simp(J,3)1)
if (bdry(t1).eq.1) then
orient (J) = 1
elseif(bdry(t1).eq.1) then
orient (J) = 1
elseif (bdry (t2).eq.1) then
orient (J) = 1
elseif (bdry (t2).eq.1) then
orient (J) = 1
elseif (bdry (t3).eq.1) then
orient (J) = 1
elseif (bdry (t3).eq.1) then
orient (J) = 1
end if
if (orient(J).ne.0) then
bdry (t1) = bdry (t1) + orient (J)
bdry (t2) = bdry (t2)  orient (J)
bdry (t3) = bdry (t3) + orient (J)
if (bdry (t1).eq.2.or.bdry(t1).eq.2) then
orientable = .false.
return
end if
if (bdry (t2).eq.2.or.bdry(t2).eq.2) then
orientable = .false.
return
end if
if (bdry (t3).eq.2.or.bdry(t3).eq.2) then
orientable = .false.
return
end if
else
write (6,*) 'Orientation wasn''t found ...'
end if
end if
end do
return
end
==============================================================================
Date: Tue, 21 Mar 95 14:05:32 CST
From: rusin (Dave Rusin)
To: [Permission pending]
Subject: Re: polyhedra
[Salutation deleted  djr]
Your recent work sent me to do a more thorough literature review. Here
are the reviews of the (eleven) articles I found which appear
relevant. I haven't read them yet but it appears people have recently
been looking at precisely the issues you have. Below they're sorted by
date, but I'll mention the ones I think you might find particularly
interesting:
#2  major work! shows the eulerformula minimum is in fact all you need for
a combinatorial manifold with the right genus.
This appears to be the same problem your program addresses, that is, the
embedding of the mfld into R^n is not considered. For embeddings into
R^n we might, in principle, require more vertices. However,
#3  proves 10 vertices are minimal for both 2 and 3holed tori, for
embeddings in R^3.
#6  like #3, but with more symmetry
#7  like #6, but for genus 4. (Notes that genus 6 is open).
I take it it is still unknown whether the combinatorial manifolds can be
linearly embedded into R^3 for genus 5 or more. Asked another way, I take
it the minimum value of n such that the combinatorial manifold linearly
embeds in R^n is unknown for these genera.
One can ask the same question about nonorientable surfaces, for which
n>=4 is necessary. However, one author considered the possibility of an
_immersion_ into R^n; there it seems conceivable that n=3 is enough.
However, I take it this is not possible at least for the projective plane:
#9  minimal polyhedral immersion of RP^2 (using 9 vertices)
Some authors extend the problem in different ways, for example:
#1  "minimal" torus, klein bottle, KB minus one face, but with slightly new
definition of "minimal".
#4  extending to some 3D manifolds
#5  extending to ndim manifolds, namely the ncube
#8  extending to polyhedra with quadrangles, not triangles
There is also a summary (#10) and another paper whose role in this I cannot
discern from the review (#11).
dave
[output from MathSci disc attached]
MathSci Disc 1980  1987 1 of 11
MR 81c:57003 
AU Schulz,Ch.; Wills,J.M. 
TI Kleinste kleinsche Flaschen mit Rand. 
PY 1979 
JN Geom.Dedicata [GeometriaeDedicata] 8 (1979), no. 4, 395406. 
LA German 
PC 57M20, 57M, 57 
SC 52A25, 52A, 52 
RL MEDIUM; (24 lines) 
AB A ''realisation'' of a 2manifold M will mean a subspace C of some
Euclidean space E{sup}d (d >= 3) such that M is homeomorphic to C and
each face of C is a convex polygonal disc. If C has f{sub}0 vertices,
f{sub}1 edges and f{sub}2 faces, the fvector f(C) of C is the triple
(f{sub}0, 3f {sub}1, 3f{sub}2) with norm f{sub}0+f{sub}1+f{sub}2. The
authors consider the problem of finding the ''minimal'' possible
realisation C in the sense that f(C) has least norm. They give
references to solutions of the problem when M is the torus, Mobius
band or Klein bottle B, and address themselves to the case when M is
the result L of removing one face from B. A comprehensive theorem is
proved, which states that (a) every realisation K of L has f{sub}0 >=
7, f{sub}1 >= 14, f{sub}2 >= 5 and cannot attain all three bounds
simultaneously; (b) in E{sup}3 there are four realisations K{sub}1,
K{sub}2, K{sub}3, K{sub}4 of L, each unique to within isomorphism,
such that f(K {sub}1)=(7, 3

RE Griffiths,H.B.; (Southampton) 
RT Signedreview 
DE *(57M20) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); Lowdimensionaltopology; Twodimensionalcomplexes 
DE (52A25) Convexanddiscretegeometry; Generalconvexity; Polyhedraandpolytopes 
DT Journal 
IS 03044637 
CO GEMDAT 
AN 553677 (553677001) 
MRI 81; 81c 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1980  1987 2 of 11
MR 82b:57012 
AU Jungerman,M.; Ringel,G. 
TI Minimal triangulations on orientable surfaces. 
PY 1980 
JN ActaMath. [ActaMathematica] 145 (1980), no. 12, 121154. 
LA English 
PC 57Q15, 57Q, 57 
SC 05C10, 05C, 05 
RL MEDIUM; (21 lines) 
AB A polyhedron on S, a compact 2manifold, is called a triangulation
if each face is a triangle with 3 distinct vertices and the
intersection of any two distinct triangles is either empty, a single
vertex, or a single edge. Let delta (S) denote the minimum number of
triangles in any triangulation of S. The second author determined
delta (S) for nonorientable S (Math. Ann. 130 (1955), 317  326; MR
17, 774). A routine application of Euler's formula shows that if S is
an orientable surface of genus p, then delta (S) >= 4(p 
1)+2((7+{radlin}1+48p))/2). It is the authors' considerable
achievement to show that equality holds except when p=2 (here delta
(S)=24). They assert, ''The proof of the formula is a problem similar
in nature and at least equivalent in complexity to the problem of
determining the genus of the complete graph K{sub}n. In both problems
one must exhibit triangular embeddings of graphs which are complete or
nearly complete (where some edges are m

RE Albertson,MichaelO.; (Northampton, Mass.) 
RT Signedreview 
DE *(57Q15) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); PLtopology; Triangulatingmanifolds 
DE (05C10) Combinatorics (For finite fields, see 11Txx); Graphtheory (For applications of graphs, see 68Q90, 68R10, 90C35, 94C15); Topologicalgraphtheory,imbedding (See also 57M15, 57M25) 
DT Journal 
IS 00015962 
CO ACMAA8 
AN 586595 (586595001) 
MRI 82; 82b 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1980  1987 3 of 11
MR 82i:52017 
AU Brehm,Ulrich 
TI Polyeder mit zehn Ecken vom Geschlecht drei. 
PY 1981 
JN Geom.Dedicata [GeometriaeDedicata] 11 (1981), no. 1, 119124. 
LA German 
PC 52A25, 52A, 52 
SC 57Q15, 57Q, 57 
RL SHORT; (7 lines) 
AB Let F be a closed, orientable surface of genus g, and let e(g) be
the minimal number of vertices of a triangulation of F by an embedding
polyhedron. Then e(g) <= h(g) with h(g) := {1/2}[7+(1+48g){sup}(1/2)]
(g {neq}2), and h(2) := 10. For g=0 (trivially) and g=1 (by a result
of Czaszar) the equation e(g)=h(g) holds. The author shows the
equations e(2)=h(2)=10 and e(3)=h(3)=10 by an interesting construction
of a polyhedron of genus 3 with 10 vertices.

RE Hertel,E.; (Jena) 
RT Signedreview 
DE *(52A25) Convexanddiscretegeometry; Generalconvexity; Polyhedraandpolytopes 
DE (57Q15) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); PLtopology; Triangulatingmanifolds 
DT Journal 
IS 03044637 
CO GEMDAT 
AN 608166 (608166001) 
MRI 82; 82i 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1980  1987 4 of 11
MR 86a:52012 
AU Kuhnel,Wolfgang, (DTUB); Lassmann,Gunter, (DTUB) 
TI The rhombidodecahedral tessellation of $3$space and a particular $15$vertex triangulation of the $3$dimensional torus. 
PY 1984 
JN ManuscriptaMath. [ManuscriptaMathematica] 49 (1984), no. 1, 6177. 
LA English 
PC 52A25, 52A, 52 
SC 52A45, 52A, 52; 57M99, 57M, 57; 57Q15, 57Q, 57 
RL SHORT; (10 lines) 
AB A highly symmetric triangulation of the 3dimensional torus
$S\sp 1\times S\sp 1\times S\sp 1$ is given. This triangulation has
15 vertices, all the (120) possible edges, and its symmetry group
is of order 120. It is studied (in analogy to the minimal
triangulation of the 2dimensional torus) from different points of
view: combinatorial, algebraic, topological and geometricthe last
seems to be the most interesting. In particular it is shown that
this simplicial complex is the quotient of a particular tessellation
of 3space by a translation group. Each vertex star is a
rhombidodecahedron, the dual of a (semiregular) cuboctahedron.

RE Altshuler,A.; (ILBGUN) 
RT Signedreview 
DE *(52A25) Convexsetsandrelatedgeometrictopics; Polyhedraandpolytopes 
DE (52A45) Convexsetsandrelatedgeometrictopics; Packing,covering,tiling (See also 05B40, 05B45, 11H31, 51XX); (57M99) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); Lowdimensionaltopology (old 55Axx); Topicsnotcoveredbyotherclassificationsinthissubsection; (57Q15) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); PLtopology; Triangulatingmanifolds 
DT Journal 
IS 00252611 
CO MSMHB2 IN (DTUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany 
AN CMP762787 (762787001) 
MRI 86; 86a 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1980  1987 5 of 11
MR 87d:52011 
AU Lee,CarlW., (1KY) 
TI Triangulating the $d$cube. 
TIC Collection: Discrete geometry and convexity (New York, 1982), 205211 
SE Ann. New York Acad. Sci., 440, 
PY 1985 
PUBL New York Acad. Sci., New York, 1985. 
LA English 
PC 52A25, 52A, 52 
SC 52A37, 52A, 52 
RL MEDIUM; (11 lines) 
AB A triangulation of a cube is a triangulation into closed simplices
whose vertices are vertices of the cube. P. S. Mara
[``Triangulations of the cube'', Master's Sci. Thesis, Colorado
State Univ., Fort Collins, Colo., 1972; per bibl.] gave a
triangulation of the 4cube into 16 simplices. Several
recent articles have shown it is minimal and the author here gives
another proof of this fact. He also goes on to describe two
general methods of triangulating arbitrary polytopes: by
``pulling'' vertices and by ``placing'' vertices. The first
method is also used to give a new description of a triangulation
due to J. F. Sallee [Discrete Appl. Math. 4
(1982), no. 3, 211215; MR 84g:52019] for the 5cube.
\{For the entire collection see MR 86g:52002.\}

RE Sallee,G.T.; (Davis, Calif.) 
RT Signedreview 
DE *(52A25) Convexsetsandrelatedgeometrictopics; Polyhedraandpolytopes 
DE (52A37) Convexsetsandrelatedgeometrictopics; Otherproblemsofcombinatorialgeometry 
DT ProceedingsPaper 
IN (1KY), Department of Mathematics, University of Kentucky, Lexington, Kentucky 40506 
XN 86g:52002 
XP 809185 
AN CMP809208 (809208001) 
MRI 87; 87d 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1988  1992 6 of 11
MR 89b:52012 
AU Brehm,Ulrich, (DTUB) 
TI A maximally symmetric polyhedron of genus $3$ with $10$ vertices. 
PY 1987 
JN Mathematika [Mathematika.AJournalofPureandAppliedMathematics] 34 (1987), no. 2, 237242. 
LA English 
PC 52A25, 52A, 52 
SC 51M20, 51M, 51; 52A37, 52A, 52; 57M20, 57M, 57 
RL SHORT; (3 lines) 
AB The author constructs a polyhedron with ten vertices
of genus 3 and with three axes of symmetry, which is
the maximal possible symmetry. Ten is the minimal number
of vertices which a polyhedron of genus 3 can have.

RE Wills,J.M.; (DSGN) 
RT Signedreview 
DE *(52A25) Convexsetsandrelatedgeometrictopics; Polyhedraandpolytopes 
DE (51M20) Geometry (For algebraic geometry, see 14XX); Realandcomplexgeometry; Polyhedraandpolytopes;regularfigures,division ofspaces (See also 51F15); (52A37) Convexsetsandrelatedgeometrictopics; Otherproblemsofcombinatorialgeometry; (57M20) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); Lowdimensionaltopology (old 55Axx); Twodimensionalcomplexes 
DT Journal 
IS 00255793 
CO MTKAAB 
IN (DTUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany 
AN CMP933502 (933502001) 
MRI 89; 89b 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1988  1992 7 of 11
MR 90a:52008 
AU Bokowski,Jurgen, (DDARM); Brehm,Ulrich, (DTUB) 
TI A polyhedron of genus $4$ with minimal number of vertices and maximal symmetry. 
PY 1989 
JN Geom.Dedicata [GeometriaeDedicata] 29 (1989), no. 1, 5364. 
LA English 
PC 52A25, 52A, 52 
SC 51M20, 51M, 51 
RL SHORT; (7 lines) 
AB The authors construct a polyhedron of genus 4 in $\bold R\sp 3$
with 11 vertices (and no selfintersections). This shows that also for
genus 4 (as for $g=1,2,3$) the minimal numbers of vertices of
combinatorial manifolds and of polyhedra coincide. The polyhedron has
a symmetry group of order 2, which is maximal for genus 4 and 11
vertices. The result is a step forward in the famous open problem of
the existence of a polyhedron of genus 6 with 12 vertices in $\bold
R\sp 3$.

RE Wills,J.M.; (DSGN) 
RT Signedreview 
DE *(52A25) Convexsetsandrelatedgeometrictopics; Polyhedraandpolytopes 
DE (51M20) Geometry (For algebraic geometry, see 14XX); Realandcomplexgeometry; Polyhedraandpolytopes;regularfigures,division ofspaces (See also 51F15) 
DT Journal 
IS 00465755 
CO GEMDAT 
IN (DDARM), FB Mathematik, TH Darmstadt, 6100 Darmstadt, Federal Republic of Germany; (DTUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany 
AN CMP989187 (989187001) 
MRI 90; 90a 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1988  1992 8 of 11
MR 90j:57003 
AU Hartsfield,Nora, (1UCSC); Ringel,Gerhard, (1UCSC) 
TI Minimal quadrangulations of nonorientable surfaces. 
PY 1989 
JN J.Combin.TheorySer.A [JournalofCombinatorialTheory.SeriesA] 50 (1989), no. 2, 186195. 
LA English 
PC 57M15, 57M, 57 
SC 05C10, 05C, 05 
RL MEDIUM; (11 lines) 
AB Introduction: ``Let $N$ be a compact 2manifold. A polyhedron on
$N$ is called a quadrangulation if each face of the polyhedron
is a quadrangle (square) with four distinct vertices; no two
vertices are joined by more than one edge, and the intersection
of any two distinct squares is either empty or at most one
edge and at most three vertices. A quadrangulation of $N$ is
called minimal if the number of squares is minimal. We denote the
number of squares in a minimal quadrangulation of $N$ by
$\psi(N)$. We construct quadrangular embeddings of $K\sb n$
for $n\equiv 1\pmod 4$ and the general octahedral graph.
Both of these embeddings determine polyhedra which are
minimal quadrangulations of the surfaces.''

RN Introduction 
RT Abstract 
DE *(57M15) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); Lowdimensionaltopology (old 55Axx); Relationswithgraphtheory (See also 05Cxx) 
DE (05C10) Combinatorics (For finite fields, see 11Txx); Graphtheory (For applications of graphs, see 68Q90, 68R10, 94C15); Topologicalgraphtheory,imbedding (See also 57M15, 57M25) 
DT Journal 
IS 00973165 
CO JCBTA7 
IN (1UCSC), Department of Mathematics, University of California, Santa Cruz, California, 95064 
AN CMP989193 (989193001) 
MRI 90; 90j 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1988  1992 9 of 11
MR 91h:52007 
AU Brehm,Ulrich, (DTUB) 
TI How to build minimal polyhedral models of the Boy surface. 
PY 1990 
JN Math.Intelligencer [TheMathematicalIntelligencer] 12 (1990), no. 4, 5156. 
LA English 
PC 52B70, 52B, 52 
SC 53A05, 53A, 53; 53C42, 53C, 53 
RL SHORT; (9 lines) 
AB Any simplexwise linear immersion of the real projective plane into
Euclidean 3space must have a triple point, so there must be three
disjoint triangles in the original triangulation. Therefore any such
triangulation must have at least nine vertices. In this paper, it is
shown that the lower bound is achieved by exhibiting three combinatorially
distinct polyhedral immersions of the real projective plane with exactly
nine vertices. The article is accompanied by instructions for building
cardboard models of the extraordinary immersions, and photographs display
the wellconstructed models.

RE Banchoff,T.; (1BRN) 
RT Signedreview 
DE *(52B70) Convexanddiscretegeometry; Polytopesandpolyhedra; Polyhedralmanifolds 
DE (53A05) Differentialgeometry (For differential topology, see 57Rxx. For foundational questions of differentiable manifolds, see 58Axx); Classicaldifferentialgeometry; SurfacesinEuclideanspace; (53C42) Differentialgeometry (For differential topology, see 57Rxx. For foundational questions of differentiable manifolds, see 58Axx); Globaldifferentialgeometry (See also 51H25, 58XX; for related bundle theory, see 55Rxx, 57Rxx); Immersions (minimal, prescribed curvature, tight, etc.) (See also 49Q05, 49Q10, 53A10, 57R40, 57R42) 
DT Journal 
IS 03436993 
CO MAINDC 
IN (DTUB), FB Mathematik, TU Berlin, 1000 Berlin, Federal Republic of Germany 
AN 076535 (076535001) 
MRI 91; 91h 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1988  1992 10 of 11
MR 92k:57043 
AU Kuhnel,Wolfgang, (DDUIS) 
TI Triangulations of manifolds with few vertices. 
TIC Collection: Advances in differential geometry and topology, 59114 
PY 1990 
PUBL World Sci. Publishing, Teaneck, NJ, 1990. 
LA English 
PC 57Q15, 57Q, 57 
SC 05B99, 05B, 05; 52B70, 52B, 52 
RL SHORT; (8 lines) 
AB This is a detailed survey of the literature about concrete and
explicit triangulations of manifolds (compact, without boundary), in
particular, those with a small or minimal number of vertices. It involves
geometry, combinatorics and topology, with some emphasis on the
topological aspects. Some open problems are stated.
The survey is divided into the following sections: introduction and
definitions; $2$manifolds; $3$manifolds; $4$manifolds;
higherdimensional examples; lower bounds; combinatorial Morse theory.
{For the entire collection see MR 91k:53002}.

RE Altshuler,A.; (ILBGUN) 
RT Signedreview 
DE *(57Q15) Manifoldsandcellcomplexes (For complex manifolds, see 32C10); PLtopology; Triangulatingmanifolds 
DE (05B99) Combinatorics (For finite fields, see 11Txx); Designsandconfigurations (For applications of design theory, see 94C30); Noneoftheabove,butinthissection; (52B70) Convexanddiscretegeometry; Polytopesandpolyhedra; Polyhedralmanifolds 
DT ProceedingsPaper 
IN (DDUIS), FB Mathematik, GHS Duisburg, W4100 Duisburg, Federal Republic of Germany 
XN 91k:53002 
XP 095528 
AN 095532 (095532001) 
MRI 92; 92k 
SF MR; (Mathematical Reviews) AMS 
MathSci Disc 1988  1992 11 of 11
MR 92k:52029 
AU Barnette,D.W., (1CAD) 
TI The minimal projective plane polyhedral maps. 
TIC Collection: Applied geometry and discrete mathematics, 6370 
SE DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 4, 
PY 1991 
PUBL Amer. Math. Soc., Providence, RI, 1991. 
LA English 
PC 52B70, 52B, 52 
SC 05C10, 05C, 05 
RL MEDIUM; (12 lines) 
AB Summary: ``A well known theorem of Steinitz states that the graphs of
convex 3dimensional polytopes can be generated from the graph of the
tetrahedron by a process called facet splitting.
``One generalization of convex 3polytopes is polyhedral maps in
2manifolds. Elsewhere [92d:52038J. Combin. Theory Ser. B
51 (1991), no. 2, 277291; MR 92d:52038], we showed how to
generate the polyhedral maps in the projective plane from seven
minimal maps using face splitting and its dual, vertex splitting. In
this paper we show how to generate the polyhedral maps in the
projective plane from 16 minimal maps using just vertex splitting. By
duality, this is equivalent to giving a generating procedure using
just face splitting.''
{For the entire collection see MR 92b:00050}.

RN Summary 
RT Abstract 
DE *(52B70) Convexanddiscretegeometry; Polytopesandpolyhedra; Polyhedralmanifolds 
DE (05C10) Combinatorics (For finite fields, see 11Txx); Graphtheory (For applications of graphs, see 68Q90, 68R10, 90C35, 94C15); Topologicalgraphtheory,imbedding (See also 57M15, 57M25) 
DT ProceedingsPaper 
IN (1CAD), Department of Mathematics, University of California, Davis, California, 95616 
XN 92b:00050 
XP 116332 
AN 116338 (116338001) 
MRI 92; 92k 
SF MR; (Mathematical Reviews) AMS 
==============================================================================
Date: Thu, 23 Mar 1995 06:37:55 0800 (PST)
From: [Permission pending]
To: Dave Rusin
Subject: Re: minimal polyhedra, etc.
Dave,
I had a thought about embedding the polyhedra.
If you have that embedding of an nvertex polyhedron into R^n, where each
vertex goes to a separate basis vector, then a projection from R^n to R^3
is a linear transformation.
So there is a kernel subspace of R^n of dimension n3.
In order to have an embedding you don't want the image of any of the faces
to cross. So a vector from one face to another can't be in the kernel of
the map.
So the set of all those vectors must leave room for an n3 dimensional
subspace, or if you projected those vectors onto RP^(n1) they must
leave room for an RP^(n4) subspace of RP^(n1).
I wonder if such a subspace could just be calculated, or searched for. I
wonder if there is something about that collection of vectors for
nonorientable 2manifolds which makes it evident that an embedding
isn't possible.
Thanks for sending the abstracts.
[sig deleted  djr]