TRIANGULATION AND FOLDING METHODS FOR GRAPHS

Abstract

Triangulation, folding, extending methods of graphs play an important role in geometry, topology, algebraic topology, computa­ tional geometry, finite elements, medicine, and other subjects.

The aim of preparing this thesis is to give algorithms of triangu­ lation, folding, extending methods for a large polyhedral graphs. These algorithms enable us to compute their different incidence ma­ trices using computer pr.ograms which we construct.

The thesis consists of seven chapters and an Appendix.

In chapter zero; we give some needed definitions, fundamental concepts which are important for our study.

In chapter one; we explain triangulation method in the surface in. article one. The second article explains the method of triangulation of the graph in the plane by using two methods (without using computer program, and with using computer program which we construct) for calculating the different incidence matrices for any large planar graph. Then we compare the two results. The third article explains the method of triangulation of the graph in the space by using the same two methods for calculating the different incidence matrices for any large polyhedral graphs, finally we compare the two results.

In chapter two; we generalize the work ofYOSHIMI EGAWA and

ROLADND E. ROMAS. We put a theorem says that "Let G be a connected graph. Then R n (G) = G for some positive integer n if and only if G is isomorphic to one ofthe fifteen graphs submitted in the thesis", we depend on our work that G must contain Ks (a complete subgraph of order 5).

In Chapter three; this chapter is based on work done by E. EI­ Kholy[l3] and M. El-Ghoul [15].\Je put an algorithm for the method of folding, also we construct a program to calculate the different incidence matrices for any graph after folding, finally we give some examples and its computer results for some graphs.