Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.

Shifting attention from the plane to the sphere and torus, we extend the study of pseudo-triangulations. Planar representations of each surface are used. A number of theorems and concepts are taken from the plane and applied to the sphere and torus not only for pseudo-triangulations but for triangulations as well. We found the number of edges and faces in a triangulation on n vertices in the plane, on the sphere and on the torus.

An efficient air transport system is an important part of social and economic development of Southern African Development Community (SADC). Efficient intra-SADC air service connections enhance regional integration, access to the global economy, international tourism and contribute towards the vision to establish the African Economic Community by 2034. SADC, in July 1998, embarked on liberalisation of the regional civil aviation sector in order to enhance the efficiency of air transport services. In the United States of America and European Union, the liberalisation of air transport has transformed civil aviation networks. The fragmentation of air service connections on the intra-SADC network in the midst of the liberalisation process is symptomatic of a poor implementation strategy coupled with air transport market imperfections. The purpose of this thesis is to examine, understand and explain the factors that influence the disintegration of the intra-SADC air transport network .The aim is to identify how regional air transport services can be transformed to meet the social and economic demands of the region. This research adopts network theory, as the conceptual framework of the investigation. Assuming a graph approaching maximal connection as the sought after state of affairs for SADC; this study benchmarked the post liberalisation network structure to the regional economic communities of ASEAN and MERCOSUR. The aim of the benchmarking is to identify the extend of the differences in air transport network in those two regions, resulting from the policies adopted and to establish how the SADC policies may be improved and implemented more efficiently. The findings of the study are that, in comparison to the two developing regions, SADC’s liberalisation measures have failed. The study developed and evaluated an econometric model which analysed demand patterns on the intra-SADC passenger air transport network. Although low levels of passenger demand seem to characterise the majority of SADC city-pairs, the study identified nodes with sufficient demand to justify direct connections which would in turn reduce network fragmentation. This research also establishes that the absence of a realistic detailed roadmap, an ill-defined programme of action and inadequate resources contributed to the failure of SADC’s liberalisation strategy. In its final sections, this study proposes an ideal demand-driven network configuration and offers specific recommendations to SADC member states for that network to be functional. The proposed network improves network connectivity from the current poor levels, where a connectivity measure of 15% suggests underdevelopment, to levels over 40%. The study however, acknowledges that air transport liberalisation does not necessarily guarantee equitable distribution of network efficiency in developing regions. There are communities that cannot sustain commercially viable air service connections without economic subvention, probably in the form of the Public Service Obligation (PSO) programme adopted in the EU.

An efficient air transport system is an important part of social and economic development of Southern African Development Community (SADC). Efficient intra-SADC air service connections enhance regional integration, access to the global economy, international tourism and contribute towards the vision to establish the African Economic Community by 2034. SADC, in July 1998, embarked on liberalisation of the regional civil aviation sector in order to enhance the efficiency of air transport services. In the United States of America and European Union, the liberalisation of air transport has transformed civil aviation networks. The fragmentation of air service connections on the intra-SADC network in the midst of the liberalisation process is symptomatic of a poor implementation strategy coupled with air transport market imperfections. The purpose of this thesis is to examine, understand and explain the factors that influence the disintegration of the intra-SADC air transport network .The aim is to identify how regional air transport services can be transformed to meet the social and economic demands of the region. This research adopts network theory, as the conceptual framework of the investigation. Assuming a graph approaching maximal connection as the sought after state of affairs for SADC; this study benchmarked the post liberalisation network structure to the regional economic communities of ASEAN and MERCOSUR. The aim of the benchmarking is to identify the extend of the differences in air transport network in those two regions, resulting from the policies adopted and to establish how the SADC policies may be improved and implemented more efficiently. The findings of the study are that, in comparison to the two developing regions, SADC’s liberalisation measures have failed. The study developed and evaluated an econometric model which analysed demand patterns on the intra-SADC passenger air transport network. Although low levels of passenger demand seem to characterise the majority of SADC city-pairs, the study identified nodes with sufficient demand to justify direct connections which would in turn reduce network fragmentation. This research also establishes that the absence of a realistic detailed roadmap, an ill-defined programme of action and inadequate resources contributed to the failure of SADC’s liberalisation strategy. In its final sections, this study proposes an ideal demand-driven network configuration and offers specific recommendations to SADC member states for that network to be functional. The proposed network improves network connectivity from the current poor levels, where a connectivity measure of 15% suggests underdevelopment, to levels over 40%. The study however, acknowledges that air transport liberalisation does not necessarily guarantee equitable distribution of network efficiency in developing regions. There are communities that cannot sustain commercially viable air service connections without economic subvention, probably in the form of the Public Service Obligation (PSO) programme adopted in the EU.

Not available / text

Thesis (Honors)--College of William and Mary, 2008. / Includes bibliographical references (leaf 47). Also available via the World Wide Web.

Thesis (Ph. D.)--Auburn University, 2008. / Abstract. Vita. Includes bibliographical references (p. 50-51).

Thesis (Ph. D.)--University of Texas at Austin, 2003. / Vita. Includes bibliographical references. Available also from UMI Company.

Thesis (M.S.)--University of West Florida, 2007. / Title from title page of source document. Document formatted into pages; contains 68 pages. Includes bibliographical references.

We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality, (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in O( n) time, where n is the number of vertices. In the second, an insertion query runs in O(log² n) time, an insertion in O(n) time, a deletion query in O(n) time, and a deletion in O(n log n) time. We also introduce the clique-separator graph representation of a chordal graph, which provides significantly more information about the graph's structure than the well-known clique tree representation. We present fundamental properties of the clique-separator graph and additional properties when the input graph is interval. We then introduce the train tree representation of interval graphs and use it to decide whether there is a certain linear ordering of the graph's maximal cliques. This yields a fully dynamic algorithm to recognize interval graphs in O(n log n) time per edge insertion or deletion. The clique-separator graph may lead to dynamic algorithms for every proper subclass of chordal graphs, and the train tree may lead to fast dynamic algorithms for problems on interval graphs. / Graduate