The theme of this work is graphic representation of planar and regular graphs of the degrees r = 0, 1, 2, 3, 4 and 5 in which are given the rules (algorithm) for their graphic representation based on their specific features.

At the end the notion of “spatial structures” and their relation to planar graphs is introduced. Graphic representations of all planar and regular graphs are given in the special sections at the end of the paper. The representations of all the graphs up to the degree r=4 are based on existing procedures known in the literature, while for the graphs degree r=5 had to be defined a specific algorithm.

**Regular and Planar Graphs**

Graph could be defined in various ways. One of the definitions connects graph to the notion of binary relations: Let X be non-empty set and q a binary relation within X. The ordered pair G=(X,q) is graph in which elements of the set X are called vertices and the elements of the set q are edges.

A specific property of the graph is a possibility to be presented on a plane where the vertices x1, x2, x3… xn are represented as points and edges as lines. When vertices x1 and x2 belong to a single edge q, then the point that marks vortex x1 is connected by a line with the point that represents vortex x2. This line, together with the points x1 and x2, is a graphic representation of the edge q. If x1 and x2 do not belong to the same edge, then they are not directly connected with a line.

Two graphs are isomorphic if there is biunivoque correspondence between the sets of their vertices in a way that maintains the same neighborhood relationships. On the Fig.1 three graphs are shown, each with four vertices and four edges. Graph 1a consists of one vortex of the third degree (r=3), two vertices of the second degree (r=2) and one vortex of the first degree (r=1), while in the graphs 1b and 1c all the vertices are of the same degree r=2.

Fig.1

The difference in the degrees of the vertices between two graphs is sufficient indicator that they are not isomorphic, which means that graph 1a is not isomorphic with any of the other two. On the other hand it is easy to show that graphs 1b and 1c are isomorphic, indicating that, in addition to equal numbers of vertices and edges, necessary condition for their isomorphism is the equal degrees of the corresponding vertices.

Fig.2

However, on the Fig.2 are shown two non-isomorphic graphs that have the same number of vertices and edges, each vortex being of the same degree r=3, thus indicating that these are not sufficient conditions for isomorphism. Obviously, establishing an isomorphism between two graphs is not a simple task and it is much easier identified through the matrix of neighborhoods.

We have already noticed that all the vertices in the graphs 1b and 1c are of the same degree (r=2) and all the vertices in the graphs 2a and 2b are also of the same degree (r=3). Graph in which all the vertices are of the same degree are regular graphs. Let d1, d2, d3,…,dn be the degrees of the vertices in a graph with m number of edges. Since each edge is defined with two vertices, the sum of degrees of all vertices corresponds to the double number of edges: d1+d2+d3+…+dn= 2m.

Theorem 1: Number of vertices with add degree (r=2n+1) in a finite graph is always even.

A graph is regular with degree r if d1=d2=d3=…=dn=r. Thus a regular graph with degree r has m=1/2 nr edges. Thus, graphs 1b and 1c are regular of the degree r=2 while 2a and 2b are regular with the degree r=3. These two graphs could be presented in a different way (Fig3).

Fig.3

We could notice that 3a can be presented on a plane where all the edges meet in the vertices only, while graph 3b can not be presented this way. Here there is at least one (crossing) point between two edges that doesn’t belong/correspond to the set of vertices. Based on this property all the graphs could be grouped in two classes: planar and non-planar graphs. In planar graphs all the edges meet only in the vertices. This graph divides a plane in finite enclosed parts and one that is infinite. This property of planar graphs is a bases for the well known Euler’s theorem.

Theorem 2: Connected planar graph with n number of vertices and m edges divides a plane in f=m-n+2 areas.

Proof is inductive based on the number of edges. Minimal number of edges in the graph with n vertices is m=n-1. In this case graph is represented as a tree which doesn’t define any encircled area (contour) f=1, meaning that the Euler’s theorem is valid for m=n-1.

If a graph G has m edges and if f is a number of areas G (m>n-1) then graph has at least one contour. Lets assume that Euler’s formula is valid for the graphs with m-1 edges. If an edge belongs to a contour in a graph G it is also a dividing line between two areas. If we remove this edge from the graph we will have graph G1 with m-1 edges and f-1 areas, since the number of edges and areas is reduced for 1. In that case f-1= (m-1)-n+2, meaning that in a graph with m edges, number of areas is f=m-n+2.

**Representation of graphs on a plane**

As it was already shown a certain graph could be represented in various ways. This is why it would be useful to define some rules based on the graph’s properties that would determine its representation.

Fig.5

For the planar graphs the first rule is that this property (planarity) is visible. In Fig.5 is shown a certain planar graph in its planar (5b) and non-planar (5a) representations. We will always represent this graph in its planar version (5b). Second rule is based on the length of the longest contour. A graph will be represented in the way that its longest contour is its outer line, but first satisfying the rule of planar representation. This is why, in spite of the longer outer contour, the 5a version is not acceptable.

