Lecture
The genus of a graph (English: genus) g(G) denotes the smallest number of handles that must be added to the sphere so that the graph can be embedded on this surface without crossings.
For planar graphs g = 0,
for the graph K5 g = 1.
If we want the graph shown in the figure to be without crossings, 1 handle is needed.
In the design of transport networks, the problem arises of embedding a graph in the plane, but not every graph is planar. If a network is a non-planar graph, then one has to build intersections or construct bridges. Building bridges costs more than building an ordinary road, and intersections increase travel time. Therefore, before starting the work, it is useful to compute the genus, thickness, coarseness and crossing number of the graph.
The graphs K5, K3,3, K4,4, K7 - are toroidal graphs, that is, they have genus g = 1.
For any surface there is a finite set of graphs
that characterizes it, that is, those graphs which
cannot be embedded on that surface.
Generalization of Euler's THEOREM to graphs of genus g.
Given G(p, q) having f faces, the following holds for it: p + f - q = 2 - 2g
COROLLARY 1. For any connected graph with p vertices and q edges, where p 4, the following holds:
g = ] (q - 3p + 1)/6 [
COROLLARY 2. For complete graphs the following holds
g(Kp) = ] (p - 3)(p - 4)/12 [
The thickness of a graph (English: thickness) - is the minimum number of planar subgraphs of the graph G such that their union gives the graph G.
It is known that the thickness of complete graphs equals
Since in a planar graph q = 3p - 6, then 
Since in a complete graph q = p(p - 1)/2, then 
By definition, if there exists a set of k planar graphs having the same vertex set, whose union gives the graph G , then the thickness of the graph G does not exceed k . Thus, a planar graph has thickness 1 . Graphs with thickness 2 are called biplanar graphs. The concept of thickness arose in Frank Harary's conjecture: any graph with 9 vertices, either itself or its complement, is non-planar. This conjecture is true, since the complete graph K9 is not biplanar.
The thickness of the complete graph θ(Kn)=⌊n+76⌋ but the thickness of the graphs K9 and K10 equals 3 .
THEOREM (on the degrees of vertices in a planar graph).
In any planar graph there exists a vertex whose degree is at most 5.
Proof:
Suppose there is no such vertex, then
the degree of each vertex is at least 6, and therefore,
6p <= 2q, that is q >=3p.
But for planar graphs
q <=3p - 6.
We have obtained a contradiction.
| Definition: |
| Coarseness (English: coarseness) ξ of the graph G is defined as the largest number of non-planar graphs in G that are edge-disjoint. |
The formulas for computing the coarseness of a complete graph are not as simple as for other topological invariants.
The coarseness of a planar graph equals 0 , since a planar graph cannot contain a non-planar subgraph.
Coarseness ξ(K5)=1 and ξ(K3,3)=1 , since K5 and K3,3 contain only one non-planar subgraph.
| Definition: |
| The crossing number (English: crossing number) ν of the graph G is defined as the smallest number of edge crossings that occur when embedding G in the plane. |
The exact value of the crossing number is not known; only an upper bound has been established.
The crossing number of the complete graph ν(Kn)⩽14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋
The crossing number of the complete bipartite graph ν(Kn,m)⩽⌊n2⌋⌊n−12⌋⌊m2⌋⌊m−12⌋
An embedding of a planar graph can be done using the gamma algorithm, where the crossing number will equal 00.
| Definition: |
| If a graph can be embedded on the torus, then it is toroidal. |
A toroidal graph G has genus γ(G)⩽1
Comments