Very large graphs are difficult for a person to browse and edit on a computer screen. This thesis introduces a visual formalism, structured graphs, which supports the scalable browsing and editing of very large graphs. This approach is relevant to a given application when it incorporates a large graph which is composed of named nodes and links, and abstraction hierarchies which can be defined on these nodes and links. A typical browsing operation is the selection of an arbitrary group of nodes and the display of the network of nodes and links for these nodes. Typical editing operations is: adding a new link between two nodes, adding a new node in the hierarchy, and moving sub-graphs to a new position in the node hierarchy. These operations are scalable when the number of user steps involved remains constant regardless of how large the graph is. This thesis shows that with structured graphs, these operations typically take one user step. We demonstrate the utility of structured graph formalism in an application setting. Computer aided software engineering tools, and in particular, structured analysis tools, are the chosen application area for this thesis, as they are graph based, and existing tools, though adequate for medium sized systems, lack scalability. In this thesis examples of an improved design for a structured analysis tool, based on structured graphs, is given. These improvements include scalable browsing and editing operations to support an individual software analyst, and component composition operations to support the construction of large models by a group of software analysts. Finally, we include proofs of key properties and descriptions of two text based implementations.

Graph visualization plays an increasingly important role in software engineering and information systems. Examples include UML, E-R diagrams, database structures, visual programming, web visualization, network protocols, molecular structures, genome diagrams, and social structures. Many classical algorithms for graph visualization have already been developed over the past decades. However, these algorithms face difficulties in practice, such as the overlapping nodes, large graph layout, and dynamic graph layout. In order to solve these problems, this research aims to systematically address both algorithmic and approach issues related to a novel framework that describes the process of graph visualization applications. At the same time, all the proposed algorithms and approaches can be applied to other situations as well. First of all, a framework for graph visualization is described, along with a generic approach to the graphical representation of a relational information source. As the important parts of this framework, two main approaches, Filtering and Clustering, are then particularly investigated to deal with large graph layouts effectively. In order to filter 'noise' or less important nodes in a given graph, two new methods are proposed to compute importance scores of nodes called NodeRank, and then to control the appearances of nodes in a layout by ranking them. Two novel algorithms for clustering graphs, KNN and SKM, are developed to reduce visual complexity. Identifying seed nodes as initial members of clusters, both algorithms make use of either the k-nearest neighbour search or a novel node similarity matrix to seek groups of nodes with most affinities or similarities among them. Such groups of relatively highly connected nodes are then replaced with abstract nodes to form a coarse graph with reduced dimensions. An approach called MMD to the layout of clustered graphs is provided using a multiple-window�multiple-level display. As for the dynamic graph layout, a new approach to removing overlapping nodes called Force-Transfer algorithm is developed to greatly improve the classical Force- Scan algorithm. Demonstrating the performance of the proposed algorithms and approaches, the framework has been implemented in a prototype called PGD. A number of experiments as well as a case study have been carried out.

The purpose of the study was to investigate students' learning of the function concept and the role of the graphing calculator in a College Algebra course. Differences between students with high symbolic manipulation skills. and students with low symbolic manipulation skills were also examined. On the basis of an algebraic skills test administered by the instructor (high/low) and students' academic majors (math & science, business, and liberal arts), 25 students from one College Algebra class were placed into six categories. To gather data on students' understanding of functions, a pretest and posttest were administered. The Function Test consisted of four identification questions given in each of the representations, three questions asking for the definition, an example, and a nonexample of functions, and 15 questions consisting of three problem situations given in the numerical, graphical, and symbolic representations. To gather data on the role of the graphing calculator, daily classroom observations were conducted. To verify students' responses and classroom observations, formal interviews with students and informal interviews with the instructor were conducted. Students' personal definition progressed towards the formal definition of functions. Yet, students had difficulties with the univalence requirement in three areas: (a) order of domain and range, (b) preference for simple algorithms, and (c) the restriction that functions were one-to-one. Compared to students with low symbolic manipulation skills, students with high symbolic manipulation skills were more flexible working between representations of functions. Half of the interviewed students with low symbolic manipulation skills perceived a single function given in numerical, graphical, and symbolic representations as separate entities. The graphing calculator played a role in all phases of the solution process. During the initial phases, students used calculators to develop a symbolic approach. The prime motivation for using graphing calculators during the solution-execution phase was to avoid careless errors. The most common use of graphing calculators was to check answers during the solution-monitoring phase. However, graphing calculators created difficulties for students who accepted graphs at face value. Interpreting the truncated graph shown by the calculator, students determined that exponential functions possessed a bounded domain because they did not explore the graph. / Graduation date: 2001

