Figure 1: Alternating diagrams of the trefoil and its mirror image
| Topology Atlas Document # taic-38 | Topology Atlas Invited Contributions vol. 5 issue 1 (2000) 20-26 |
Fachbereich Mathematik, Universität Dortmund, 44221 Dortmund, Germany
E-mail: sawollek@math.uni-dortmund.de
WWW: http://www.mathematik.uni-dortmund.de/lsv/sawollek
The aim of this brief survey is to give a short introduction to main problems of topological graph theory. Embedding problems are considered from a graph theoretical and from a knot theoretical point of view. For a general introduction into the field see, for example, [11], [27], [25]. A more extensive survey of topological graph theory, including hundreds of citations, can be found at Dan Archdeacon's homepage [4], as well as a collection of open problems in topological graph theory [5].
The main purpose of topological graph theory is to consider geometric realizations of a graph and its embeddings in 3-space or its embeddings or immersions in the plane or surfaces of higher genus. When studying the arising objects, it is possible to characterize intrinsic topological properties of the graph such as those described in the following.
Conceiving of embedding graphs into R3 as a natural generalization of knot theory, where embeddings of the loop graph consisting of one vertex and one edge are considered, the different embeddings of a given graph and their properties may be investigated. From a graph theoretical point of view, it is interesting which properties of a graph do not depend on the specific embedding but are immanent in the structure of the abstract graph. For example, a graph is called intrinsically chiral if every embedding of the corresponding topological graph is chiral, i.e., there does not exist an orientation reversing autohomeomorphism of R3 that maps the embedded graph onto itself. In [9] the intrinsically chiral 3-connected graphs are characterized by the existence of certain automorphisms of the graph group. As a consequence, it can be shown that among the complete graphs Kn on n vertices exactly those with n = 4k+3, for k => 1, are intrinsically chiral.
A graph is called intrinsically knotted if every embedding contains a non-trivial knot, i.e., a subgraph in form of a cycle that is not equivalent to a simple closed curve in the plane. Likewise, a graph is intrinsically linked if every embedding contains a pair of linked cycles, i.e., a subgraph consisting of two cycles which cannot be separated by a 2-sphere embedded in R3. In [18] it is shown that an embedding has no linked cycles if and only if it is flat , i.e., each cycle of the embedded graph bounds a disk disjoint from the rest of the graph, and, furthermore, that a graph is intrinsically linked if and only if it has a minor , i.e., a graph that arises from a subgraph by contracting edges, in the so-called Petersen family which consists of seven graphs. An analogous characterization for intrinsically knotted graphs is still missing, see [14].
Intrinsic structure of whole classes of graphs can be revealed by Ramsey-type theorems for knotted graphs. In [15] it is shown that for every knot, link, or spatial graph K there exists a positive integer R(K) such that K or its mirror image , i.e., the result after applying an orientation reversing autohomeomorphism to R3 (see Fig. 1),
is contained in every rectilinear embedding of Kn for all n => R(K) (observe that it is necessary to require the embeddings to be rectilinear or to assume similar restrictions such that the graph edges are not embedded locally knotted, see [16]). The corresponding result for complete multipartite graphs is proved in [23]. In general, it is very difficult to determine the Ramsey number of a given knot K, i.e., the minimal number R(K) with respect to the property described above. In [1] it is shown that the Ramsey number of the trefoil (see Fig. 1) is equal to seven by using the theory of oriented matroids.
i.e., images under regular projections to an appropriate plane equipped with over-under information at double points (called crossings ). Two graph diagrams D and D' are said to be equivalent if the corresponding graphs in R3 are equivalent. The crossing number cr(G) of a graph G is the minimal number of crossings in any diagram of G. These definitions are formulated from a knot theoretical point of view. Knot theorists are interested in generalizations of known theorems on knot diagrams to diagrams of embedded graphs. In [20] and [21] theorems on alternating knot diagrams, i.e., over- and undercrossings are alternating with each other while walking along the knotted curve in the diagram (see Fig. 1), known as Tait conjectures are extended to 4-regular graphs. For example, one of these theorems ensures that each of the diagrams in Fig. 1 has minimal crossing number with respect to equivalent diagrams. Of course, the crossing number of the underlying graph is zero because the loop graph is planar; changing one crossing in any diagram in Fig. 1 yields a diagram of the unknot, for example. A crucial difference between diagrams of a knot and diagrams of an arbitrary graph is due to the fact that a knot can be unknotted in any diagram by appropriate crossing changes while a diagram of an arbitrary graph, even a planar one, can in general not be transformed by crossing changes into a diagram that is equivalent to one with minimal crossing number, see [24] and [22].
In graph theory, the equivalent definition of cr(G) as minimal number
of crossings in a good drawing of G (see Fig. 2) is
more common which essentially means that it is not distinguished between
over- and undercrossing arcs at a crossing and that some situations are
excluded in which the number of crossings obviously can be diminished.
There are a lot of unsettled questions concerning crossing numbers. For
example, the conjectured crossing numbers of the complete graph Kn,
the complete bipartite graph Km,n, and the product of cycles
Cm x Cn are as follows where the confirmed cases are given
in brackets (it is always assumed to be 3 <= m <= n):
*
| cr(Kn) | = 1/4 [n/2] [(n-1)/2] [(n-2)/2] [(n-3)/2] | (n <= 10 [8]) |
| cr(Km,n) | = [m/2] [(m-1)/2] [n/2] [(n-1)/2] | (m <= 6 [12], m = 7 and n <= 10 [28]) |
| cr(Cm x Cn) | = (m-2)n | (m <= 6 [13], m = n = 7 [2]) |
There are nearly no other general results concerning the crossing number of graphs.
Even less is known about the rectilinear crossing number
cr-(G) of a graph G, i.e., the minimal number of crossings
in a drawing of G in which all edges are realized as straight line
segments.
Of course, the inequality cr(G) <= cr-(G)
holds and, if the conjectured values for cr(Km,n) and
cr(Cm x Cn) are correct,
then the equality cr(G) = cr-(G) holds in both cases.
Furthermore, it is believed that
cr(Kn) < cr-(Kn)
for n => 10 but there does not seem to be a
reasonable conjecture on the values cr-(Kn)
for n => 10.
Finally, it can be shown that
limn to infinity
cr(Kn) / n4
and
limn to infinity
cr-(Kn) / n4
exist (see [25]) and it is
conjectured that both limits are equal to 1/64.
Following [7], there exist graphs
with crossing number greater than or equal to four and arbitrarily high
rectilinear crossing number and, on the other hand,
for every graph G with crossing number cr(G) <= 3,
the equality cr-(G) = cr(G) holds.
The minimal genus of an orientable closed surface such that a given graph G can be embedded into it is called the genus g(G) of G . The corresponding number with respect to non-orientable closed surfaces is called crosscap number of G. Clearly, an upper bound for the crosscap number of G is given by 2g(G)+1. While the values for Kn, Km,n, and the cube Qn are well-known (see [11]) it is, for example, an open problem to determine genus or crosscap number of the complete tripartite graph Kp,q,r.
A 2-cell embedding of a graph G on a closed surface S is an embedding such that every component of S \ G is homeomorphic to an open disk. Observe that the closure of a component of S \ G in a 2-cell embedding is not necessarily homeomorphic to a closed disk (as an example, consider an embedding of the graph consisting of one vertex and two edges on the torus such that the edges correspond to a meridian and a longitude, respectively). In case this property holds for every component, the embedding is called a strong embedding . The strong embedding conjecture claims that every 2-connected graph has a strong embedding on some closed surface. It is known to be valid for graphs that are planar or embeddable in the projective plane [6], graphs that contain no K5-minor [30], and graphs with crosscap number at most five [29].
The chromatic number of a closed surface S is the least number of colours needed to colour the faces S \ G of any 2-cell embedding of any embeddable graph G such that each two faces that share the same edge have different colours. The proof of the Heawood map colouring theorem , stating that the chromatic number of a closed surface with Euler characteristic c <= 1, with the Klein bottle being the only exception, is [(7 + sqrt(49-24c)) / 2], * heavily relies on the calculation of genus and crosscap number of Kn, see [11]. The theorem is also valid in the remaining case c = 2 (the related surface being the sphere) but its proof is completely different and even more complicated. The corresponding statement is the famous four colour theorem for which recently a shorter proof (with respect to the original one by Appel and Haken) has been found, see [17].
A problem concerning colourings that still is unsolved is the entire colouring conjecture which states that the vertices, edges, and faces of any embedding of a planar graph in the plane can be coloured simultaneously with D + 4 colours such that each of two incident or adjacent vertices, edges, or faces receive distinct colours where D denotes the maximal degree of the graph's vertices. For recent progress in this question, see [19].
Date published: August 15, 2000.