We consider several random spatial graphs of the nearest-neighbour type, including the k- nearest neighbours graph, the on-line nearest-neighbour graph, and the minimal directed spanning tree. We study the large sample asymptotic behaviour of the total length of these graphs, with power-weighted edges. We give laws of large numbers and weak convergence results. We evaluate limiting constants explicitly. In Bhatt and Roy's minimal directed spanning tree (MDST) construction on random points in (0,1)(^2)， each point is joined to its nearest neighbour in the south-westerly direction. We show that the limiting total length (with power-weighted egdes) of the edges joined to the origin converges in distribution to a Dickman-type random variable. We also study the length of the longest edge in the MDST. For the total weight of the MDST, we give a weak convergence result. The limiting distribution is given a normal component plus a contribution due to boundary effects, which can be characterized by a fixed point equation. There is a phase transition in the limit law as the weight exponent increases. In the second part of this thesis, we give criteria for ergodicity, transience and null recurrence for the random walk in random environment (RWRE) on z+ = {0,1,2,...}, with reflection at the origin, where the random environment is subject to a vanishing perturbation from the so-called Sinai's regime. Our results complement existing criteria for random walks in random environments and for Markov chains with asymptotically zero drift, and are significantly different to these previously studied cases. Our method is based on a martingale technique 一 the method of Lyapunov functions.

This thesis studies behavioural equivalences on labelled infinite transition graphs and the role that they can play in the context of modal logics and notions from language theory. A natural class of such infinite graphs is that corresponding to the SnS-definable tree languages first studied by Rabin. We show that a modal mu-calculus with label set {0,...,n - 1} can define these tree languages up to an observational equivalence. Another natural class of infinite transition graphs is that of normed BPA processes, which correspond to the graphs of leftmost derivations in context-free grammars without useless productions. A remarkable result is that strong bisimulation is decidable for these graphs. After an outline of the existing proofs due to Baeten et al. and Caucal we present a much simpler proof using a tableau system closely related to the branching algorithms employed in language theory following Korenjak and Hopcroft. We then present a result due to Colin Stirling, giving a weakly sound and complete sequent-based equational theory for bisimulation equivalence for normed BPA processes from the tableau system. Moreover, we show how to extract a fundamental relation (as in the work of Caucal) from a successful tableau. We then introduce silent actions and consider a class of normed BPA processes with the restriction that processes cannot terminate silently, showing that the decidability result for strong bisimilarity can be extended to van Glabbeek's branching bisimulation equivalence for this class of processes. We complete the picture by establishing that all other known behavioural equivalences and a number of preorders are undecidable for normed BPA processes.

Topological embeddings of complete graphs and complete multipartite graphs give rise to combinatorial designs when the faces of the embeddings are triangles. In this case, the blocks of the design correspond to the triangular faces of the embedding. These designs include Steiner, twofold and Mendelsohn triple systems, as well as Latin squares. We look at construction methods, structural properties and other problems concerning these cases. In addition, we look at graph representations by Steiner triple systems and by combinatorial embecldings. This is closely related to finding independent sets in triple systems. We examine which graphs can be represented in Steiner triple systems and combinatorial embeddings of small orders and give several bounds including a bound on the order of Steiner triple systems that are guaranteed to represent all graphs of a given maximum degree. Finally, we provide an enumer- ation of graphs of up to six edges representable by Steiner triple systems.

Network theory is a long standing, rapidly changing and highly motivated field. However, historically its results have been centred on static networks, leaving the area of evolving networks relatively less explored. In this thesis we draw from those existing results and extend them to the case of evolving networks to develop new analytical tools and representations. We do this through the introduction of an importance, or activity, metric for evolving networks, and the creation of a general framework for their models, allowing us to easily define, represent and classify them. We identify observable network properties and seek to predict the long term network structure of these modelled evolving networks. We find that networks can have a wide range of equilibria, even within the same model, from those devoid of network activity, to those exhibiting quasi-periodic network structure. These different equilibria within models are found to arise from chosen parameter values, highlighting the importance of their estimation. The properties upon which these models are based are often neglected for simplicity, however the application of our models to existing data proves their existence, and the significant variety of equilibria between network models shows us how important these properties are.