Fig.6

On the Fig.6 is a planar graph with n=6 and r=3 in two ways. Since both versions are satisfying the condition of planar representation we will accept version with the longer outer contour (Fig.6b).The third rule for representing planar graphs will be symmetry. Between two representations of the same graph (Fig.7) we will select 7b.

Fig.7

–**Graph of the degree r=0** consists only of one vortex and has no edges (q=0).

–**Graph of the degree r=1** is a regular and planar graph consisting of two vertices and one edge (Fig.8). This is the only regular graph of the degree r=1. This graph divides the plane in f=m-n+2=1 parts.

Fig.8

–**Graph of the degree r=2** is called a contour. Minimal graph of this degree consists of three vertices (n=3) and three edges q=3 (Fig.9).

Fig.9

Beginning with this simplest case, by adding one vortex and one edge at the time, it is possible to generate graphs with 4, 5, 6,.., n vertices(Fig. 10).

Fig.10

Any two graphs of this type with the same number of edges are isomorphic. In other words, for a certain number of vertices there is only one corresponding graph of this type. In that sense, graphs 1b and 1c are isomorphic (being regular, with four vertices, each with degree r=2). All graphs of this kind divide the plane in two areas regardless of the number of vertices (f=m-n +2=2) and each has its planar representation.

–**Graphs of the degree r=3** (cubic graphs) have both planar and non-planar cases and it is more difficult to distinguish them, and for a certain number of nods n there are several non-isomorphic graphs. Of all regular graphs with r=3 here are presented all the planar graphs with number of vertices n=4, 6, 8, 10, 12 and 14[2]. Relationships between the number of all graphs r=3 and planar graphs for a given number of vertices n is illustrated in Fig.11. We could notice that with increasing the number of vertices decreases the proportional number of planar graphs for the given n.

Fig.11

In the Fig.12 is presented the same planar graph in two different ways. We could notice that in both cases the number of areas is the same-seven that seems to be sufficient to identify isomorphic graphs. However, two regular graphs of the same degree r=3, same number of vertices (n=12) and the same number of areas (cells) f=8 are not isomorphic.

Fig.12

In fact, two planar graphs are isomorphic only if all the corresponding areas (cells) in both graphs have the same neighboring areas (cells). We could also notice that two representations of the same graph could define two different divisions of the plane (Fig.13, 14).

Fig. 13

Fig.14

Based on the graphic presentation of a planar graph G it is possible to define its (geometric) dual, a graph G* which vertices correspond to the cells of the graph G. Here to each cell in G, including infinite, correspond one vortex in G*. Thus, two neighboring cells in G have corresponding neighboring vertices in G*, which indicates that the edges in G* are defined by the neighborhoods of cells in G. In the fig.15 are presented two graphs that are dual to those shown in Fig.13.

Fig.15

It is now possible to define a condition for two graphs being isomorphic by comparing the neighborhoods of corresponding vertices of their duals. Two planar graphs G1 and G2 are isomorphic if all corresponding vertices in G1* and G2* have the same neighborhoods, meaning that for a certain vortex of degree d in G1* there is a corresponding vortex of same degree in G2* so that both vertices have the neighborhoods with same configuration.

–**Graphs of the degree r=4 **

Regular and planar graphs of the degree r=4 are presented here up to the number of vertices n=12. The minimal planar and regular graph of the degree r=4 has six vertices and all its cells are triangular (Fig.20).

Fig.20.

There are regular and planar graphs of the degree r=4 with n=6, 8, 9, 10, 11, 12…vertices[1, 4] except for the number n=7 for which there is no such graph. Examples of these graphs with various number of vertices and how to enlarge them are given in Fig. 21, 22, 23, 24 and 25.

Fig. 21-25

–**Graphs of the degree r=5**

Following the methods for enlargements of the graphs r=4 it is possible to establish similar procedure for generating regular and planar graphs of the degree r=5 that is based on its minimal case (Fig.26) which consists of 12 vertices and all its cells are triangular.

Fig.26

In the Fig. 27-31 are given some methods for enlargement of the minimal graph while maintaining its basic properties. Although it is uncertain if all these operations are complete and independent we could assume that there is a finite set of independent operations that could generate all the regular and planar graphs of the degree r=5 based on the minimal graph shown in Fig.26.

Fig.27-31

–**Planar graphs and spatial structures**

If there is a finite set X=x1,x2,x3,x4,x5, and if there are between its elements defined neighborhood relationships in this way: x1qx2, x1qx4, x2qx3, x2qx4, x3qx4, x4qx5 that can be represented with the graph shown in Fig32.

Fig. 32

Let assume that the elements of the set X, instead of vertices (dots), are represented as finite parts of the plane with defined shape and size as shown in Fig 33. Now the given relationships between the elements of this set could be presented as shown in Fig. 34.

