DREI '98 Graph Theory & Combinatorial Optimization

"The Cycle Space of a 3-connected Hamiltonian Graph"

Let G be a 3-connected graph with minimum degree at least d and let Z(G) be the cycle space of G over the field GF(2). Adrian Bondy conjectured that if G has at least 2d vertices then every cycle in Z(G) can be written as the sum of an odd number of cycles, each having at least 2d-1 edges. Removing the parity requirement produces the following slightly weaker conjecture: Conjecture 1: If G has at least 2d-1 vertices then Z(G) has a basis consisting of cycles, each having at least 2d-1 edges. Locke proved Conjecture 1 when G is not hamiltonian, exploiting relationships between longest cycles of G and their bridges. The case when G is hamiltonian requires a modified attack, by means of which Barovich and Locke have shown that if G is a counterexample to Conjecture 1 and v is the cardinality of the vertex set of G then G is hamiltonian, 8 < v < 4d-7 and for every vertex x of G, G-x is 2-connected or hamiltonian.

"Triangular imbeddings of $G_{(m)}$"

Here $G_{(m)}$ denotes the lexicographic product of a simple graph $G$ by an independent set of size $m$. We try to derive a triangular imbedding of $G_{(m)}$ into a closed surface $\tilde S$ from a known triangular embedding of $G$ in a closed surface $S$, the surfaces $S$ and $\tilde S$ being both orientable or not. We conjecture that the construction is possible except for a small number of cases. We proved some years ago that it is possible when $m$ has no divisor 2, 3 or 5 (nowhere-zero flows are used). It is also possible when $G$ has even degrees. In a joint work with Dominique B\'enard and Bruce Richter we obtain some new results when $m = 2$.

"On the Maximum Planar Subgraph Problem"

Maximum Weight Planar Subgraph is the following NP-hard problem: given an undirected graph G, with weights on the edges, find a planar subgraph of G of maximum weight. One can prove that a maximum spanning tree in G has weight at least one third of the optimum. Many polynomial-time algorithms had been presented prior to ours, but, even in the unweighted case, none could guarantee a ratio bigger than 1/3 when comparing the output to the optimum.

Using graphical matroid parity, we devised an algorithm with higher approximation ratio (4/9 = 0.44 instead of 1/3 = 0.33) for (unweighted) Maximum Planar Subgraph. The algorithms for the unweighted case do not work in the weighted case. Based on the Berman-Ramaiyer Steiner tree algorithm, we obtained the first algorithm with a nontrivial approximation ratio for Maximum Weight Planar Subgraph.

Maximum Planar Subgraph is joint work with Cristina Fernandes, Ulrich Finkler and Howard Karloff. The results on Maximum Weight Planar Subgraph were obtained in collaboration with Cristina Fernandes, Howard Karloff and Alexander Zelikovsky.

"Defective Coloring of Graphs on Surfaces"

We define a $(k,d)$-coloring of a graph as a coloring of the vertices with $k$ colors such that each vertex has at most $d$ neighbors of its same color. For a graph $G$ we define $\chrom_d(G)$ as the minimum $k$ such that there is a $(k,d)$-coloring of $G$. So a $(k,0)$-coloring is a proper coloring, and $\chrom_0(G)$ is the usual vertex chromatic number of the graph. (Joint work with Wayne Goddard, University of Natal, S.A)

"Topological Graph Theory on Vox-solids"

