Many areas of computer science use graph theory and thus benefit from research in graph theory. Some of the important activities involved in graph theory work are the study of concepts, algorithm development, and theorem proving. These can be facilitated by providing computerized tools for graph drawing, algorithm animation and accessing graph theory information bases. Project G-Net is aimed at developing a set of such tools.Project G-Net has chosen to provide the tools in hypertext form based on the analysis of users' requirements. The project is presently developing a hypertext application and a hypertext system for providing the above set of tools. In the process of this development various issues pertaining to hypertext authoring, hypertext usability and application of graph theory to hypertext are being explored.The focus of this thesis is in proving that hypertext approach is most appropriate for realizing the goals of the G-Net project. The author was involved in the research that went into analysis of requirements, design of hypertext application and system, and the investigation of the complementary relationship between graph theory and hypertext. / Department of Computer Science

Software systems have experienced an impressive growth in the last few decades and have impacted a wide variety of areas. In this respect, two elds bene t greatly. Learning and research. In this work, we present several software systems that we have created to assist in the process of learning and to help researchers by performing complex computations and generating data. We demonstrate three web-based educational video games that we developed to teach science to middle school students. We also describe several software systems that we created for research in graph theory and model checking. Finally, we discuss our results, contributions and future directions. / Educational perspectives -- Graph algorithms and their applications -- E-learning -- Model checking. / Educational perspectives -- Graph algorithms and their applications -- E-learning -- Model checking. / Department of Computer Science

This thesis considers spectral approaches to finding maximum cocliques in graphs. We focus on the relation between the eigenspaces of a graph and the size and location of its maximum cocliques. Our main result concerns the computational problem of finding the size of a maximum coclique in a graph. This problem is known to be NP-Hard for general graphs. Recently, Codenotti et al. showed that computing the size of a maximum coclique is still NP-Hard if we restrict to the class of circulant graphs. We take an alternative approach to this result using quotient graphs and coding theory. We apply our method to show that computing the size of a maximum coclique is NP-Hard for the class of Cayley graphs for the groups $\mathbb{Z}_p^n$ where $p$ is any fixed prime. Cocliques are closely related to equitable partitions of a graph, and to parallel faces of the eigenpolytopes of a graph. We develop this connection and give a relation between the existence of quadratic polynomials that vanish on the vertices of an eigenpolytope of a graph, and the existence of elements in the null space of the Veronese matrix. This gives a us a tool for finding equitable partitions of a graph, and proving the non-existence of equitable partitions. For distance-regular graphs we exploit the algebraic structure of association schemes to derive an explicit formula for the rank of the Veronese matrix. We apply this machinery to show that there are strongly regular graphs whose $\tau$-eigenpolytopes are not prismoids. We also present several partial results on cocliques and graph spectra. We develop a linear programming approach to the problem of finding weightings of the adjacency matrix of a graph that meets the inertia bound with equality, and apply our technique to various families of Cayley graphs. Towards characterizing the maximum cocliques of the folded-cube graphs, we find a class of large facets of the least eigenpolytope of a folded cube, and show how they correspond to the structure of the graph. Finally, we consider equitable partitions with additional structural constraints, namely that both parts are convex subgraphs. We show that Latin square graphs cannot be partitioned into a coclique and a convex subgraph.

In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.

This thesis studies a problem that has been proposed as a novel way to disrupt communication networks: the load maximization problem. The load on a member of a network represents the amount of communication that the member is forced to be involved in. By maximizing the load on an important member of the network, we hope to increase that member's visibility and susceptibility to capture. In this thesis we characterize load as a combinatorial property of graphs and expose possible connections between load and spectral graph theory. We specifically describe the load and how it changes in several canonical classes of graphs and determine the range of values that the load can take on. We also consider a connection between load and liquid paint flow and use this connection to build a heuristic solver for the load maximization problem. We conclude with a detailed discussion of open questions for future work.

This thesis examines the characteristics of railway infrastructure development and associated issues in Manitoba, Canada. The period under consideration dates from when the first tracks were laid in 1878 through to the completion of the Hudson Bay Railway in 1929. Setting the scene is a template for railway development in general, one that allows hypotheses to be drawn that are specific to Manitoba. In order to test those hypotheses it is necessary to first provide a comprehensive overview of the historical evolution of the railway network. Next, aspects of graph theory are reviewed, identifying the methodology most appropriate for a spatial analysis of railway networks. This analysis attempts to draw conclusions about the relationship between the railway companies and the governments, people and geography that they were compelled to deal with. The testing of these forms revealed that while the Manitoba railway network is very complex, it never arrived at the maximum possible complexity.

Although theoretically practical algorithms for torus embedding exist, they have not yet been successfully implemented and their complexity may be prohibitive to their practicality. We describe a simple exponential algorithm for embedding graphs on the torus (a surface shaped like a doughnut) and discuss how it was inspired by the quadratic time planar embedding algorithm of Demoucron, Malgrange and Pertuiset. We show that it is faster in practice than the only fully implemented alternative (also exponential) and explain how both the algorithm itself and the knowledge gained during its development might be used to solve the well-studied problem of finding the complete set of torus obstructions.

No description available.

To date, research of computer science education in the elementary classroom has focused on technology-dependent tools like Alice, Scratch, LOGO and LEGO Mind-storms. While these tools seem to have the potential to support learning in accordance with constructionist theory, they have not lived up to expectations. Results of this research, in particular the impact of programming instruction on student achieve- ment, have been weak or mixed. Possible reasons for this are many, including the corresponding threshold and friction associated with technology-dependent learning. Inspired by a trend of non-technology-dependent instruction of computer science topics, as demonstrated by the success of Computer Science Unplugged by Tim Bell, Mike Fellows and Ian Witten, we have chosen instead to investigate the impact of unplugged computer science instruction on Grade Six students. The shift away from programming instruction may also serve to help dispel the myth that computer science is programming. Computer science is a broad and diverse field which impacts the lives of all people in a multitude of ways. It is not yet clear what the best approach is for integrating computer science education into the elementary classroom. One suggestion is to teach computer science topics such that they support other areas of elementary education. For example, students are encouraged to adopt many different problem solving strategies, as supported by the British Columbia Ministry of Education’s K-7 Mathematics Integrated Resource Package (IRP). These strategies include “draw a picture”. Graph theory has the potential to support problem solving as a means of representing complex connections and relationships in a clear and concise manner. Alternatively, a standalone computer science curriculum may be appropriate, in the spirit of the Computer Science Teacher’s Association (CSTA) “A Model Curriculum for K-12 Computer Science”. Whatever the approach, an important, and fundamental, step in making curricular change is to support the need for change with sound educational research. Only then can we hope to earn the support of the stakeholders, such as school districts and teacher education programs, who can make this change a reality. In this pilot study, we investigate the impact of graph theory lessons in two Grade Six math classes. Because of the small class sizes and somewhat reduced participation rates, the results of this study need to be verified with further, larger scale studies. However, early indications are that Grade Six students are capable of learning graph theory, and applying it when working on mathematical word problems. In some cases, there appears to be an association between students’ ability to apply graph theory as one of many problem solving strategies, and the correctness of their solutions to problems.

Thesis (M.S.)--State University of New York at Binghamton, Department of Computer Science, Thomas J. Watson School of Engineering and Applied Science, 2007. / Includes bibliographical references.