Week 1 Topic: Intersection Graphs, Tolerance Graphs
Michael AckermanBallarmine UniversityIntersection Graphs of SemigroupsWe investigate the application of intersection graphs to subalgebras of an
algebara. Specifically, we define the intersection graph of a semigroup S to
be the graph G(S) whose vertex set consists of all proper subsemigroups of
S. The vertices X and Y are adjacent in G(S) if and only if X and Y have a
nonempty intersection. The structure of G(S) is examined. We also discuss
the characterization of those semigroups whose intersection graph is a
certain class of graphs. Kenneth BogartDartmouth CollegeClassification of Trapezoid GraphsA graph G=(V,E) is called a trapezoid graph if there are two parallel lines
(called baselines) so that for each vertex x in V, there is a trapezoid T(x)
with bases on the two baselines with the property that x is adjacent to y
if and only if T(x) and T(y) intersect. A trapezoid graph is called a
parallelogram or triangle graph if we can assign trapezoids that are parallelograms or
triangles, respectively (so that x and y are adjacent if and only if T(x) and T(y)
intersect). A trapezoid, parallelogram, or triangle graph is called proper if
we can assign trapezoids, parallelograms or triangles, respectively, so
that no one is a subset of any other. A trapezoid, parallelogram or triangle graph is
called unit if we can assign trapezoids, parallelograms or triangles,
respectively, so that all have unit area. As in the case of interval graphs,
the unit graphs are proper. It is straightforward to show that triangle
graphs are all proper triangle graphs. We now have 8 graph properties, Trap, Par,
Tri, UTrap, UTri, Upar, PTrap, Ppar. Of the 256 subsets of these properties, it is
possible to find 20 that describe classes of graphs (e.g. parallelogram and
proper trapezoid) that are not obviously equal to classes described by other
subsets. There are examples to show that all 20 of these classes are
different; we shall discuss some of them. Each of these classes has a transitive orientation given in a natural way
by the assignment of trapezoids, parallelograms, or triangles. It seems likely that
every orientation can be described by such an assignment, but except for
trapezoid graphs, parallelogram graphs, proper trapezoid graphs, and unit
parallelogram graphs, and triangle graphs, I am not aware of any proofs. This might make a good topic for joint work in the workshop. David BrownUniversity of Colorado at DenverVariations on Interval GraphsInterval graphs and probe interval graphs were introduced for studies in
certain biological fields specializing in genetics in
the late 50's (for interval graphs), and in the late 90's (for probe
interval graphs). The definition of a probe interval graph is conducive
to a natural extension called interval bigraphs. This extension
distinguishes a new class of interval graphs exhibiting
ties to R/L-interval bigraphs which were introduced in a non-biological
context. Classes of R/L-interval bigraphs can be generated by interval
graphs and probe interval graphs. Well-known characterizations of
interval graphs and probe interval graphs will be reviewed. Interval
bigraphs will be introduced and characterized. R/L-interval bigraphs will
be characterized. Also containment relationships between these classes of
graphs in the bipartite case will be proven. Jason DeVinneyJohn Hopkins UniversityClass Cover Catch Digraphs Theory and ApplicationsMotivated by high-dimensional classification, we investigate a class
cover problem with an associated family of directed graphs - class
cover catch digraphs (CCCD). CCCDs are a special case of catch
digraphs. In order to solve the underlying class cover problem, we
are interested in determining the domination number of any given CCCD.
We have calculated the exact distribution of the domination number of
CCCD generated from a random one dimensional process. A
characterization of CCCDs is also given. Nancy EatonUniversity of Long IslandOdd-Intersection Representations of GraphsIn an odd-intersection representation of a graph, each vertex,
v, has a finite set of labels associated with it, S(v), so that a pair of vertices
{u,v}, is an edge in the graph if and only if the size of the intersection
of the sets of labels, S(u) and S(v), is odd. The odd-intersection number of a
graph is the least number of labels used in an odd-intersection representation.
Various results are given, including a comparison between the odd-intersection
number of a graph and the rank of its adjacency matrix. Michael L. GarganoPace UniversityA Genetic Algorithm Approach to Solving the Archaeology Seriation ProblemA robust, flexible method for solving the archaeology seriation problem of Sir Flinders Petrie using a genetic algorithm(GA) approach will be discussed. Martin Charles GolumbicUniversity of HaifaSome Algorithmic Aspects of Tolerance GraphsJoit Work with Assaf Siani In this talk, we will report on several improvements on coloring tolerance
graphs and on some shortest path problems which are generalized from known
results on interval graphs. We will also discuss some results on
bipartite tolerance graphs and algorithmic questions that we have been
investigating. Garth IsaakLehigh UniversityK-Split Interval Orders and GraphsAn interval order representation has intervals [g_1(x),g_2(x)]
assigned to elements
(vertices) such that x < y iff g_2(x) < g_1(y) (the graph is the
co-comparability graph of the order).
A split interval order (equivalent to a unit bitolerance order) has 3
points g_1(x) < g_2(x) < g_3(x)
assigned to elements such that x < y iff g_3(x) < g_2(y) and g_2(x) <
g_1(y). We can extend this
an arbitrary number, k, of splitting points. This gives another notion
of dimension for orders.
We discuss basic results on these sorts of orders and graphs. Note that
another intersection
perspective on these structures is to consider k levels and look at
intersections of staircases
with vertical risers and varying length treads. Robert JamisonClemson UniversityPath Tolerance GraphsA graph G = (V,E) is a path tolerance graph with tolerance t (PT(t)-graph)
provided there is a map v --> P[v] from the vertex set V of G into
subpaths of a tree T such that vertices v and w are adjacent in G iff the
representing paths P[v] and P[w] have at least t nodes in common. The tree
T is called the host tree for the PT(t)-representation. A graph G is a
path tolerance graph (PT-graph) iff G is a PT(t)-graph for some tolerance t. Previously studied classes of path tolerance graphs include the
PT(1)-graphs, known as either path graphs or VPT graphs (for vertex
intersection graphs of paths in a tree). The PT(1)-graphs form a class
intermediate between interval graphs (where the host is a path) and chordal
graphs. PT(1)-graphs can be recognized in polynomial time. Around 1985,
several papers by Golumbic and Jamison, Syslo, and Tarjan also studied the
class of PT(2)-graphs, known as EPT-graphs (for edge intersection graphs of
paths in a tree). The recognition problem for EPT-graphs is NP-complete --
in fact, recognizing which VPT-graphs are EPT-graphs is NP-complete. This talk will show how the recognition problem for general PT-graphs
reduces to an integer programming problem and hence is at least decidable.
Some of the structure of general PT-graphs will also be discussed and
several constructions for graphs that are not PT(t) for any tolerance t
will be given. Suh-Ryung KimKyung Hee UniversityThe Competition Number of a Graph Having Exactly One HoleJoint Work with Han Hyuk Cho Let D be a digraph. The competition graph of D has the same set of
vertices as D and an edge between vertices u and v if and only if there is a
vertex x in D such that (u,x) and (v,x) are arcs of D. We call vertex x
a prey of vertex v if (v,x) is an arc of D. Then the competition graph
of a digraph D can be rephrased as the intersection graph of the family each
member of which is the set of prey of a vertex of D. The competition number of a
graph G, denoted by k(G), is the smallest number k such that G together with
k isolated vertices is the competition graph of an acyclic digraph. Roberts
[1978] showed that the competition number of a chordal graph is less than or equal
to one and it seems natural to ask about the competition number of a graph having
exactly one hole (a hole is a chordless cycle of length at least 4). In this talk,
we present the result showing that the competition number of such a graph G
is less than or equal to two, and give conditions under which the competition
number of G is less than or equal to one. We also show that if G is a connected graph with at least one pendant vertex and G' is obtained from G by deleting some pendant vertices of G, then k(G) = k(G'). Key words: competition graph, competition number, chordal graph, chordless cycle. Joshua D. LaisonDartmouth CollegeClassification of Tube Graphs and Tube OrdersBuilding on the concepts of trapezoid graphs and triangle graphs discussed
in Ken's talk, I generalize somewhat further to (n,i,f)-tube graphs.
Consider a "tube" of n parallel lines in n-dimensional space, and otherwise
in general position. In the same way that we fit trapezoids and triangles
between two parallel lines in the plane, we can fit n-dimensional polytopes
between the n parallel lines in n-space. We call a graph an (n,i,f)-tube
graph if it is the intersection graph of a set of these n-dimensional
polytopes, such that each polytope has exactly n+i vertices on the lines
and exactly f vertices in the interior of the tube (and no vertices outside
the tube). We call the set of all (n,i,f)-tube graphs T(n,i,f). I have been
interested in the containment relations between these sets, and I have a
number of results and many, many open questions. This research is motivated by a paper of Habib, Kelly, and Mohring. In
this paper, the authors prove that every result about (n,i,f)-tube graphs
extends to the analagously defined (n,i,f)-tube orders. Renu LaskarClemson UniversityElimination Orderings of Chordal GraphsJoint Work with Robert Jamison It is well known that chordal graphs are intersection graphs of subtrees of
a tree . It is also known that chordal graphs have perfect elimination
orderings. We will discuss some perfect elimination orderings of chordal
graphs. Marc LipmanOakland UniversityNine PointsJoint Work with Eddie Cheng and Serge Kruk The Sphere-of-Influence graph (SIG) of a set of at least two
points in the plane is the intersection graph of a set of open balls
centered at the points in the set. The radius of the ball centered at
point P is the shortest distance from P to the other points in the set.
Alternatively, the radius of the ball at P is the largest number so that
the open ball centered at P contains no other point from the set. For a
complete SIG, think of the balls as having to be close enough so that
each pair of balls overlaps yet far enough apart so that no center lies
inside more than one ball. Phrased that way, the maximum complete SIG
determines an invariant of the euclidean plane. It is easy to find sets
of eight points that have a complete SIG. It is known that no set of
twelve points has a complete SIG. We provide lots of evidence that no
set of nine points has a complete SIG. Marina LipshteynBar-Ilan UniversityOn the Hierarchy of Tolerance, Probe and Interval GraphsJoint Work with Martin Charles Golumbic Tolerance graphs and interval probe graphs are two generalizations of the
well known class of interval graphs. All three families are defined in
terms of being able to assign an interval on the line to each vertex of
the graph such that there is an edge between two vertices if and only if
the intersection of their intervals is non-empty and satisfies an
"extra" condition. For interval graphs, there is no extra condition.
For probe graphs, the vertices are partitioned into two sets P (probes)
and N (non-probes), and the extra condition is that at least one of the
two vertices of an edge must be in P. For tolerance graphs, the vertices
are assigned positive real numbers (tolerances), and the extra condition
is the requirement that the size of the intersection of the two intervals
must be greater than or equal to the minimum of the two tolerances in order
to produce an edge.
It is known, and easy to show, that every interval graph is a probe graph
(by choosing N to be empty), and that every probe graph is a tolerance
graph (by assigning infinite tolerance to each member of N and a small
tolerance to each member of P.) Moreover, for all three models, we can
place additional restrictions of requiring that all intervals be of unit
length or that no interval properly contains another. Clearly, a unit
interval representation is also a proper representation. Conversely,
however, it is well known that unit tolerance graphs do not equal proper
tolerance graphs, but unit interval graphs do equal proper interval graphs.
In this talk, we present the complete hierarchy of all nine subclasses
taken from { Terry McKeeWright State UniversityRestricted Circular-Arc Graphs and Clique CyclesCircular-arc graphs are natural analogs of chordal (and interval) graphs,
but without some of the features that make chordal/interval graphs
particularly nice; perhaps the biggest difference is the failure of the
Helly condition. Suppose you restrict circular-arc representations so as to have no
three or fewer arcs cover the entire circle and to have the endpoints of
arcs be distinguishable by other arcs. Such 'restricted circular-arc
graphs' now enjoy many of the nice features of chordal graphs, including
the Helly condition, and their theory is surprisingly parallel to that of
chordal graphs when 'clique cycles' are substituted for clique trees.
Restricted circular-arc graphs also have distinctive features, such as the
following characterization: (1) There are no simplicial vertices. (2) The only induced wheels are K_4s. (3) The number of vertices, minus the number of edges, plus the number of triangles, minus the number of K_4s, and so on, equals zero. The lack of simplicial vertices in particular shows that, in other ways,
we have gotten far away from chordal/interval graphs, and that their
potential applicability can be expected to be in rather different
directions from chordal/interval graphs. Geoffrey McKennaGeorge Washington UniversityTaxonomy of P-Groups that are Automorphism Groups of TreesA cheap recursive formula for enumerating isomorphism classes of rooted
trees. Analysis of the normal structure of those p-groups that are the
automorphism groups of finite trees. A verbal characterization of tree automorphism groups, along with a
bijection between tree automorphism groups and their associated words. A computationally cheap scheme for identifying a given rooted tree with a
canonical word, affording cheap computation of: - whether two given trees are isomorphic.
- the automorphism group of a given tree.
T. S. MichaelUnited States Naval AcademySphere of Influence GraphsWe define and discuss a relatively new type of proximity graph and mention some open problems. Henry Martyn MulderErasmus UniversiteitIntersection Graphs, Forbidden Subgraphs, and Elimination Schemes. An
Introductory TrajectoryInterval graphs may be described in terms of thee different models. First,
they are the intersection graphs of intervals on the real line (or
equivalently: of subpaths of a very long path). Second, a graph is an
interval graph if and only if it does not contain a forbidden subgraph from
a list of specified graphs. Third, a graph is an interval graph if and only
if we can eliminate its vertices one by one such that in each step a vertex
of a specified type is eliminated. This lecture will explore these three models "Intersection Graph",
"Forbidden Subgraph", "Elimination Scheme" for chordal graphs and tolerance
graphs. The presentation will mostly be elementary, but already at this
level applications and challenging puzzles arise. Fred S. RobertsRutgers UniversityFrom Genes to Archaeological Digs and from Traffic Lights to Childhood Development: The Many Applications of Interval GraphsThe concept of interval graph was introduced by the Hungarian
mathematician Hajos in connection with a scheduling problem and
independently by the Nobel-prize-winning geneticist Seymour Benzer in
connection with the problem of understanding the makeup of the fine
structure inside the gene. Since then, this one simple idea has had
applications in archaeology, developmental psychology, utility theory
in economics, traffic light phasing, ecology, and many other areas,
and has given rise to some fascinating mathematical theories and
algorithms. This talk will introduce the concept of interval graph. Li ShengDrexel UniversityA Characterization for a Tree to be a Unit Probe Interval GraphA probe interval graph is an variation of interval graph
that arose from the DNA physical mapping of molecular biology. Given a
graph, and a partition of its vertex set into probe vertices and
non-probe vertices, the graph is called a partitioned probe interval graph
if an interval can be assigned to each vertex such that two vertices are
adjacent if and only if their corresponding intervals have a nonempty
intersection, and at least one of the interval is a probe vertex. Unit probe interval graph is
a special case of probe interval graph where we require that all the
intervals assigned to the vertices must have the same length. We
give a characterization for a cycle free graph to be a unit probe interval
graph using a list of forbidden subgraphs. Randy ShullWellesley CollegeRelationships Between Interval Digraphs and Bounded Bitolerance DigraphsTalk based on joint work with Ann Trenk Sen, Das, Roy, and West introduced the class of interval digraphs as a
directed analogue of the well-known interval graph. A digraph is an
interval digraph if each vertex can be assigned a closed source interval
and a closed sink interval so that there is an edge from vertex u to
vertex v if and only if the source interval for u intersects the sink
interval for v. Bogart and Trenk provide a different directed graph
analogue based on the work of tolerance graphs. A directed graph is a
bounded bitolerance digraph if each vertex v can be assigned a real
closed interval I(v) = [L(v), R(v)], and left and right tolerance points,
p(v) and q(v) respectively, in I(v) so that there is an edge from vertex u
to vertex v if and only if L(u) <= q(v) and R(u) >= p(v). Note that
according to this definition, bounded bitolerance digraphs have a loop at
each vertex. For convenience, the definition is sometimes phrased to
specifically exclude loops. The class of interval digraphs and class of bounded bitolerance
digraphs are both properly contained in the class of digraphs of Ferrers dimension
at most two. In this paper we explore the structure and relationships
between these and related digraph classes. We show that the class of
interval digraphs with a loop at each vertex is a proper subset of the
class of bounded bitolerance digraphs. Ann TrenkCornell UniversityA Hierarchy of Classes of Tolerance Graphs and OrdersIn this all-institute talk we introduce tolerance graphs as a generalization
of interval graphs. Special classes of tolerance graphs arise in different
applications. For example, unit tolerance graphs (like unit interval
graphs) will have a representation using intervals that all have the same
length, and these classes can arise in the problem of assigning rooms to
one hour classes when only a limited number of rooms is available. We discuss a hierarchy of classes of tolerance graphs and prove some of the
classes are equal using geometric arguments. The ordered sets perspective
is useful in analyzing these classes. |

Page last updated June 22, 2001.