The first linear-time planarity testing algorithm was developed in 1974 by Hopcroft and Tarjan (H&T) [32] using a method to split a biconnected graph up into edge disjoint paths and then sequentially embed them to test for planarity (a path addition method). Shortly afterwards Booth and Leuker [5] developed an alternative vertex addition linear-time planarity test, based on the earlier work of Lempel, Evan and Cederbaum [47], using a new PQ-Tree data structure. Since then there have been many developments in PQ- Tree vertex addition (and related PC-Tree edge addition) methods including authors such as: Chiba et al. [14]; Shih & Hsu [35, 69]; Boyer and Myrvold [10, 11]; and Haeupler and Tarjan [29]. In comparison, path addition has changed very little from the original algorithm. In 1984, Williamson [84] showed how H&T's algorithm can be extended to find Kuratowski sub-graphs in the event of a non-planar graph; and, in 1993, Mehlhorn, Mutzel and Naher [53] produced an implementation (in C) of H&T's algorithm and extended it to create a planar embedding of a graph. This has remained the state-of-the-art in path addition algorithms for over a decade. Recently", de Fraysseix formulated an algorithm [15, 17], based on Tremaux Trees and a characterisation of planarity by W. Wu [87]; this may prove to be a highly optimised version of H&T's algorithm but is difficult to definitively prove as only an outline of its planarity testing phase is provided. These authors represent the majority of the work on path addition methods of planarity testing and embedding; indicating that it receives little attention compared to vertex or edge addition methods This thesis attempts to reinvigorate the field of path addition and demonstrates: • How Trernaux Trees, which allow undirected connected graphs to be represented as a simple partial order relationship are fundamentally related to H&T-‘^planarity testing algorithm and includes some related invariant properties of these trees; • That the restriction on H&T's planarity testing algorithm to test undirected biconnected graphs can be relaxed to undirected connected graphs; • How to generate all possible embeddings of a biconnected component and how to extend this to generate all possible embeddings of separable graphs; and • Empirical Testing of various graph types and sizes to validate these results.

No description available.

No description available.

This thesis describes our novel methods for data clustering, graph characterizing and image matching. In Chapter 3, our main contribution is the M1NN agglomerative clustering method with a new parallel merging algorithm. A cluster characterizing quantity is derived from the path-based dissimilarity measure. In Chapter 4, our main contribution is the modified log likelihood model for quantitative clustering analysis. The energy of a graph is adopted to define the description length to measure the complexity of a clustering. In Chapter 5, our main contribution is an image matching method based on Delaunay graph characterization and node selection. A normalized Euclidean distance on Delaunay graphs is found useful to estimate pairwise distances.

This thesis contributes a novel approach to navigation tasks in large graphs. Graph visualization is the problem of representing the structure of a mathematical graph G = (V,E), V a set of vertices (or nodes) and E ⊆V ×V a set of edges. My work is concerned with the node-link representation of graphs and I use the term network to distinguish this external representation from the underlying mathematical structure. Networks are an intuitive representation of a set of elements and the relationships between them, and are known to be effective for analysis tasks involving following paths between nodes. I define navigation as the task of identifying and following such a path in display space. Unfortunately the utility of a network diminishes as the density of edges increases and edge-crossings make navigation taxing. A well-explored approach to this problem is to find a perspicuous layout of the nodes. While this improves the readability of individual nodes and edges it may also require a compromise: to be easily understood the overall arrangement of the network should also correspond with the user’s internal mental model of the domain, a property referred to as congruence. Other solutions distort the display space or use multiple-scaled-views to promote comprehension of local details while retaining awareness of the global context, but often lack direct support for navigation of the network topology beyond the local context. This thesis contributes a model of visual graph analysis that brings together recent advances in cartographic representation, diagram comprehension, and graph visualization, leading to a greater understanding of network navigation bottlenecks in terms of the degree of correspondence between the external graph representation, and the user’s ‘mental map’. Motivated by this model I present a new approach to graph visualization that separates concerns of navigation from those of depiction with the aim of improving correspondence between the internal and external representations. I describe the design and realization of an interface for network navigation inspired by the new approach within a pipeline-based architecture, and provide a reflective evaluation of the implementation.

In this thesis we consider the class of simple graphs defined by excluding even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We first prove that every even-hole-free graph has a node whose neighborhood is triangulated. This implies that in an even-hole-free graph, with n nodes and m edges, there are at most n+2m maximal cliques. It also yields a fastest known algorithm for computing a maximum clique in an even-hole-free graph. Afterwards we prove the main result of this thesis. The result is a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is an O(n19) recognition algorithm for even-hole-free graphs. The recognition of even-hole-free graphs was first shown to be polynomial by Conforti, Cornu´ejols, Kapoor and Vuˇskovi´c. They obtained an algorithm of complexity of about O(n40) by first preprocessing the input graph using a certain “cleaning” procedure, and then constructing a decomposition based recognition algorithm. The cleaning procedure was also the key to constructing a polynomial time recognition algorithm for Berge graphs. At that time it was observed by Chudnovsky and Seymour that once the cleaning is performed, one does not need a decomposition based algorithm, one can instead just look for the “bad structure” directly. Using this idea, as opposed to using the decomposition based approach, one gets significantly faster recognition algorithms for Berge graphs and balanced 0,±1 matrices. However, this approach yields an O(n31) recognition algorithm for even-hole-free graphs. So this is the first example of a decomposition based algorithm being significantly faster than the Chudnovsky/Seymour style algorithm.