APPROVAL SHEET 
T~tle of Thesis: A Combinatorial Representation for 
Oriented Polyhedral Surfaces 
Name of Candidate: John Robert Edmonds, Jr. 
Master of Arts, 1960 
Thesis and Abstract Approved, ~?~  
Dr.riiceReina.r 
Assistant Professor 
Department of Mathematics 
Date approved: ~ /~ J'fl 0 
ugRi\ll'l 
mnvrnslTY OF MAR'fl.AHU 
r''~: rcF Pt,r:K. MD. 
,\ 
A COMBINATORIAL REPRESENTATION FOR 
ORIENTED POLYHEDRAL SURFACES 
by 
John Robert ,E .. dmonds, Jr. 
Thesis submitted to the Faculty of the Graduate School 
of the University of Maryland in partial fulfillment 
of the requirements for the degree of 
Master of Arts 
1960 
. f tMRYtAI\U 
? '(. Mfl 
~? I 
SECTION I 
Any connected linear graph can be imbedded without 
self~intersections in a closed, two-sided surface so that the 
components of the complement of the graph in the surface are 
topological discs (1). Our purpose is to strengthen this 
well known theorem (in Theorem 2) and then apply the stronger 
result to formulating (in Theorems 3 and 4) a simple combi-
natorial manner for representing an oriented polyhedral sur-
face, i 0 eo, a surface with an imbedded graph as described 
above. 
Each disc and its closure may be considered a (topo-
logical) polygon whose edges and vertices are those shared 
by the graph. Every edge of the graph belongs to exactly 
two polygons or perhaps to the same polygon twioeo On the 
other hand, any collection of such polygons with no inter-
sections except that each edge belongs exactly twice to mem-
ber polygons forms one or more closed (not necessarily 
orientable) polyhedral surfaces. When in no proper subcol-
lection of the polygons do the edges have this property of 
coinciding in pairs, the collection forms a single polyhe-
dron, in which case its edges and vertices are a connected 
graph. 
1 
2 :; tJ :. ..' . ~j : ~-
2 
It is. intuitively evideilt thait: Theor61Tl 1. If a poly-
hedron is two-sided -- that is orientable then with res-
pect to one of these sides, the edge-ends to each vertex have 
a uniquely determined cyclic ordering clockwise around the 
vertex. 
We will not formally prove this theorem. For a more 
precise and thorough treatment of polyhedral surfaces, includ-
ing essentially a proof of this theorem, the reader is refer-
red to (2); though the polydra there have only triangular 
faces, the point~set considerations apply to the polyhedra of 
this papero For our purposes, however, the following remarks 
about the ordering are more usefulo 
Every vertex of a polygon is an endpoint of exactly 
two of its edges or is an endpoint of the same edge tw,ice~ 
The vertices of a polyhedron arise by the coincidences of the 
polygonal vertices induced by the coincidences of the poly-
gonal edges in pairs. In particular, a certain polygonal 
vertex will coincide twice with other polygonal vertices by 
virtue of the coincidences of the two polygonal edges in 
which it occurs (or else will coincide only with itself by 
virtue of a coincidence with each other of the polygonal edges 
containing it). These two other vertices will each coincide 
in the same manner with another polygonal vertex, and so on. 
We thus have, except for orientation, a cyclic ordering of 
polygonal vertices, each coinciding with the two vertices ad-
jacent to it in the ordering. Because of the transitivity 
of coincidence, these polygonal vertices will thereby all co-
incide with each other to form a single vertex of the polyhedron. 
No other polygonal vertex will coincide in the poly-
hedron with these because the coincidences of the polygonal 
edges in which they occur are all accounted for and there-
fore there are no further edge coincidences to give rise to 
further vertex coincidences with these vertices. This dis-
cussion indicates why a polyhedron, formed by the coincidence 
of edges of polygons in pairs, is locally euclidean, even at 
its vertices, and is hence a surface. 
Now, where v 1 and v 2 are polygonal vertices which are 
adjacent in the ordered set of vertices which coincide to 
form vertex v of a polyhedron, pair v 1 v 2 corresponds to the 
edge-end to v formed by the coincidence of the polygonal 
edges which gives rise to the coincidence of v 1 and v ? The 2
ordered set of polygonal vertices determines a similar order-
ing of its adjacent pairs of vertices and hence an ordering 
of the edge-ends to v. On the basis of our remarks so far 
(which apply as well to non-orientable polyhedra), this or-
dering of the edge-ends to a polyhedral vertex is cyclic but 
Without orientation -- that is, no distinction is made between 
the ordering and its reverse. 
The edges of a polygon are cyclically ordered without 
orientation by saying that adjacent edges in the ordering 
are those having a common (polygonal vertex) end point. To 
orient a polygon is to orient this ordering, i.e., to speci-
fy one 0 ~ the two possible cyclic orderings whose adjacent 
edges are the same as above. Pairs of adjacent edges are 
thus directed so that for each edge there exists one right-
adjaoent edge and one left-adjacent edge. (bis right-adja-
4 
Cent to a if and only if a is left-adjacent to bo) 
By speoifyirig an ?upper side" of the polygon we speci-
fy a clockwise orientation of the polygon, and conversely; 
that is, we can orient a surface element (or a surface if it 
has two sides) by speaifying an "upper side". To formalize 
. . , 
this concept of "the sides" of a surface element one must, 
of course, employ neighborhoods of points of the surface 
element imbedded in some 3 dimensional space. Nevertheless, 
the device of 11 sides0 i.s intuitively convenient without def-
inition. 
We now have for any polyhedron, the sets of the edges 
of its polygons and the sets of the edges to its vertices 
8 11 cyclically ordered without orientationo By the manner 
of construction of these ordered sets, it is clear that two 
edges are adjacent in some vertex set if and only if they 
are adjacent in some polygon set. 
An oriented polyhedron is one whose polygons are ori-
ented so that the directed adjacency of pairs of edges in the 
Polygon sets induces a directed adjacency of the correspond-
ing pairs in the vertex sets which gives rise to a consistent 
orientation of each of the vertex set orderings. That is, 
an oriented polyhedron is one for which the orderings of all 
the polygon sets and vertex sets are oriented so that edge a 
is right-adjacent to edge bin a polygon set if and only if 
tor the corresponding adjacent pair in a vertex set bis 
right-adjacent to ao This description may be taken as a def-
inition for "oriented polyhedron" or else can be proven from 
5 
some other definition. It should be geometrically evident 
that the description is equivalent to forming an oriented 
polyhedron by joining edges of o.riented polygons so that the 
upper sides of the polygons are locally on the same side of 
their union. 
SECTION II 
It has apparently not been observed in the literature 
that , indeed 9 conversely to Theorem I: 
Theorem 2. Given a connected linear graph with an ar-
b1? t rari? ly speoified cyclic ordering of the edges to each ver-
tex~ there exists a topologically unique, two-sided polyhedron 
Whose edges and vertices are the given graph and whose clock-
w? 
ise edge orderings at each vertex (with respect to one of 
the sides) are as specified. 
Proof. We may see that Theorem 2 is true by using the 
00ncept of the dual of a polyhedron: by selecting in each face 
of a polyhedron a point and by replacing each edge, which be-
longs to two faces or to the same face twice, by a new edge 
intersecting it and joining the corresponding selected points 
of the faces, we obtain a new polyhedral division of the sur-
face where faces have been replaced by vertices and vertices 
have been replaced by faoes. Each of these two polyhedra is 
the topologically unique "dual" of the other. 
Suppose we are given a graph and a specified cyclic 
Ordering of the edges to eaoh vertexo Corresponding to each 
~ertex, let there be a polygon such that the edges of the 
Polygon correspond one-to-one to the edges of the graph go-
ing to that vertex and such that the polygon edges are ar-
ranged with respect to a certain "upper side" of the polygon 
clockwise around the boundary in the order specified for the 
corresponding edges to the vertex. Since an edge of the graph 
6 
7 
has two ends? exactly two polygonal edges correspon~ to each 
edge of the grapho Now we join the polygons together along 
pairs of edges corresponding to the same graph edge so that 
upper sides of the polygons all become part of the same side 
of the surface formed. (At any step of the process of join-
ing, any remaining pair of corresponding edges may be joined 
in wrong way and one right way.) In the process, the 
polygonal vertices are made to coincide with each other as 
described in the remarks following Theorem 1. We thus ob-
tain a polyhedron the l~skeleton of whose dual is the given 
graph imbedded in the desired manner. This dual is therefore 
the topologically unique polyhedron whose existence is as-
serted in the theorem-~ unique because any other such poly-
hedron is constructable in the same unambiguous manner. 
Though this definitely informal proof is instructive, it is 
actually not necessary to employ the dual in order to prove 
Theorem 2. The theorem follows immediately from the remarks 
following Theorem 1 by noticing that the steps for obtaining, 
for a polyhedron, the orderings of the vertex sets {of edges) 
are reversible. By reversing the procedure~ one finds for a 
graph with cyclic ordered vertex sets a unique set of cir-
cuits of edges such that a surface is formed when each cir-
cuit is made to bound a 2 cell. We shall essentially describe 
this reverse procedure in Section 4 where we give a combina-
torial construction for the dual of a polyhedron. 
p ----------------
SECTION III 
There is a simple combinatorial representation for 
Polyhedral surI'.acesp based on the remarks following Theo-
rem 1 or, alternatively, based on Theorem 2. Topologically, 
an oriented polygon is determined by a cyclically ordered 
set of elements which correspond one-to-one to the edges of 
the polygon so that element bis right-adjacent to element 
a. ? 
in the set when corresponding edges a and b meet at a 
00 mmon vertex so that edge b follows edge a clockwise 
around the boundary with respect to the orientatione The 
Polygon may be one-edged in which case, of course, a= b. 
An oriented polyhedral surface Pis then represent-
able by a class of such cyclically ordered sets where each 
element occurs exactly twice in sets of the olass 9 perhaps 
in the same set twiceo (T): Two occurrences e 1 and e of 2 
the same element e will correspond to polygon edges e 1 and 
8 2 Which coincide in the polyhedron so that the vertex (end-
P0int) of edge 81 shared with its left-adjacent edge coin-
Cides with the vertex shared by edge e2 with its right 
adjacent edge. Adjacency here is, of course, with respect 
to the set representations. 
Conversely, every such class of ordered sets, in which, 
(A), every element of these sets occurs exactly twice, deter-
mines in the manner (T) a set of oriented polyhedra. If, (B), 
for no proper subclass, does every element occurring once in 
a set of the subclass occur twice in sets of the subclass, 
8 
9 
then no proper subclass determines a polyhedron a.nd hence 
the o la. s s represen t s a s?i ng1e  po 1 yhe  d ron. 
On the other hand, a class of unordered sets such that ' 
every element of a set in the class occurs exactly twice 
(A)? 
in sets of the class perhaps to the same set twice, is a 
9 
convenient representation of a grapho The sets correspond 
to the vertices of the graph? Ea.ch element corresponds to 
and edge whose endpoints are the vertices corresponding to the 
If (B), no proper sub-
set., i? n which the element ooours
9 
? 
0 
class of the class has property (A), then the corresponding 
graph is connected. 
A class with properties (A) and (B) such that, (C), 
the sets of the class a.re cyclically ordered, represents on 
e one hand a polyhedron Pas described earlier. On the 
th
other hand it specifies a cyclic ordering of the edge ends 
9 
to each vertex of the represented graph. The polyhedron P, 
Whose 1-skeleton is this graph so arranged clockwise a.round 
~e vertioe, is the dual of -P. 
We prefer to regard the class of ordered sets a.s rep-
resenting P, rather than P: 
Theorem 3. A class of sets with properties (A), (B), 
and (C) is a representation for a topologically unique ori-
ented polyhedral surface (polyhedron) where the sets of the 
class correspond to its vertices and the distinct elements 
correspond to its edge?? Every oriented polyhedral surrace 
has such a representation ? 
F 
C / '\ -
I ~ 
I \ 
I 6 '\ 
I '\ 
" 
SECTION IV 
In the dual, P, of polyhedron P there is an edge, a, 
corresponding to each edge, a, of Po Edg~ a of Pis the one 
Which intersects a and joins the (arbitrarily selected) ver-
tices of plying in the cell~faces of Pon whose boundary 
lies 
If a lies twice in the boundary of the same face 
F of P, i.e., if Flies on both sides of a, then a is a 
curve joining to itself the vertex of P correspond-
ing to F. 
Since pis regarded as having a particular orienta-
tion (given by the representation) and since Pis geomet-
rically constructed on the same surface on which P has some 
geometric existence, we want Pas a surface to have the 
same orientation as P. Therefore, the edges to a vertex V 
of P will be arranged clockwise around V with the same cyclic 
Order as that with which the corresponding edges are ar-
ranged clockwise around the. face F of P to which V corre-
sponds. 
According to Section I? edges a and b of face F of p 
have endpoints at a common vertex v1 of F so that a and b 
are adjacent components of the boundary of F and b follows a 
clockwise around the boundary if and only 1~ ~ 1 
~ a ~o lows b 
clockwise around V, i.e., if and only if a is right-adjacent 
to bin the ordered set V or the representation of P. 
See 
figure 1. 
In this case, bis then right-adjacent to a in the 
set V 0 f the representation of P. 
10 
11 
Now, similarly, the edge c which is right adjacent 
to bin set V corresponds to the c following b clockwise 
around the boundary of Fe Edge b follows this c in the 
clockwise arrangement of edges around the other endpoint 
v2 of b, the vertex which separates band c as components 
of the boundary of F. That is, c is the left-adjacent 
edge to the other set occurrence (in set v2 ) of bin the 
representation of P. Therefore, making no verbal dis-
tinction between a polyhedron P and its representation, 
the dual of P may be combinatorially computed by using: 
Theorem 4. For a vertex-set occurrence of any edge 
bin the dual p of P the edges left-adjacent and right-
adjacent to this occurrence are respectively a and c, 
where edge a is right adjacent to one occurrence of b in 
p and C is left adjacent to the other occurrence of b in 
P. The other occurrence of 'S follows the same rule in 
the only other possible instance of the rule. 
-
We can compute p by letting occurrences of X in p 
correspond respectively to particular occurrences of X in 
P. Then to the right of an occurrence of a in P, we place 
an occurrence of b corresponding to the b to the left of 
the a occurrence other than the one to which this a occur-
rence corresponds. 
Example: 
p [(ndetg) (b) (6 df) {ban) (gel] 
'F Ugb'bof'ee;fd) (dcage )] 
ggmbingtgpiglly the ~AOe? o~ p. 
are ~ive vePtige? 1 twg ~fig@? 
12 
and seven edges, Euler's formula, V-E+F, tells us that the 
characteristic is zero and hence that the polyhedron is a 
torus. A simpler torus is ~ababD with one vertex and 
one face. 
~aaD is a sphere on which there is one edge whose 
endpoints are at the same vertex. This polyhedron has two 
faces, both one-edged. Its dual is CTa)(aD, a sphere on 
which there is a single edge with separate endpoints. 
SECTION V 
The class representation of polyhedra provides con-
venient machinery for their classification according to 
their mutual homeomorphisms as surfaces. There is a set of 
simple operations on the representations for getting from 
one polyhedral representation to another where the poly-
hedra represented have their geometric existence on homeo-
morphic surfaces. Using these operations, the polyhedra 
can be reduced to canonical forms which correspond to the 
orientable surfaces of various genuses. 
Another useful application of the theorems in this 
?'.; 
?I 
paper is to the study of the Cayley diagram of a finite n,,  ,,'  
l 
groupe For this topic see (3). 
Since a self-intersecting imbedding of a graph in I 
a plane also arranges the edges to each vertex in a def- I 
inite clockwise order around the vertex, any imbedding of ! 
.I 
any connected graph in a plane determines a topologically j 
! 
:1 
unique oriented polyhedral surface. For example figure 2 
?J 
I 
corresponds to the torus, [(a ba b )] ? l 
13 
REFERENCES 
l.. Lindsa 
a Yo J 0 H. An elementary treatment of fhe imbedding of 
'V fraph in a surf'ace~ The American Mathematical Monthly., 
0 
0 6 6., 1959, pp. 117~118. 
2. Aletsatid . 
p ro'V? P. S. Combinatorial Topology., vol. 1 (especially 
3. Po 73-76), Graylook Press, Rochester, N.Y., 1956. 
Co.:iceter 
t ? H.S 0 Mo and WoO.J. Moser, Generators and Relations 
~isorete Groups, Ergebnisse der Mathematik, Springer, 
Berlin., 1957., Chapter S.