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,
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.
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
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
9:00 am Speaker #4 Rajagopalan
11:00 am Speaker #5 Dean
2:00 pm Speaker #6 Roberts
4:00 pm Discussion