Thesis (Ph. D.)--University of California, Riverside, 2008. / Includes abstract. Title from first page of PDF file (viewed March 10, 2010). Available via ProQuest Digital Dissertations. Includes bibliographical references (p. 166-170). Also issued in print.

published_or_final_version / Statistics / Doctoral / Doctor of Philosophy

No description available.

No description available.

No description available.

This thesis details the results of investigations into bounds on some distance-based topological indices. The thesis consists of six chapters. In the first chapter we define the standard graph theory concepts, and introduce the distance-based graph invariants called topological indices. We give some background to these mathematical models, and show their applications, which are largely in chemistry and pharmacology. To complete the chapter we present some known results which will be relevant to the work. Chapter 2 focuses on the topological index called the eccentric connectivity index. We obtain an exact lower bound on this index, in terms of order, and show that this bound is sharp. An asymptotically sharp upper bound is also derived. In addition, for trees of given order, when the diameter is also prescribed, tight upper and lower bounds are provided. Our investigation into the eccentric connectivity index continues in Chapter 3. We generalize a result on trees from the previous chapter, proving that the known tight lower bound on the index for a tree in terms of order and diameter, is also valid for a graph of given order and diameter. In Chapter 4, we turn to bounds on the eccentric connectivity index in terms of order and minimum degree. We first consider graphs with constant degree (regular graphs). Došlić, Saheli & Vukičević, and Ilić posed the problem of determining extremal graphs with respect to our index, for regular (and more specifically, cubic) graphs. In addressing this open problem, we find upper and lower bounds for the index. We also provide an extremal graph for the upper bound. Thereafter, the chapter continues with a consideration of minimum degree. For given order and minimum degree, an asymptotically sharp upper bound on the index is derived. In Chapter 5, we turn our focus to the well-studied Wiener index. For trees of given order, we determine a sharp upper bound on this index, in terms of the eccentric connectivity index. With the use of spanning trees, this bound is then generalized to graphs. Yet another distance-based topological index, the degree distance, is considered in Chapter 6. We find an asymptotically sharp upper bound on this index, for a graph of given order. This proof definitively settles a conjecture posed by Tomescu in 1999. / Thesis (Ph.D.)-University of KwaZulu-Natal, Westville, 2012.

Let G = (V, E) be a graph. For any real valued function f : V >R and SCV, let f (s) = z ues f(u). The weight of f is defined as f(V). A signed k-subdominating function (signed kSF) of G is defined as a function f : V > {-I, I} such that f(N[v]) > 1 for at least k vertices of G, where N[v] denotes the closed neighborhood of v. The signed k-subdomination number of a graph G, denoted by yks-11(G), is equal to min{f(V) I f is a signed kSF of G}. If instead of the range {-I, I}, we require the range {-I, 0, I}, then we obtain the concept of a minus k-subdominating function. Its associated parameter, called the minus k-subdomination number of G, is denoted by ytks-101(G). In chapter 2 we survey recent results on signed and minus k-subdomination in graphs. In Chapter 3, we compute the signed and minus k-subdomination numbers for certain complete multipartite graphs and their complements, generalizing results due to Holm [30]. In Chapter 4, we give a lower bound on the total signed k-subdomination number in terms of the minimum degree, maximum degree and the order of the graph. A lower bound in terms of the degree sequence is also given. We then compute the total signed k-subdomination number of a cycle, and present a characterization of graphs G with equal total signed k-subdomination and total signed l-subdomination numbers. Finally, we establish a sharp upper bound on the total signed k-subdomination number of a tree in terms of its order n and k where 1 < k < n, and characterize trees attaining these bounds for certain values of k. For this purpose, we first establish the total signed k-subdomination number of simple structures, including paths and spiders. In Chapter 5, we show that the decision problem corresponding to the computation of the total minus domination number of a graph is NP-complete, even when restricted to bipartite graphs or chordal graphs. For a fixed k, we show that the decision problem corresponding to determining whether a graph has a total minus domination function of weight at most k may be NP-complete, even when restricted to bipartite or chordal graphs. Also in Chapter 5, linear time algorithms for computing Ytns-11(T) and Ytns-101(T) for an arbitrary tree T are presented, where n = n(T). In Chapter 6, we present cubic time algorithms to compute Ytks-11(T) and Ytks-101l(T) for a tree T. We show that the decision problem corresponding to the computation of Ytks-11(G) is NP-complete, and that the decision problem corresponding to the computation of Ytks-101 (T) is NP-complete, even for bipartite graphs. In addition, we present cubic time algorithms to computeYks-11(T) and Yks-101(T) for a tree T, solving problems appearing in [25]. / Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 2003.