Fig.33 Fig.34

A structure of a finite number of elements which are finite parts of the plane with defined neighborhood relationships between its elements will be named ‘’the spatial structure’’. However, with the same set shown in Fig.33 the same neighborhood relationships could presented in different ways (Fig35).

Fig.35

In order to avoid this multiplicity, we will choose the square-like shape in Fig.34 to be the standard shape for the spatial structure (Fig36).

Fig. 36 Fig. 37

Let compare the neighborhood relationships between the elements of the spatial strictures in Fig. 37.

We will notice that they all correspond to the same graph shown in Fig.32, which indicates that all these spatial structures are isomorphic. While their neighborhoods are the same, the elements of these structures differ in their sizes, shapes and positions they occupy within a structure, indicating that the sets which are defining these structures are not the same.

Fig. 38

A set that defines structure 37a is shown in Fig.33, while the sets defining the other three structures are shown in Fig.38. With different sets we could define structures that are isomorphic, and with the same set we could define structures that are not isomorphic. Thus with the sets in Fig.33 and in Fig.38d we could define non-isomorphic structures as shown in Fig. 39, together with the corresponding graphs.

Fig.39

If we observe element x1 we will notice that it occupies different parts in the spatial structures I and II, as if the element x1 has changed the position in relation to the structure as a whole. We could assume that the change of the position of x1 is determined by the change/transformation of the structure I into structure II. However, we could notice that element x1 in other two structures III and IV has unchanged position in relation to the structure as a whole. We could conclude that the position of an element within a spatial structure does not depend of its neighborhood relationships. In other words, in addition to the size, shape and neighborhoods of an element, within a spatial structure it acquires another property, that is its position in relation to the entire structure. This property of an element is characteristic for the spatial structure. Also, unlike the graph, spatial structure covers the plane since it consists of the elements with finite size. Some spatial structures corresponding to certain planar and regular graphs are presented in the appendix VIII.

***********

Literature:

1. А.М.Бараев, И.А.Фараджев:

Построение и исследование на ЭВМ однородных и однородных двудольных графов,

Наука, Москва 1978.

A.M.Baraev, I.A.Faradzhev:

Construction and investigation of homogeneous and homogeneous bipartite graphs on computers

Science, Moscow 1978.

2. F.C.Bussemaker, S.Cobeljić, , D.M.Cvetković, J.J.Seidel:

Computer investigation of cubic graphs, Technological University Eindhoven,

Department of mathematics 1976

3. D.Cvetković, M.Milić:

Teorija grafova i njene primene, Univerzitet u Beogradu, Beograd 1977

Graph Theory and its applications, Belgrade University, Belgrade 1977

4. P.Manca:

Generating All Planar Graphs Regular of Degree Four, Journal of Graph Theory, No.4, 1979

5. C.Marshall:

Applied Graph Theory, Wiley-Interscience, New York, 1971

*) This work was submitted as a diploma paper at the Belgrade University in May 1980.

Goran Đorđević

**Appendix I**

Here are presented 14 planar and regular graphs of the degree r=3 with number of vertices n=4,6,8 and 10, according to these rules:

-graph has to be visibly planar

-outer contour is a the longest cell in the graph

-symmetry

**Appendix II**

Here are presented 32 planar and regular graphs of the degree r=3 with number of vertices n=12 according to these rules:

-graph has to be visibly planar

-outer contour is a the longest cell in the graph

-symmetry

**Appendix III**

Here are presented 133 planar and regular graphs of the degree r=3 with number of vertices n=14 according to these rules:

-graph has to be visibly planar

-outer contour is a the longest cell in the graph

-symmetry

**Appendix IV**

Here are presented different approaches in generating planar and regular graphs of the degree r=3. It is also shown that some of these graphs of the degree r=3 could be products of the sum of two planar and regular graphs (G1+G2) of the degrees r=2(G1) and r=1(G2).

**Appendix V**

Here are presented 20 planar and regular graphs of the degree r=4 and number of vertices n=6, 8, 9, 10, 11

and 12, according to these rules:

-graph has to be visibly planar

-outer contour is a the longest cell in the graph

-symmetry

**Appendix VI**

Here are introduced some examples of generating planar and regular graphs of the degree r=5 and their graphic representations for the number of vertices n=12,16, 20, 22, 24 and 30, according to these rules:

-graph has to be visibly planar

-outer contour is a the longest cell in the graph

-symmetry

**Appendix VII**

Here are some examples of generating planar and regular graphs of the degrees r=2, 3, 4 and 5.

We could notice that graphs of various degrees represented in this way show certain visual similarities.

**Appendix VIII**

Here are presented some simple graphs r=0, 1, 2, 3 and corresponding spatial structures including those corresponding to the cubic graphs with number of vertices n=10.