The objective of this work is the study of voxelable graph embeddings and their applications. These graphs appear in the study of solids digitized into unitary cubes (voxels), with coordinates in the integer lattice of $\rtres$. When the boundary of a solid so digitized is a surface we say that it is a vox-solid; the face adjacency graph embedding of a vox-solid $\voxsolid$ is the graph whose vertices are the voxel's faces on the boundary of $\voxsolid$, and two vertices are joined by an edge when the associated faces exactly share one side. A graph embedding $\Psi$ is voxelable when there exists a vox-solid $\voxsolid$ whose face adjacency graph embedding is isomorphic to $\Psi$. The main conjecture is that every voxelable graph is Hamiltonian. This work can be seen as a restricted version of a very difficult question: Which $4$-regular, $4$-connected graphs are Hamiltonian? The restrictions imposed are interesting both theoretically and practically. We force the $4$- regular graphs to be the face adjacency graphs of a discrete body. The main line of thinking behind our approach is that under these assumptions we are able to characterize infinite families of Hamiltonian $4$- regular graphs for every oriented surface in contrast to characterizing the whole family for each particular surface as for example the well known result of Tutte for the plane and the more recent results of R. Thomas and X. Yu for the torus and projective plane. At first glance one can be tempted to prove several results by inductive arguments; that is by proving a proposed property $P$ on one voxel and then extending the argument by adding step by step a new voxel until we obtain the voxsolid. Vox-solids for which there exists an ordering of its voxels into a sequence $V_1, . . . , V_n$ in such a way that for each $i$, ($1 \leq i \leq n $) the chain { $V_1, . . . , V_i$ } is a vox-solid are called step-voxsolids. An interesting problem is to characterize these vox-solids. We prove that every face adjacency graph embedding is 4-connected by giving a general characterization of those 4-connected 2-cellular graph embeddings having representativity 4. We also proved that if we refine a vox-solid by dividing its voxels in eight identical sub-voxels then we get a vox-solid whose boundary adjacency graph is always Hamiltonian.

"Hamilton Cycles in Caley Graphs"

We complete the proof of the Negami 1, 2, infinity conjecture for embedding covering spaces of a finite graph, namely, every graph is planar, has a planar double covering, or else no finite covering of it is planar. We do this by showing that K_{2,2,2,1} has no finite planar covering.

"A Characterization of Weakly Bipartite Graphs"

A labeled graph is said to be weakly bipartite if the clutter of its odd cycles has the weak max-flow min-cut property (also known as ideal property). Seymour conjectured that a labeled graph is weakly bipartite if and only if it does not contain a minor called an odd $K_5$. I will present a proof of this conjecture. An extension of this result and connexions with multi-commodity flows will also be discussed.

"Between planarity and flatness"

Let $G=(V,E)$ be a graph and let $S$ be a subset of $V$. An invariant $\mu_r(G,S)$ is introduced for pairs $(G,S)$, which is similar to the graph invariant $\mu(G)$ introduced by Y. Colin de Verdiere. We show which pairs satisfy $\mu_r(G,S) \leq 2$. Then a new discrete structure is introduced. Using this discrete structure we give a definition of planarity for pairs $(G,S)$. We show that these pairs satisfy $\mu_r(G,S) \leq 3$ (the converse is still open). A relation of flat graphs with planar pairs $(G,S)$ is given.

"Clases in Prague?"

