| A near triangulation on a surface is a map on the surface such that each face of the map, except possibly one face, has valence three. A diagonal flip adjacency graph of near triangulations on surfaces is defined as a graph in such a way that all near triangulations of some type, specified in applications, to be its vertices, two of which are connected by an edge if one near triangulation can be transformed into the other by a diagonal flip. In this thesis, we study some properties of these graphs when the near triangulations are 2-connected or simple.;Using generating function technique, we have found the total number of flippable edges in all rooted 2-connected (simple) planar near triangulations of the same type. From this, we obtain the total number of edges and average vertex degree of the corresponding diagonal flip adjacency graphs. We also find the probability that an edge is flippable in all rooted 2-connected (simple) planar near triangulations.;For any unlabelled, rooted or labelled simple (2-connected) planar near triangulations, we obtain the maximum number and minimum number of flippable edges in these triangulations. They are the same as the maximum and minimum vertex degrees in the corresponding diagonal flip adjacency graphs. We also investigate the diameters of these diagonal flip adjacency graphs. For unlabelled and rooted simple (2-connected) planar near triangulations of type [ n, m], we determine that the diameters of the corresponding diagonal flip adjacency graphs are both O(n + m) and show that the order of this bound cannot be improved. In the labelled case, if the near triangulations are triangulations, i.e. m = 3, then the diameter of the corresponding diagonal flip adjacency graph is O(n log n). If m≠3 , the corresponding diagonal flip adjacency graphs are not connected; however, the subgraphs consisting of all labelled near triangulations of type [n, m] with the same labelling on their non-triangular faces have diameter O(n log n + m).;The exact enumeration of non-planar triangulations is usually very difficult. It is much more complicated than that of planar triangulations. Very few results on exact enumeration of triangulations on non-planar surfaces are known. In this thesis, we successfully enumerate rooted 2-connected triangulations on the Torus, rooted 2-connected triangulations on the Klein Bottle, and rooted 3-connected triangulations on the Projective Plane. In each case, we obtain a nice parametric expression for the generating function of the number of triangulations. In the language of the diagonal flip adjacency graph, we obtain the numbers of vertices in the corresponding diagonal flip adjacency graphs. We also enumerate simple Catalan triangulations on the Torus. |
