Version of 11/7/05 - note changed assignment This is now due on Wed. 11/9/05.
Drawings of graphs are continuous functions defined on the
piecewise-linear subset of 3-dimensional space by which any
graph can be represented. The codomain of a drawing is usually
taken to be a surface but later we'll see some more general
examples. A drawing f of G in a surface S is an embedding
if the function is one-to-one. It follows that for embeddings,
a graph is homeomorphic to its image under the embedding.
Let S be a set and let Y = {S_1, ..., S_n} be any family of
nonempty subsets of S, n at least 1. The intersection graph
I(Y) is the graph with Y as its set of vertices,
where S_i and S_j are adjacent if and only if i and j are
different and S_i and S_j have nonempty intersection.
Ex. 1: If Y = {[0,1], [1/2,3/2], [4,5]}, what is I(Y)?
Ex. 2: If S = (-oo,oo) and Y is a family of n distinct closed
intervals in S with the property that any two of the intervals
have a common point, what is I(Y)? Is there necessarily some
point which is in all of the closed intervals? Would this be
true if the elements of Y were not intervals?
Given a graph and a drawing of it in some surface, we shall
always require that images of vertices intersect images of edges
only when the edge has the vertex as an endpoint and that no
points from the interior of edges are mapped to vertices - i.e.,
the image of the interior of an edge never touches the image of
a vertex.
Suppose G is a graph and let f be any drawing of G in a surface
S. The crossing graph X(f) of f is the intersection graph of
the family Y = {f(e'_1), ... ,f(e'_m)}, where e_1, ... ,e_m
are the edges of G and e' denotes the interior of an edge (i.e.,
the edge with its endpoints deleted) - so e' applies not to the
graph itself but to its realization as a subset of 3-dim'l space.
Note that each e' is mapped into a subset f(e') of the surface S.
Thus, f is an embedding of the graph in S if and only if X(f) is
edgeless.
We may assume that each edge e_i is embedded by f - the argument
is just like that we used earlier to see that every walk contains
a path joining its endpoints. So if some edges in the drawing do
cross themselves, we first simplify the drawing to avoid this.
Also, if three (or more) edges intersect at some common interior
point, then by making an arbitrarily small perturbation of the
drawing, we can arrange that each pair of these edges intersects
at a separate point - and from now on, all drawings will be
assumed to have this property - i.e., the mapping f from G to a
surface S is never more than 2-to-1.
For X(f) as above:
Ex. 3: What is the number of edges of X(f)?
Ex. 4: What is the chromatic number of X(f)?
Ex. 5: What is the maximum degree of X(f)?
Ex. 6: Recalling the theorem that chi(G) <= 1 + Delta(G),
give a corresponding result for f.
Ex. 1 and 2 are trivial - or quite difficult - resp.
See class discussion.
For X(f) as above:
Ex. 3: What is the number of edges of X(f)?
Ex. 4: What is the chromatic number of X(f)?
Ex. 5: What is the maximum degree of X(f)?
Ex. 6: Recalling the theorem that chi(G) <= 1 + Delta(G),
give a corresponding result for f.
Answers:
|E(X(f))| = number of crossings in f
chi(X(f)) = ``thickness'' of f, which is the minimum number
of parts in any partition of the edge-set of G so that each
part is crossing-free
Delta(X(f)) = largest number of crossings on any one edge
``local crossing number''
Cor. For any drawing f of G, the thickness of f does not
exceed 1 plus the local crossing number.
Defining each of these for G as the minimum over all f,
thickness(G) <= 1 + lcr(G)
Now we consider an analogous situation with a strong
restriction on the surface (the plane) and on the type
of embedding. Such embeddings are determined by a choice
of cyclic order - i.e., the number of ways to seat people
around a circular table considering two such seatings to
be the same if and only if each person has the same two
neighbors.
Suppose G = (V,E) is any graph. Pick a cyclic order omega
on V and use this order to put the vertices around the
unit circle in the complex plane. Each edge of G is now
represented as a straight-line segment joining the two
points on the circle corresponding to its endpoints.
An open-edge refers to the interior of one of the line
segments. Let X(G,omega) be the intersection graph I(Y),
where Y is the set of all the open edges. Equivalently,
X(G,omega) = X(f), where f is any of the embeddings of G
in the plane corresponding to omega.
exercise
Show that G is planar provided that there exists some
cyclic order omega of the vertices V of G such that
chi(X(G,omega)) <= 2
If G is planar, it is only known that there is some omega
for which chi(X(G)) is at most 4. It is possible to give
specific examples that require three colors.
Back to the graph theory page.