How can you divide a class into working groups so that every pair works togethr exactly once? How can you represent a graph in a grid using a Prague embedding? Surprisingly, there is a connection between these two problems, the first a famous problem regarding orthogonal latin squares and the second a problem regarding the prague dimension of complete graphs. We will discuss this connection as well as breifly reviewing some other ways to geometrically `embed' graphs using lines, circle and boxes.

"Coloring Knots and Graphs"

This talk explains how one can use an attracive coloring problem for knot and link diagrams to get topological information about them. In joint work with Frank Harary we define a new invariant of knots, the colori ng number C(K). This is the least number of colors needed to color any dia gram of the knot (i.e. any diagram representing the same topological type). The coloring number is difficult to compute and leads to a number of interesting conjectures.

"Virtual Knot Theory"

A Gauss code is a sequence of labelled symbols such that every symbol inthe sequence appears exactly twice, each symbol is labelled with an O (over) or a U (under) and so that each symbol appears once label led as O and once labelled as U. A pair of symbols in the code is called a abstract crossing in that code. A virtual knot or link is a Gauss code with assigned orientations (signs) at its abstract crossings, taken up to the equivalence relation generated by Reidemeister moves defined on these codes. Most of the theory of knots and links generalises to these abstract code s, with sometimes very fascinating variations and relationships with knots and links that embed in three manifolds of the form MxI where M is an orientable surface and I is the unit interval. This talk explores various properties of virtual knots, inculding virtual knots that are non-trivial but have trivial Jone polynomial, and quantum invariants and Vassiliev invariants of virtual knots.

"Integral Heuristics"

This talk shows how much of the theory of Vassiliev invariants of knots and the intricate combinatorics of chord diagram evalustions is motivated by Witten's functional integral. The integral is a formal device that holds an enormous trove of combinatorics. We explain these heuristics at the level of naive advanced calculus.

"Graph Planarity"

We present some of our recent developments on graph planarity in different directions. One direction concerns various strengthenings of Kuratowski's planarity criterion. We will discuss from this point of view quasi 4--connected graphs and cubic bipartite graphs. Another natural direction is to study various generalizations of matroid duality of graphs and strengthenings of Whitney's planarity criterion. We will discuss in particular some results on semi--duality of graphs.

"Loose Ends in Knot Theory (The Computational Complexity of Unknotting)"

The problem of distinguishing knotted curves from unknotted ones has a long history. However only in 1961 did Wolfgang Haken give an explicit decision procedure to recognize unknottedness, based on normal surface theory. This talk reviews the history of problems in computational topology and knot theory. It then describes explicit complexity bounds for the unknotting problem, obtained using the Haken approach. Recognizing if a knot diagram with n crossings is unknotted is in the complexity class NP. There is an algorithm to decide unknottedness which halts in at most O(2^cn) bit operations. If a knot diagram is unknotted, then there is an explicit unknotting that takes at most O(2^cn) Reidemeister moves, with c=10^12. (The first two results are joint work with Joel Hass(U. Calif.-Davis) and Nick Pippenger(U. British Columbia); the last with Joel Hass.).

"Topological subgraphs in graphs of given average degree"

It is well known that for every positive integer n there is a least integer f(n) such that every finite graph of minimum degree f(n) contains a subdivision of the complete graph K_n.We survey recent results on this function f and related results, imposing further conditions on the graphs or the subdivisions, and compare them to results on minors K_n.

"The Geometry of Fullerenes"

Before chemists discovered Buckminsterfullerene, and looked for other related molecultes, geometers had already studied some of their combinatorial properties. Fullerenes are fascinating geometrical objects and there are many simple questions about them that need answering.

"Embedding Graphs into a d+1-page Book with O(m log_d n) Edge-Crossings Over the Spine"

This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it is shown that there exists a 3-page book embedding of G in which each edge crosses the spine at O(log_2 n) times. This paper consider a book with more pages than three. In this case it was known that a complete graph K_n with n vertices can be embedded in a n/2-page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This paper shows that there exists a d-page book embedding of G in which each edge crosses the spine at most O(log_d n) times. As a direct corollary, we can obtain that for any real number s, there is an n^s-page book embedding of G in which each edge crosses the spine at a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d if n is sufficiently large compared with d then for any embedding of K_n into a d-page book, there must exist \Omega(n^2 \log_d n) points at which edges cross over the spine.

"Flexibility of graph embeddings"

By the well-known result of Whitney, 3-connected planar graphs admit combinatorially unique embedding in the 2-sphere. Several generalizations of this result to graphs on arbitrary surfaces will be presented.

"Quadrangulations on closed surfaces covered by vertices of degree 2, 3 and 4"

A quadrangulation on a closed surface F2 is a simple graph which has been embedded in F2 so that each face is quadrilateral. A quadrangulation G is said to be k-covered if for any e = a;y ~ E(G), de"(x) = k or de"(y) = k. In this talk, we first show that for any closed surface F2 and any natural number k > 2, there exist k-covered quadrangulations on F2, and secondly characterize the k-covered quadrangulations on closed surfaces with k = 2,3,4. THEOREM 1. A quadrangulation G is 2-covered if and only if G is a planar quadrangulation isomorphic to K2,r, for some n > 2. Let G be an embedding on a closed surface F2. Put a vertex v on a face f of G and join v with all vertices lying on the boundary walk of f. Apply this operation to each face of G and delete all edges of G. Then the resulting bipartite graph on F2 is called the radial graph R(G) of G. THEOREM 2. A quadrangulation G is 3-covered if and only if either G is isomorphic to the radial graph R(K) for some triangular embedding K (possibly with multiple edges) on a closed surface, or G is isomorphic to one of the e~ceptions on the sphere and the projective plane. For the 4-covered quadrangulations on closed surfaces, we give a constructible characterization.

"Diagonal flips in pseudo-triangulations on closed surfaces"

Negami has already shown that there is a natural number N(F2) for any closed surface F2 such that two triangulations on F2 with n vertices can be transformed into each other, up to equivalence, by a sequence of diagonal flips if n > N(F2). Any diagonal flip in the sequence has to keep the simpleness of triangulations. However, we shall consider diagonal flips in pseudo-triangulations to give an upper bound for N(F2). A pseudo-triangulation G on a closed surface F2 is a triangular embedding of a graph G on F2 which may have multiple edges or self-loops. Define the diagonal crossing number crv(G~'G2) of two labeled graphs G~ and G2 on F2 with the same vertex set V(G~) = 3DV(G2) as the minimum number of crossings on their edges when we put them together on F2. Then we have the following theorem:

= THEOREM 1. Let G~ and G2 be two labeled pseudo-triangulations on a closed surface F2 with the same number of vertices. Then they can be transformed into each other, up to equivalence, by a sequence of diagonal J7ips of length at most = crv(G~, G2). As an application of this theorem, we can prove the following theorem as we expect. = THEOREM 2. There is a linear upper bound for N(F2) with respect to the genus g of the surface F2; N(F2) = 3DO(g).=20

"Coloring of Colored And Mixed Structures"

We survey recent results related to homomorphisms and colorings of graphs and relational structures. We illustrate some unifying features (such as density and duality; joint work with C.Tardif) as well as differences. In this framework we discuss restricted colorings (joint work with A.Raspaud) and OPPDC and CDC problems (joint work with J.Maxova).

"A characterization of those topologically-minor-minimal graphs of crossing number at least 2 which have no $V_8$ minor."

In joint work with Neil Robertson and Dirk Vertigan, we have characterised the topologically-minor-minimal graphs of crossing number at least 2. In this talk we consider those which have no $V_8$ minor.

"Shortest Connecting Networks"

The old Bell Laboratories became interested in shortest connecting networks in the 1950's, for reasons one might not at first expect. This talk will trace this history up to the present time. We shall highlight the interplay of the development of the mathematics and of the applications, and the insights we get into the modeling process. Research by both Gauss and DIMACS will turn out to be important.

"Vertex Accumulation Points in Infinite Planar Graphs"

If an infinite graph is drawn in the plane, there may be sequences of distinct vertices that converge to a limit point. Halin and Thomassen have given characterizations of those graphs that have an embedding with no such accumulation point. Halin showed that there are four "Halin graphs" such that a connected planar graph has an accumulation point free embedding in the plane if and only if the graph has no subdivision of one of the four graphs.The purpose of this research is to try to generalize their work to provide a more detailed understanding of planar graphs and their accumulation points. We have theorems such as the following.

1. Let G be a locally finite graph embedded in the plane with a discrete set of accumulation points. Let B be the space generated by the face boundaries and let Z be the space generated by the cycles and 2-way infinite paths. Then dim(Z/B) is the number of accumulation points.

2. A locally finite planar graph has an embedding in the plane with finitely many accumulation points if and only if it does not contain an infinite sequence of "finitely-disjoint" Halin graphs. In the event the accumulation points are not discrete, the theory is much less clear. An example involving the "pseudoarc" gives some indication of the difficulties involved. This is joint work with C. Paul Bonnington.

"Trees and Euler Tours in Planar Graphs and Its Relatives"

A graph (or network) consists of points (or vertices), some pairs of which are joined by an edge. (Electrical networks, highway systems, molecules and communications networks are all examples of graphs.) A graph is planar if it is drawn in the plane so that the vertices are points and the edges are curves joining the points representing the ends of the edge.

In this talk, I will describe a few aspects of planar graphs. Every planar graph has a dual graph, obtained by placing a new vertex in each face and joining these by edges whenever the two faces have a common edge. We will see that the number of spanning trees of a planar graph and its dual are always equal.

Every planar graph has a medial graph, which is obtained by placing a new vertex in the middle of each edge and joining two such new vertices by an edge whenever they are consecutive around an original face. So every vertex of the medial graph has valence 4. We can naturally direct the edges of the medial graph so that at each vertex the edges alternate in-out-in-out. The number of directed Euler tours in this directed medial graph equals the number of spanning trees in the original graph.

Finally, we can find in the medial graph a certain kind of directed spanning tree, called an arborescence. It has a root vertex and every edge of the tree is directed away from the root, so all other vertices have "in-degree" 1 in the tree. The number of such arborescences is equal to the number of directed Euler tours, and so is equal to the number of spanning trees in the original graph.

This talk is based on my article, with Mark Kidwell, in the American Mathematical Monthly, Vol. 94 (1987) 618-630.

"On the crossing number in orientable surfaces of the projective plane grid"

The crossing number in every orientable surface of the projective plane grid is quadratic in the representativity.

"Digraph Minors"

The "graph minors" project was very fruitful, with all kinds of nice results. But what about digraphs, is there any hope of an analogue of the graph minors theorems for digraphs? What is a minor of a digraph anyway? How hard is it to test if one digraph is a minor of another? Is there such a thing as the treewidth of a digraph? This talk is a survey of some preliminary investigations into these questions, partly joint with Matt DeVos, Thor Johnson, Bruce Reed, Neil Robertson and Robin Thomas.

"Group representations and graph embeddings"

A number of theorems on highly symmetrical embeddings of graphs rely on representations of groups. We describe the connection of group representations to graph embeddings and survey briefly the known results. Focusing on representations within the symmetric groups or matrix groups we outline new results on C)ayley maps and other highly symmetrical graph embeddings.

" The looseness of triangulations on closed surfaces"

A triangulation G on the closed surface F2 is called tight if there is a face of G which has three distinct colored vertices on its boundary for any surjective color assignment f: V(G) ~ {1,= 2,3}. (Such a face is called a heterochromatic face.) For example, Arocha, Bracho and Neumann-Lara have discussed on = triangular embeddings of the=20 complete graph Kn into surfaces and shown a certain method to = constract a series of tight triangulations with complete graphs and a series of uptight ones. This concept is extended by Negami and Midorikawa.=20 A triangulation G is called k-loosely tight if there is a heterochromatic face for any surjective color assignment f: V(G) ~ {1,2,3,. . . ,= k + 3}. The looseness of a triangulation G is defined as the minimum value of k such that G is k-loosely tight, and is denoted by ((G). The looseness ((G) depends on the embedding of G in general. However, we shall show that ((G) is determined only by the combinatorial structure of G in some special cases. We denote the independence number and the diameter of G by a(G) and dia(G), respectively. = THEOREM 1. Let G be a triangulation on the sphere, the projective plane, the torus or the Klein bottle. Then G is 1-loosely tight if and only if a(G) < 2 and dia(G) < 2.=20 = THEOREM 2. If G1 and G2 are two triangulations on the projective plane that are isomorphic to each other as graphs, then ((G1) = 3D((G2)

" Tutte's edge 3-coloring conjecture"

Tutte conjectured in 1966 that every 2-connected cubic graph with no minor isomorphic to the Petersen graph is edge 3-colorable. The conjecture implies the Four Color Theorem by a result of Tait. In the first part of the lecture I will discuss related results and problems. In the second part I will outline a proof of Tutte's conjecture obtained in joint work with N. Robertson, D.P. Sanders and P.D. Seyour

"New Bounds on Crossing Numbers"

The crossing number of $G$ is the minimum number of crossing points in any drawing of $G$ in the plane. Ajtai, Chatal, Newborn, Szemer', and independently Leighton proved that, for any graph $G$ with $n$ vertices and $e\ge 4n$ edges, we have over n^2, where 1/64$ is a suitable constant. (We show that this remains true with a somewhat better constant $c={1\over 33.75}$.) The order of magnitude of this bound cannot be improved, in general. However, we establish much stronger results for graphs satisfying some monotone properties. In particular, we show that if $G$ contains no $C_4$ as a subgraph and 400n, then {1\over 10^7}{e^4\over n^3}$ and this bound is also best possible, apart from the exact value of the constant. This settles a question of M.Simonovits.The pairwise crossing number, pair-cr resp. the odd-crossing number,odd cr of $G$ is the minimum number of pairs of edges that cross resp.cross an odd number of times over all drawings of $G$. Clearly, odd-cr G pair-cr G G$. It is a challenging open question to decide whether these three numbers coincide for every graph $G$. We prove that the largest of these numbers, cannot exceed twice the square of the smallest. Joint work with J. Pach.

"The Classification of Planar Groups"

Call a group A planar if it has a Cayley map whose underlying surface S is planar, that is, an open subset of the sphere; here Cayley map means an embedding of a Cayley graph G for A such that every rotation is the same or reversed, so that the action of A extends to the surface S, possibly including orientation-reversing homeomorphisms. We are interested in classifying infinite, finitely generated planar groups, by the number of ends ( either 1,2 or infinity). The finite-ended cases are reasonably well-understood as folk theorems: one-ended planar groups are euclidean or hyperboliccrstallographic groups, and two-ended planar groups are the seven cylindrical groups analagous to the seven symmetry groups for friezes.

The infinite-ended case is given here:

The finitely generated, infinite ended group A is planar if and only if A is ( in the language of combinatorial group theory) the fundamental group of a graph of groups such that the graph is a finite tree T, the vertex groups are one-ended or two-ended planar groups, and the group corresponding to edge e is the cyclic or dihedral stabilizer of a point in the planar actions given by the two components of T-e ( the cyclic and dihedral groups of order two are considered different here) The condition on the amalgamating subgroups is necessarily complicated, but has clear geometric meaning. Although this classification could be expected, it is by no means obvious that a finitely generated planar group is even finitely presented. The proof uses standard low-dimensional topology methods to find equivariant, geodesic closed curves, and is anticipated by work of B. Maskit in the late 1960's on regular planar coverings. If every Cayley graph for the group A is 3-connected, then the group A is planar if and only if it has a planar Cayley graph. On the other hand, as Droms, Servatius, and Servatius have observed, the free product of the cyclic groups of order 6 and 4 with amalgamation over the cyclic group of order 2, better known as SL(2,Z), has 2-connected planar Cayley graph; by the above classification, the group is now known not to be planar.

"Cayley Maps"

A Cayley map is an embedding of a Cayley graph where the rotation at every vertex is the same. A general theory of Cayley maps is developed in the context of maps ( especially regular maps), groups acting on sets, and branched covering spaces. The fundamental problem is determining when a given map is a Cayley map. Results include: Theorem 1: A regular map of valence d, with dart group G and rotation r, is a Cayley map if and only if there is a homomorphism from G to the symmetric group on d symbols taking r to the long cycle (1 2 3...d). Moreover, the Cayley map is balanced, respectively antibalanced, if and only if the image of this homomorphism is cyclic, respectively dihedral. Theorem 2: The planar tesselation of faces of size f and vertices of valence d is a Cayley map if and only if f has a divisor less than or equal to d other than 1). d Theorem 3: Given any finite collection of finite maps, there is a single, regular Cayley map that regularly covers each of the maps. ( Joint work with L Goddyn, R.Jajcay, R.B.Richter, J.Siran, and M.E.Watkins)

"A Whitney 2-Isomorphism theorem for hypergraphs"

In joint work with Bogdan Oporowski and Neil Robertson, we have characterised the topologically-minor-minimal graphs of crossing number at least 2. In this talk we consider those which have a $V_8$ minor. The list is infinite.

"Light subgraphs of multigraphs embedded in compact 2-manifolds"

In the talk I will report on our results on 3 - connected graphs and 3 - connected multigraphs embedded in compact 2 - dimensinal manifolds. to his abstract that I have sent earlier.

"Reconstructing graphs embedded in surfaces and coloring"

In this talk, a brief survey about the edge reconstruction conjecture will be given. Then we will prove that if a connected graph G embeddable in a surface S of characteristic c(S) satisfies: (1) the minimum degree of G > 4, (2) |V(G)|>-43c(S), then G is edge reconstructible. A direct consequence of this result is that a triangulation G of a surface S of characteristic c(S) is edge recdonstructible if |V(G)|>-43c(S)