11   Advanced Drawings of Graphs
Since not all graphs are planar, it is natural to ask what can be done about "nice drawing" of the nonplanar ones. Two possible approaches come in mind first:
Either we stick with the definition of a proper embedding, and generalize a drawing from the plane to so-called higher surfaces, or
we on the other hand allow edges in a drawing to cross each other (but not too often). We shortly outline these directions here.. .
Brief outline of this lecture
• Higher surfaces, and graph embeddings on them.
• Properties of embeddable graphs on surfaces.
• Graph crossing number, crossing minimization.
• A curiosity - the planar cover and planar emulator problems.
11.1   What is a Higher Surface
We start with one result of classical topology - the surface classification theorem.
Theorem 11.1. Every surface (a compact 2-manifold without boundary) is homeo-morphic to one of □
- So the sphere,
- Sh the sphere with h added handles,
- Nk the sphere with k added crosscaps.
The operation of adding handles is easily visualized as on the left picture.
Since crosscaps are harder to imagine in Euclidean geometry, we may (almost) equivalently visualize that as adding Möbius bands, see on the right.
Definition: A crosscap is a circle (on the surface) such that all its pairs of opposite points are indentified, and the interior of this circuit is removed.
Notation: Si is a torus (see on the left) - the surface of a donut.
7Vi is a projective plane; if an open disc is removed from TVi, then we get a Möbius b.
7V2 is the Klein bottle (right); obtained by glueing two Möbius bands together.
So and Sh are orientable surfaces, while all Mk are nonorientable. c
It is instructive to see why no other surfaces can result by combined adding of handles and crosscaps: c
Lemma 11.2. If a surface £ is obtained from the sphere by adding k > 2 crosscaps and h handles, then £ is homeomorphic to the one obtained by adding k — 2 crosscaps and h + 1 handles.
Notation: Inspired by classical topology, a surface can be represented as a polygon (disc) with prescribed oriented identification of its edges.
See the examples for the projective plane and the torus below.
11.2   Graph Embeddings in Surfaces
Definition 11.3. (cf. Definition 8.1) An embedding of a graph G on the surface £ is a mapping which takes the vertices of G onto distinct points of £, and the edges of G onto simple arcs in £ connecting their ends. No two edges are allowed to cross each other, and no edge is allowed to pass through another vertex, c
• In order to smoothly translate properties of planar embeddings to other surfaces we moreover need:
Definition: An embedding of a graph G into £ is cellular if each its face (without boundary) is homeomorphic to an open disc.
Fact: A cellular embedding of 2-connected G is uniquely determined by its facial cycles, and this embedding also defines the underlying surface £ up to homeomorphism.
In other words, £ is "glued together" from the facial discs along shared edges, c
Proposition 11.4. A cellular embedding of a graph G into an orientable surface is uniquely determined by the rotation scheme of its edges.
A rotation scheme of a graph G determines the cyclic ordering of the edges around each of its vertices.
Embedded graphs
Recall that the complete graph K$ is not planar.
Proposition 11.5. There exist embeddings of the complete graphs K$ and K§ in the projective plane, and of Kf in the torus.
On the other hand, K-j does not embed in the Klein bottle, c One can also straightforwardly extend Euler's formula as follows:
Theorem 11.6. Let a cellular embedding of a nonempty graph G in £ has f faces. Then
\V(G)\ + f-\E(G)\=x(P) where (the Euler characteristic ofY.) is 2 — 2h for £ — Sh snd 2 — k forH — Mk ■
11.3   Embedding Obstructions, Minors
Similarly to algorithmic testing of planarity, embeddability in any other fixed surface can be tested in linear time by using the following strong result of Mohar:
Theorem 11.7. For every fixed surface £ there is a linear-time algorithm that either finds an embedding in £, or outputs some minimal obstruction to embeddability in E.
On the other hand, a related problem to determine the smallest surface where the given graph embeds is already MV-hard. c
Fact: Embeddability in a surface is preserved under taking subgraphs or even minors.
So, one would like to naturally generalize Kuratowski theorem to other surfaces... □
- This is always possible (Robertson and Seymour), but the lists of obstructions (forbidden minors) get very very large. In fact, such a complete obstruction list is known only in one case (Archdeacon) - the projective plane:
Embeddings vs. Graph minors
Besides planarity and the Four Colour theorem, what motivates study of graph embeddings on higher surfaces?
• Somehow surprisingly, even the whole deep Graph minors theory of Robertson and Seymour builds upon graphs embedded in surfaces, though the final result itself does not seem to relate to embedded graphs at all... □
To explain this finding, we introduce one of the most important partial results of the Graph minors theory.
Theorem 11.9. Let H be a nonplanar graph. Then every graph G excluding a minor isomorphic to H has a tree-decomposition of the following property:
- every bag induces a subgraph Gx ofG such that Gx is, up to a bounded number of "local exceptions", embeddable in a surface £ where H does not embed in.
11.4   Crossing Number of a Graph
Another generalization of planar graphs aims at allowing edges to "cross" each other in a controlled way.
This is based on the following definitions: c
Definition 11.10. Generalized drawing of a graph G into the plane
(see also Definition 8.1) maps the vertices of G into distinct points in the plane, and
the edges into simple arcs joining their endvertices. Moreover, □
- no three edges can cross each other in the same point, □
- each intersecting pair of edges transversally cross there, □
- and no edge can pass through other vertex except its ends.
Example 11.11. The following are valid generalized drawings in the plane. Are they optimal wrt. the number of pairwise edge crossings?
Not quite - the first two can be drawn better, with none and 1 crossings, respectively. On the other hand, the right-most drawing is optimal, c C
Definition: The crossing number of a graph G in the plane is the least number of pairwise edge crossings over all drawings of G in the plane. It is denoted by cr(G). c
Why are we interested in the graph crossing number problem?
Indeed, it has found applications e.g. in VLSI design (Leighton) and in graph visualization.
Example 11.12. What are the crossing numbers of the following two graphs?
It is 2 on the left and 3 on the right. C
After all, the crossing number problem appears to be unusually difficult...
Fact: Nobody knows for sure even the crossing numbers of complete and complete bipartite graphs!
On complexity of the crossing number problem
Theorem 11.13. It is NT'-complete to decide whether cr(G) < k for G and k on the input. The same holds if G is cubic 3-connected. □
Furthermore, even for a planar graph G and a pair of nonadjacent vertices u,v, it is MV-complete to decide cr(G + uv) < k for k on the input!
The last result raises a worrying question; what else can be easy about computing the crossing number?
In fact, determining the crossing number of a given graph is a hopelessly hard problem from the practical point of view, too. Though, at least one (yet totally impractical) general positive algorithmic result exists: □
Theorem 11.14. For a fixed k, it can be tested whether cr(G) < k in linear time. Besides that, only a few approximation algorithmic results exist.. .
11.5   A note on Planar Covers and Emulators
Definition: A graph H covers a graph G if there exists a locally-bijective graph homo-morphism t : V(H) —>• V(G), such that, for every vertex v e V(H), the neighbours of v in if are bijectively mapped onto the neighbours of t(i>) in G.
H
u3 Ul
t(u2) t(ui)
G
Proposition 11.15. If G embeds in the projective plane, then the universal covering map of the projective plane by the sphere "lifts" G into a planar double cover H ofG.
t(vi) = t(v2) = v
H
v2
G = K5
Negami's planar cover conjecture
Conjecture 11.16. A connected graph G has a cover by a finite planar graph if, and only if, G embeds in the projective plane, c
Regarding the (over) 20-years effort to solve this curious conjecture, the following steps have been gradually made by [Archdeacon, Fellows, Negami, Thomas, and the author]:
• The property of having a planar cover is preserved under taking subgr. / minors.□
• To prove Conjecture 11.16, it is enough to verify that none of the 32 connected forbidden minors from Theorem 11.8 has a finite planar cover, c
• The previous is quite easy for majority of those graphs.
• A few more specialized cases solved over the years, c
• Finally; if the graph ^1,2,2,2 had no finite planar cover, then Conjecture 11.16 would be true, c
• However, the best we know nowadays is that; there are at most 16 specific graphs (up to trivial modifications) for which Conjecture 11.16 might possibly fail.
Z
Planar emulators
Definition: A graph H emulates a graph G if there exists a locally-surjectivegraph ho-momorphism t : V(H) —>• V(G), such that, for every vertex v e ), the neighbours of v in if are surjectively mapped onto the neighbours of t(v) in G.
c2 h
□
Fact: Being a planar cover is a special case of being a planar emulator, c
Actually, where is any relevant difference between planar covers and planar emulators? How can the possibility of having "duplicate neighbours" help us in obtaining planar emulators (more edges make planarity harder!). . . ?
Planar emulator conjecture?
So, what is the relation between planar covers and planar emulators?
• Fellows conj. that any graph has a finite planar emulator iff it has such a cover.□
• Though the conjecture seemed quite natural and perhaps nobody questioned it, more that 20 years later Rieck and Yamashita disproved this conjecture by providing two rather unexpected planar emulators of nonprojective graphs (2008).
• Some more planar emulators of nonprojective graphs have been found by Chimani and the author (2009). And then.. . Klusáček (a student of MA010 in 2010) has found yet new and unexpected planar emulators, e.g.: