Back to graph theory page
Definitions etc. 11/13/05
Graphs
The girth of a graph is the length of the shortest cycle. We
assume the graph does have some cycle. A clique in G is a subset
of the vertices which induces a complete subgraph (any two are
adjacent in G) but no additional vertex of G is adjacent to all
the members of the clique - i.e., the set of vertices is a maximal
subset which induces a complete subgraph..
G is Eulerian iff every vertex has even degree. G is Hamiltonian
iff G has a spanning cycle (one through every vertex). G is
acyclic if it contains no cycles. The line graph LG of graph G
is the intersection graph of its edges (we may assume that G is
not edgeless). Note that for two distinct edges [u,v],[w,x] of
G, the corresponding sets {u,v} and {w,x} intersect iff the
realization of the two edges by straight-line segments [fu,fv],
[fw,fx] intersect in any linear realization f of G in R^3.
A graph is called star-acyclic if it is acyclic and each nontrivial
connected component is a star graph of form K_1,p, for positive p.
Since every graph is the edge-disjoint union of its edges, there is
a positive finite least number of members in any edge-decomposition
of graph G into acyclic subgraphs; we call this the _arboricity_ of
G. Any planar graph has arboricity at most 3 and any outerplanar
graph has arboricity at most 2 (these are simple consequences of
a basic formula for the arboricity a(G) of any graph G:
a(G) = max{m'/(n'-1)}, over all induced subgraphs G' of G with n'>1
vertices and m' edges. Recall that a subgraph is induced when
adjacency in the subgraph is just the same as adjacency in the
supergraph - if two vertices are in the subgraph and adjacent in
the parent, then they are adjacent in the subgraph, too. Would
the definition change if we took _all_ nontrivial subgraphs of G
in the definition of arboricity?
We aren't proving this theorem of Nash-Williams.
Surfaces and graphs in surfaces
The Moebius band is obtained from a rectangle by identifying
opposite sides (e.g. E and W) with a twist by pi degrees, so
that N and S are reversed.
The torus is obtained from a rectangle by identifying the two
members of both pairs of parallel sides, with no twist involved.
The Klein bottle uses a twist by pi degrees for one of the two
pairs but no twist for the other, while the projective plane has
these twists for both the opposite side identifications - so that
points on the boundary are paired with each other exactly when
they are on opposite sides of the center.
The book thickness of a graph is the least number of "pages"
necessary in order to draw the graph in a book (book embedding)
so that (i) the vertices are listed along the spine in some fixed
linear order, (ii) each edge must be drawn so that it lies within
a single page, intersecting the spine exactly in its endpoints,
(iii) no two edges in the same page intersect in non-endpoints.
Here is an alternative approach which will be more convenient,
based on the crossing graph theory we've developed.
Recall that for any graph G and cyclic order omega on VG, the
graph X(G,omega) is the intersection graph of the essentially
unique drawing of G in the closed disk which places the vertices
along the circle in order omega and connects adjacent vertices
by straight-line segments, which are allowed to cross. Here,
the elements which define the intersection graph are the open
edges so edges which share a vertex are not regarded as
adjacent vertices in X(G,omega), but edge-pairs which are in
mutual conflict with the order omega become adjacent vertices
in the crossing graph X(G,omega).
bt(G,omega) = chi(X(G,omega)), where chi means chromatic number.
Define bt(G) = min bt(G,omega), all possible omega, while
bt_ham(G) = min bt(G,omega), all omega which induce Ham cycles,
where omega induces a Ham cycle iff the n edges joining the
consecutive vertices (w.r.t. omega) are all present in G, where
n is the number of vertices of G, as usual.
Given any book embedding of G, for fixed linear order lambda, just
extend lambda to a cyclic order omega by making the 1st follow the
last. Thus, given a book layout as above, one gets a cyclic order
on the vertices, and edges on the same page won't conflict with the
order. Thus, bt(X(G,omega)) is at most the book thickness of G
using lambda. But any coloring of the edges of X(G,omega), with
the property that edges of the same color don't have an interior
crossing, produces a division of the edges into pages for any of
the linear orders obtained from omega by cutting the page, and
hence the number of pages is at most the chromatic number so they
are equal.
Thus, an alternative way to describe book thickness is that it is
the least number of layers needed so that if the vertices of the
graph are placed around a circle, one can accomodate all of the
edges on the layers with no crossings.
Call the subgraph of G which is induced by a layer a layer-graph.
Recall that a graph is outerplanar if it can be drawn in the plane
so that all of the vertices of the graph occur on the boundary of
the infinite region. By definition, every layer-graph of a book
embedding of G is an outerplanar graph, where the ordering around the
infinite region is the same for every page.
We consider two further variants of book thickness. For G a graph,
bt_1(G) denotes the least number of layers needed for a book
embedding of G with the property that all the layer graphs have
maximum degree equal to 1; i.e., each vertex of G is incident with
at most one edge in each layer. Clearly, bt_1(G) is at least the
maximum degree Delta(G) of G. Why?
Also, we write bt^2(G) to mean the least number of pages in a book
embedding, where each layer-graph has diameter at most 2.
Back to graph theory page