San Diego meeting logo

MAA Short Course

A Sampler of Applications of Graph Theory

January 4--5, 2002



How to Register: There is a separate registration fee for this Short Course. To register in advance, please use the Advance Registration/Housing Form. Advance registration fees are $125/member; $175/nonmember; and $50/student, unemployed, emeritus. On-site registration fees are $140/member; $190/nonmember; and $60/student, unemployed, emeritus.

A Sampler of Applications of Graph Theory, Friday and Saturday, January 4 and 5, organized by Fred S. Roberts, Rutgers University.

The Short Course will survey a variety of applications of graph theory. Graph theory is an old subject that has found a vast number of exciting applications in recent years. The speakers will introduce the graph-theoretical topics needed, describe both historical and current applications, and discuss current research topics in graph theory related to the applications. Many of the topics to be covered will be amenable to discussion in the classroom and will make good research topics for both researchers and students. No prior knowledge of graph theory will be required. Speakers and their talks include Nathaniel Dean, Rice University, Applications to network visualization; Sridhar Rajagopalan, IBM Almaden, Graph structure on the World Wide Web; Ramamoorthy Ravi, Carnegie Mellon University, Applications of graph theory to molecular biology; K. Brooks Reid, California State University, San Marcos, Graphs in the theory of location of facilities; Fred S. Roberts, A sampler of applications of graph theory and Graph theory and social networks; and Peter M. Winkler, Bell Labs, Applications to statistical physics. updated Their abstracts are listed below:

Applications to Network Visualization- Nathaniel Dean, Rice University

Graphs are commonly used to model systems of discrete objects and to visualize these systems by exploiting technology and human visual psychology. We present several approaches to drawing graphs, some computer tools for visualizing the graphs in the plane and higher dimensions, and we explain some of the difficulties associated with constructing good drawings.

Graph Structure on the World Wide Web- Sridhar Rajagopalan, IBM Almaden

In this module, we will look at the web as a graph (pages are nodes, weblinks are edges) from three points of view. In the first section, we will detail various experimental studies to estimate macroscopic parameters of the web graph. We will compare our estimates to the parameter values expected in typical (random) graphs. In the second section, we will talk about new random graph models for generating large random web like graphs. Finally, we will talk about algorithms which process the web graph for the purpose of searching and data mining. The module is meant to be an introduction to a new and emerging research area, but is not comprehensive. Therefore, we will conclude with some pointers to follow for information not covered in the talk.

Applications of Graph Theory to Molecular Biology- R. Ravi, Carnegie Mellon University

In this talk, we will survey key concepts from graph theory that have found important applications in algorithms for problems arising in Molecular Biology. Key topics covered will include (1) exploiting the graph structure in dynamic programming applications for optimal alignment of DNA and RNA sequences, (2) graph-theoretic ideas arising in the various formulations of multiple sequence alignment problems, (3) the use of Interval graphs in applications to problems in the Physical Mapping of genomes, (4) the importance of the notion of additive and ultrametrics in the realm of phylogenetic reconstruction, and time permitting (5) the use of sophisticated graph-theoretic structures in deriving polynomial-time algorithms for deciphering the minimum genome rearrangement distance between two organisms. We will assume no prior knowledge of Molecular Biology.

Graphs in the Theory of Location of Facilities- K. Brooks Reid, California State University, San Marcos

The theory of location of facilities in networks combines tools from graph theory, basic analysis, optimization, and complexity theory. The central issue is the study of the optimal location(s) of a facility such as emergency installation, a supply depot, a switching center, a pumping station, an obnoxious dump, a communications center, or the like in a network such as a street or road network, an electrical network, a network of channels or pipes, a communications network or the like. Optimality depends on criteria usually involving some idea of distance and varies according to the application. Weighted graphs provide a context for studying these types of problems, where vertices and edges are assigned weights representing certain parameters according to the application. Usually, special sets of vertices are sought that are either "central" or "peripheral." Results range from the descriptions of optimal locations to the computational difficulty in actually determining these optimal locations. Considerable study has been focused on weighted trees. These issues have motivated graph theorists to probe many different notions of centrality and notions of the "outer fringes" in ordinary (unweighted) graphs, particularly trees. In such models, users and facility locations are thought to be restricted to vertices. However, the graph theoretical origins of centrality precede the advent of modern location theory as C. Jordan introduced the concepts of the center of a tree and the branch weight centroid of a tree in 1868.

In the main part of this talk we will suggest answers to the question: "Where is the center of a tree?" We will start with a novel treatment of the two classical central sets, the center and the branch weight centroid. Then we will treat in turn other notions and their relationships including the median, the security center, the telephone center, the accretion center, the set of weight balanced vertices, and the latency center. In contrast to these notions, we will consider the distance balanced vertices. Several other central sets will be briefly mentioned, some of which make sense in the class of all (connected) graphs. Finally, we will mention some one-parameter and two-parameter families of central sets of vertices in trees. In some instances we will discuss these concepts for general networks where, in some instances, users and facility locations can be placed not only at vertices but also at points along edges.

One goal of this talk is to convey the idea that this subject is a very accessible branch of applicable combinatorics, rich in problems, and offering an occasional surprise.

Graph Theory and Social Networks- Fred S. Roberts, Rutgers University

Graph theory has many applications in the study of social networks, networks whose vertices are people and whose edges represent some relationships between individuals. Applications include graph coloring models to help define the "social roles" of individuals; signed and marked graph models to help define "balance" and "social justice" in small group situations; models of the spread of opinions from person to person; and models describing the structure of acquaintances and the influence of some people on others. Social networks are also increasingly important in the study of infectious diseases, like AIDS, that are spread through social contact. We shall describe such applications of graph theory and the fascinating graph theoretical concepts and problems that arise in such applications.


Applications to Statistical Physics- Peter Winkler, Bell Labs

Statistical physicists would like to understand how local rules for a many-part system can cause qualitative changes, called "phase transitions'', in the global behavior of the system. How can graph theory help?

Sometimes the local rules are what we call hard contraints, which might, for example, forbid two particles to occupy neighboring sites in a grid. Such rules can be formulated graph-theoretically, and indeed the resulting systems often correspond to familiar constructions like colorings and independent sets.

We will take a little tour through the graph theory of hard constraints, visiting fertile graphs and dismantlable graphs on the way to some combinatorial understanding of the notion of phase transition.


updated Schedule
  • First day:

    9:00 Introduction and overview - Fred Roberts

    11:00 am Speaker #1 Winkler

    2:15 pm Speaker #2 Ravi

    4:00 pm Speaker #3 Reid

  • Second day:

    9:00 am Speaker #4 Rajagopalan

    11:00 am Speaker #5 Dean

    2:00 pm Speaker #6 Roberts

    4:00 pm Discussion

  MAA logo

10/31/01 12:01 POP