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 adges in a drawing to cross each other (but not too often). We briefly outline these directions now.. . c
Brief outline of this lecture
• Higher surfaces, and graph embeddings on them.
• Properties of embeddable graphs on surfaces.
• Graph crossing number, crossing minimization.
• Curiosity - the planar cover and planar emulator problems.
V
Petr Hliněný,  Fl MU Brno
FI:MA010: Drawings of Graphs
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 □
- S0 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, 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.
Petr Hliněný,  FI MU Brno_2_FI: MA010: Drawings of Graphs
□
Notation: S1 is a torus (see on the left) - the surface of a donut.
Ni is a projective plane; if an open disc is removed from Ni, then we get a Mobius b. N2 is the Klein bottle (right); obtained by glueing two Mobius bands together.
So and Sh are orientable surfaces, while all Nk 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 E is obtained from the sphere by adding k > 2 crosscaps and h handles, then E is homeomorphic to the one obtained by adding k — 2 crosscaps and h + 1 handles.
Si
M 2c
V
Petr Hliněný,  FI MU Brno
FI:MA010: Drawings of Graphs
Convention 11.3. As in 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.
M ]
S i
Petr Hliněný,  FI MU Brno
FI:MA010: Drawings of Graphs
11.2   Graph Embeddings in Surfaces
Definition 11.4. (cf. Definition 8.1) An embedding of a graph G on the surface X is a mapping which takes the vertices of G onto distinct points of X, and the edges of G onto simple arcs in X 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 X is cellular if each its face (without boundary) is homeomorphic to an open disc. c
Fact: A cellular embedding of 2-connected G is uniquely determined by its facial cycles, and this embedding also defines the underlying surface X up to homeomorphism.
In other words, X is "glued together" from the facial discs along shared edges. c
Proposition 11.5. 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.
V
Petr Hliněný,  Fl MU Brno
FI:MA010: Drawings of Graphs
Embedded graphs
Recall that the complete graph K5 is not planar.
Proposition 11.6. There exist embeddings of the complete graphs K5 and K6 in the
projective plane, and of K7 in the torus.
K5
K6
K7
On the other hand, K7 does not embed in the Klein bottle. □
One can also straightforwardly extend Euler's formula as follows:
Theorem 11.7. Let a cellular embedding of a nonempty graph G in £ has f faces. Then
|V(G)| + f -|E(G)| = x(£) where x(£) (the Euler characteristic of £) is 2 — 2h for £ = Sh and 2 — k for £ = Nk.
Petr Hliněný,  FI MU Brno_6_FI: MA010: Drawings of Graphs
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.8. For every fixed surface E there is a linear-time algorithm that either finds an embedding in E, or outputs some minimal obstruction to embeddability in E.c
The related problem to determine a smallest surface where the given graph embeds is already NP-hard.
Notice that embeddability in a surface is preserved under taking subgraphs or even minors. Therefore, one would like to generalize the Kuratowski theorem to other surfaces. .. c
This is possible, but the lists of obstructions (forbidden minors) get very very large. In fact, such a complete list is known only in one case (Archdeacon):
V
Petr Hliněný,  Fl MU Brno
FI:MA010: Drawings of Graphs
Embeddings vs. Graph minors
Quite surprisingly, also 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.. . c
To explain this fact, we introduce one of the most important partial results of this theory.
Theorem 11.10. 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 of G such that GX is, up to a bounded number of "local exceptions", embeddable in a surface E where H does not embed in.
V
Petr Hliněný,  Fl MU Brno
FI:MA010: Drawings of Graphs
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 (another generalization of Definition 8.1):
A drawing of a graph G in the plane 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 and no edge can pass through other vertex except its ends. c
Example 11.11. The following are valid drawings in the plane. Are the numbers of their edge crossings optimal?
□
V
Petr Hiineny,  FI MU Brr
FI: MA010: Drawings of Graphs
Definition 11.12. The crossing number of a graph G in the plane
is the least number of pairwise edge crossings over all proper drawings of G in the
plane. It is denoted by cr(G). c
Example 11.13. What are the crossing numbers of the following two graphs?
Fact: Nobody knows for sure even the crossing numbers of complete and complete bipartite graphs!
Petr Hlineny,  FI MU Brr
FI: MA010: Drawings of Graphs
On hardness of the crossing number problem
In fact, determining the crossing number of a given graph is a hopelessly hard problem.
• This problem is NP-complete, even for cubic 3-connected graphs. c
• Though, for any fixed k, it can be tested in polynomial time whether cr(G) < k. Unfortunately, this is a totally impractical algorithm. c
• Nowadays, an involved b&b practical computing approach to the crossing number exists, see [Chimani et al.]. This one can, surprisingly, handle "real-world" graphs of < 100 vertices. c
• Still, Cabello and Mohar proved in 2010 that even for a planar graph G and a pair of vertices u, v G V(G), determining cr(G + uv) is NP-complete!
The last result raises a worrying question; what else can be easy about computing the crossing number?
Petr Hiineny,  FI MU Brr
FI: MA010: Drawings of Graphs
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 G V(H), the neighbours of v in H are bijectively mapped onto the neighbours of t(v) in G.
H
u3
U\
T (U3) T (U2)
t(ui) Gr-
Proposition 11.14. 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 of G.
t (vi) = T (V2 ) = v
H
VV2
Vl
Petr Hlin
FI MU Brn<
G = K5 FI: MA010: Drawings of Graphs
Negami's planar cover conjecture
Conjecture 11.15. 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.c
• To prove Conjecture 11.15, it is enough to verify that none of the 32 connected forbidden minors from Theorem 11.9 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 K\t2,2,2 had no finite planar cover, then Conjecture 11.15 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.15 might possibly fail.
V
Petr Hlineny,  FI MU Brr
FI: MA010: Drawings of Graphs
On planar emulators
A small modification of the cover concept was independently suggested by Fellows.
Definition: A graph H emulates a graph G if there exists a locally-surjective graph ho-momorphism t : V(H) — V(G), such that, for every vertex v G V(H), the neighbours of v in H are surjectively mapped onto the neighbours of t(v) in G.
C2
b3 ^
H c3
b2
t 0.2 ^ C1
bi
0b\
G
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!). . . ?
Petr Hlín
ny.
FI MU Brn
FI: MA010: Drawings of Graphs
b
a
c
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 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).
• More planar emulators of nonprojective graphs have been found by Chimani and the author (2009). And then. .. □
• In 2010, a student of MA010 (one like you) has found yet a new one:
V
t 4
i 2
K7 - C4
J
Petr Hlmeny,  hi MU tin
Fl: MA010: Drawings of Graphs