# Intuitionistic Fuzzy Planar Graphs

Authors: Noura Alshehri; Muhammad Akram
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

Graph theory has numerous applications in modern sciences and technology. Atanassov introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets. Intuitionistic fuzzy set has shown advantages in handling vagueness and uncertainty compared to fuzzy set. In this paper, we apply the concept of intuitionistic fuzzy sets to multigraphs, planar graphs, and dual graphs. We introduce the notions of intuitionistic fuzzy multigraphs, intuitionistic fuzzy planar graphs, and intuitionistic fuzzy dual graphs and investigate some of their interesting properties. We also study isomorphism between intuitionistic fuzzy planar graphs.


---

## Body

## 1. Introduction

Graph theory is now a very important research area due to its wide applications. There are many practical applications with a graph structure in which crossing between edges is nuisance including design problems for circuits, subways, and utility lines. Crossing of two connections normally means that the communication lines must be run at different heights. This is not a big issue for electrical wires, but it creates extra expenses for some types of lines. Circuits, in particular, are easier to manufacture if their connections can be constructed in fewer layers. These applications are designed by the concept of planar graphs. Circuits, where crossing of lines is necessary, can not be represented by planar graphs. Numerous computational challenges can be solved by means of cuts of planar graph. In the city planning, subway tunnels, pipelines, and metro lines are essential in twenty first century. Due to crossing, there is a chance for an accident. Also, the cost of crossing of routes in underground is high. But underground routes reduce the traffic jam. In a city planning, routes without crossing are perfect for safety. But due to lack of space, crossing of such lines is allowed. It is easy to observe that the crossing between one congested and one noncongested route is better than the crossing between two congested routes. The term “congested” has no definite meaning. We generally use “congested,” “very congested,” “highly congested” routes, and so forth. These terms are called linguistic terms and they have some membership values. A congested route may be referred to as strong route and low congested route may be called weak route. Thus crossing between strong route and weak route is more safe than the crossing between two strong routes. That is, crossing between strong route and weak route may be allowed in city planning with certain amount of safety. The terms strong route and weak route lead to strong edge and weak edge of a fuzzy graph, respectively. And the permission of crossing between strong and weak edges leads to the concept of fuzzy planar graph [1–3].Presently, science and technology is featured with complex processes and phenomena for which complete information are not always available. For such cases, mathematical models are developed to handle various types of systems containing elements of uncertainty. A large number of these models are based on an extension of the ordinary set theory, namely, fuzzy sets. The notion of fuzzy sets was introduced by Zadeh [4] as a method of representing uncertainty and vagueness. Since then, the theory of fuzzy sets has become a vigorous area of research in different disciplines. In 1983, Atanassov [5] introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets. Atanassov added in the definition of fuzzy set a new component which determines the degree of nonmembership. Fuzzy sets give the degree of membership of an element in a given set (the nonmembership of degree equals one minus the degree of membership), while intuitionistic fuzzy sets give both a degree of membership and a degree of nonmembership, which are more or less independent from each other; the only requirement is that the sum of these two degrees is not greater than 1. Intuitionistic fuzzy sets are higher order fuzzy sets. Application of higher order fuzzy sets makes the solution-procedure more complex, but if the complexity on computation-time, computation-volume or memory-space are not the matter of concern then a better result could be achieved.Fuzzy graph theory is finding an increasing number of applications in modeling real time systems where the level of information inherent in the system varies with different levels of precision. Fuzzy models are becoming useful because of their aim in reducing the differences between the traditional numerical models used in engineering and sciences and the symbolic models used in expert systems. Kauffman’s initial definition of a fuzzy graph [6] was based on Zadeh’s fuzzy relations [7]. Rosenfeld [8] introduced the fuzzy analogue of several basic graph-theoretic concepts and Bhattacharya [9] gave some remarks on fuzzy graphs. Mordeson and Nair [10] defined the concept of complement of fuzzy graph and studied some operations on fuzzy graphs. In [11], the definition of complement of a fuzzy graph was modified so that the complement of the complement is the original fuzzy graph, which agrees with the crisp graph case. Shannon and Atanassov [12] introduced the concept of intuitionistic fuzzy relations and intuitionistic fuzzy graphs and investigated some of their properties in [13]. Parvathi et al. defined operations on intuitionistic fuzzy graphs in [14]. Akram et al. [15–18] introduced many new concepts including intuitionistic fuzzy hypergraphs, strong intuitionistic fuzzy graphs, intuitionistic fuzzy cycles, and intuitionistic fuzzy trees. Abdul-Jabbar et al. [1] introduced the concept of a fuzzy dual graph and discussed some of its interesting properties. Recently, Pal et al. [2] and Samanta et al. [3] introduced and investigated the concept of fuzzy planar graphs and studied several properties. In this paper, we apply the concept of intuitionistic fuzzy sets to multigraphs, planar graphs, and dual graphs. We introduce the notions of intuitionistic fuzzy multigraphs, intuitionistic fuzzy planar graphs, and intuitionistic fuzzy dual graphs and investigate some of their interesting properties. We also study isomorphism between intuitionistic fuzzy planar graphs. We have used standard definitions and terminologies in this paper. For other notations, terminologies, and applications not mentioned in the paper, the readers are referred to [8, 10, 14, 19–27].


## 2. Preliminaries

In this section, we review some elementary concepts whose understanding is necessary for full benefit from this paper.By agraph we mean a pair G*=(V,E), where V is the set and E is a relation on V. The elements of V are vertices of G* and the elements of E are edges of G*. We write xy∈E to mean (x,y)∈E, and if e=xy∈E, we say x and y areadjacent. Formally, given a graph G*=(V,E), two vertices x,y∈V are said to beneighbors, or adjacent nodes, if xy∈E. The number of vertices, the cardinality of V, is called theorder of graph and denoted by |V|. The number of edges, the cardinality of E, is called thesize of graphand denoted by |E|. Amultigraph is a graph that may contain multiple edges between any two vertices, but it does not contain any self-loops. A graph can be drawn in many different ways. A graph may or may not be drawn on a plane without crossing of edges. A drawing of a geometric representation of a graph on any surface such that no edges intersect is calledembedding. A graph G* isplanar if it can be drawn in the plane with its edges only intersecting at vertices of G*. A crisp graph is callednonplanar graph if there is at least one crossing between the edges for all possible geometrical representations of the graph. A planar graph with cycles divides the plane into a set of regions are calledfaces. The length of a face in a plane graph G* is the total length of the closed walk(s) in G* bounding the face. The portion of the plane lying outside a graph embedded in a plane is infinite region. The dual graph of a plane graph G* is a graph that has a vertex corresponding to each face of G* and an edge joining two neighboring faces for each edge in G*. The term “dual” is used because this property is symmetric, meaning that if H* is a dual of G*, then G* is a dual of H* (if G* is connected).LetX be a nonempty set. Afuzzy set [4] A drawn from X is defined as A={〈x:μA(x)〉:x∈X}, where μ:X→[0,1] is the membership function of the fuzzy set A. Afuzzy binary relation [7] on X is a fuzzy subset μ on X×X. By a fuzzy relation, we mean a fuzzy binary relation given by μ:X×X→[0,1]. Afuzzy graph [6] G=(V,σ,μ) is a nonempty set V together with a pair of functions σ:V→[0,1] and μ:V×V→[0,1] such that, for all x,y∈V, μ(x,y)≤min⁡(σ(x),σ(y)), where σ(x) and μ(x,y) represent the membership values of the vertex x and of the edge (x,y) in G, respectively. A loop at a vertex x in a fuzzy graph is represented by μ(x,x)≠0. An edge is nontrivial if μ(x,y)≠0. Let G be a fuzzy graph and, for a certain geometric representation, the graph has only one crossing between two fuzzy edges ((w,x),μ(w,x)) and ((y,z),μ(y,z)). If μ(w,x)=1 and μ(y,z)=0, then we say that the fuzzy graph has no crossing. Similarly, if μ(w,x) has value near to 1 and μ(y,z) has value near to 0, the crossing will not be important for the planarity. If μ(y,z) has value near to 1 and μ(w,x) has value near to 1, then the crossing becomes very important for the planarity.LetX be a nonempty set. Afuzzy multiset [28] A drawn from X is characterized by a function, “count membership” of A denoted by CMA such that CMA:X→Q, where Q is the set of all crisp multisets drawn from the unit interval [0,1]. Then for any x∈X, the value CMA(x) is a crisp multiset drawn from [0,1]. For each x∈X, the membership sequence is defined as the decreasingly ordered sequence of elements in CMA(x). It is denoted by (μA1(x),μA2(x),μA3(x),…,μAp(x)) where μA1(x)≥μA2(x)≥μA3(x)≥⋯≥μAp(x).LetV be a nonempty set and σ:V→[0,1] a mapping and let μ={(x,y),μ(x,y)j,j=1,2,…,pxy∣(x,y)∈V×V} be a fuzzy multiset of V×V such that μ(x,y)j≤min⁡{σ(x),σ(y)} for all j=1,2,…,pxy, where pxy=max⁡{j∣μ(x,y)j≠0}. Then G=(V,σ,μ) is denoted asfuzzy multigraph [2] where σ(x) and μ(x,y)j represent the membership value of the vertex x and the membership value of the edge (x,y) in G, respectively. In 1983, Atanassov [5] introduced the concept of intuitionistic fuzzy sets as a generalization of fuzzy sets [4]. An intuitionistic fuzzy set (IFS, for short) on a universe X is an object of the form
(1)A={〈x,μA(x),νA(x)〉∣x∈X},
where μA(x)(∈[0,1]) is called degree of membership of x in A and νA(x)(∈[0,1]) is called degree of nonmembership of x in A, and μA, νA satisfies the following condition for all x∈X, μA(x)+νA(x)≤1. An intuitionistic fuzzy relation R=(μR(x,y),νR(x,y)) in a universe X×Y(R(X→Y), for short) is an intuitionistic fuzzy set of the form
(2)R={〈(x,y),μR(x,y),νR(x,y)〉∣(x,y)∈X×Y},
where μR:X×Y→[0,1] and νR:X×Y→[0,1]. The intuitionistic fuzzy relation R satisfies μR(x,y)+νR(x,y)≤1 for all x,y∈X. Anintuitionistic fuzzy graph is a pair G=(A,B) where A=〈V,μA,νA〉 is an intuitionistic fuzzy set in V and B=〈V×V,μB,νB〉 is an intuitionistic fuzzy relation on V such that
(3)μB(xy)≤min⁡(μA(x),μA(y)),(4)νB(xy)≤max⁡(νA(x),νA(y))
such that 0≤μB(xy)+νB(xy)≤1 for all x,y∈V.LetX be a nonempty set. Anintuitionistic fuzzy multiset (IFMS) [29] A drawn from X is characterized by two functions: “count membership” of A (CMA) and “count nonmembership” of A (CNA) given by CMA:X→Q and CNA:X→Q where Q is the set of all crisp multisets drawn from the unit interval [0,1] such that, for each x∈X, the membership sequence is defined as a decreasingly ordered sequence of elements in CMA(x) which is denoted by (μA1(x),μA2(x),μA3(x),…,μAp(x)) where μA1(x)≥μA2(x)≥μA3(x)≥⋯≥μAp(x) and the corresponding nonmembership sequence will be denoted by (νA1(x),νA2(x),νA3(x),…,νAp(x)) such that μAi(x)+νAi(x)≤1 for all x∈X and i=1,2,…,p. An IFMS A is denoted by
(5){〈x:(μA1(x),μA2(x),μA3(x),…,μAp(x)),000(νA1(x),νA2(x),νA3(x),…,νAp(x))〉:x∈X}.We arrange the membership sequence in decreasing order but the corresponding nonmembership sequence may not be in decreasing or increasing order.


## 3. Intuitionistic Fuzzy Planar Graphs

We first introduce the notion of an intuitionistic fuzzy multigraph using the concept of an intuitionistic fuzzy multiset.Definition 1.
LetA=(μA,νA) be an intuitionistic fuzzy set on V and let
(6)B={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V}
be an intuitionistic fuzzy multiset of V×V such that
(7)μB(xy)i≤min⁡{μA(x),μA(y)},νB(xy)i≤max⁡{νA(x),νA(y)}
for all i=1,2,…,m. Then G is called anintuitionistic fuzzy multigraph.Note that there may be more than one edge between the verticesx and y. μB(xy)i, νB(xy)i represent the membership value and nonmembership value of the edge xy in G, respectively. m denotes the number of edges between the vertices. In intuitionistic fuzzy multigraph G, B is said to be intuitionistic fuzzy multiedge set.Example 2.
Consider a multigraphG*=(V,E) such that V={a,b,c,d}, E={ab,ab,ab,bc,bd}. Let A=(μA,νA) be an intuitionistic fuzzy set of V and let B=(μB,νB) be an intuitionistic fuzzy multiedge set of V×V defined by Table 1 and Figure 1.Table 1
(a)
a
b
c
d
μ
A
0.5
0.4
0.5
0.4
ν
A
0.3
0.4
0.3
0.4
(b)
a
b
a
b
a
b
b
c
b
d
μ
B
0.2
0.1
0.2
0.3
0.1
ν
B
0.2
0
0.2
0.3
0.2Figure 1
Intuitionistic fuzzy multigraph.By routine computations, it is easy to see from Figure1 that it is an intuitionistic fuzzy multigraph.Definition 3.
LetB={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V} be an intuitionistic fuzzy multiedge set in intuitionistic fuzzy multigraph G. The degree of a vertex x∈V is denoted by deg⁡(x) and is defined by deg⁡(x)=(∑i=1mμB(xy)i,∑i=1mνB(xy)i) for all y∈V.Example 4.
In Example2, degrees of the vertices a,b,c,d are deg⁡(a)=(0.5,0.4), deg⁡(b)=(0.9,0.9), deg⁡(c)=(0.3,0.3), and deg⁡(d)=(0.1,0.2).Definition 5.
LetB={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V} be an intuitionistic fuzzy multiedge set in intuitionistic fuzzy multigraph G. A multiedge xy of G isstrong if (1/2)min⁡{μA(x),μA(y)}≤μB(xy)i, (1/2)max⁡{νA(x),νA(y)}≤νB(xy)i, for all i=1,2,…,m.Definition 6.
LetB={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V} be an intuitionistic fuzzy multiedge set in intuitionistic fuzzy multigraph G. An intuitionistic fuzzy multigraph G iscomplete if min⁡{μA(x),μA(y)}=μB(xy)i, max⁡{νA(x),νA(y)}=νB(xy)i, for all i=1,2,…,m and for all x,y∈V.Example 7.
Consider an intuitionistic fuzzy multigraphG as shown in Figure 2.Figure 2
Intuitionistic fuzzy complete multigraph.By routine computations, it is easy to see from Figure2 that it is an intuitionistic fuzzy complete multigraph.Definition 8.
Strength of the intuitionistic fuzzy edgeab can be measured by the value
(8)Iab=(Mab,Nab)=(μB(ab)imin⁡(μA(a),μA(b)),νB(ab)imax⁡(νA(a),νA(b))).Definition 9.
LetG be an intuitionistic fuzzy multigraph. An edge ab is said to beintuitionistic fuzzy strong if Mab≥0.5 or Nab≤0.5, otherwise weak.Definition 10.
LetG be an intuitionistic fuzzy multigraph and let B contain two edges (ab,μB(ab)i,νB(ab)i) and (cd,μB(cd)j,νB(cd)j) which are intersected at a point P, where i and j are fixed integers. We define the intersecting value at the point P by
(9)IP=(MP,NP)=(Mab+Mcd2,Nab+Ncd2).If the number of points of intersections in an intuitionistic fuzzy multigraph increases, planarity decreases. Thus for intuitionistic fuzzy multigraph,IP is inversely proportional to the planarity. We now introduce the concept of an intuitionistic fuzzy planar graph.Definition 11.
LetG be an intuitionistic fuzzy multigraph and let P1,P2,…,Pz be the points of intersections between the edges for a certain geometrical representation; G is said to be an intuitionistic fuzzy planar graph with intuitionistic fuzzy planarity value f=(fM,fN), where
(10)f=(fM,fN)=(11+{MP1+MP2+⋯+MPz},000011+{NP1+NP2+⋯+NPz}).Clearly,f=(fM,fN) is bounded and 0<Mf≤1; Nf is 0<Nf≤1. If there is no point of intersection for a certain geometrical representation of an intuitionistic fuzzy planar graph, then its intuitionistic fuzzy planarity value is (1,1). In this case, the underlying crisp graph of this intuitionistic fuzzy graph is the crisp planar graph. If fM decreases and fN increases, then the number of points of intersection between the edges increases and decreases, respectively, and the nature of planarity decreases and decreases, respectively. We conclude that every intuitionistic fuzzy graph is an intuitionistic fuzzy planar graph with certain intuitionistic fuzzy planarity value.Example 12.
Consider a multigraphG*=(V,E) such that V={a,b,c,d,e},
(11)E={ab,ac,ad,ad,bc,bd,cd,ce,ae,de,be}.
Let A=(μA,νA) be an intuitionistic fuzzy of V and let B=(μB,νB) be an intuitionistic fuzzy multiedge set of V×V defined by Table 2.
The intuitionistic fuzzy multigraph as shown in Figure3 has two points of intersections P1 and P2. P1 is a point between the edges (ad,0.2,0.1) and (bc,0.2,0.1) and P2 is between (ad,0.3,0.1) and (bc,0.2,0.1). For the edge (ad,0.2,0.1), Iad=(0.4,0.5), For the edge (ad,0.3,0.1), Iad=(0.6,0.5), and for the edge (bc,0.2,0.1), Ibc=(0.6667,1). For the first point of intersection P1, intersecting value IP1 is (0.5335,0.75) and that for the second point of intersection P2,IP2=(0.63335,0.75). Therefore, the intuitionistic fuzzy planarity value for the intuitionistic fuzzy multigraph shown in Figure 3 is (0.461,0.4).Table 2
(a)
a
b
c
d
e
μ
A
0.5
0.4
0.3
0.6
0.6
ν
A
0.2
0.1
0.1
0.2
0.1
(b)
a
b
a
c
a
d
a
d
b
c
b
d
c
d
a
e
c
e
d
e
b
e
μ
B
0.2
0.2
0.2
0.3
0.2
0.2
0.2
0.2
0.2
0.2
0.2
ν
B
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1Figure 3
Intuitionistic fuzzy planar graph.Intuitionistic fuzzy planarity value for the intuitionistic fuzzy complete multigraph is calculated from Theorem13.Theorem 13.
LetG be an intuitionistic fuzzy complete multigraph. The intuitionistic fuzzy planarity value f=(Mf,Nf) of G is given by Mf=1/(1+np) and Nf=1/(1+np) such that Mf+Nf≤1, where np is the number of points of intersections between the edges in G.Definition 14.
An intuitionistic fuzzy planar graphG is calledstrong intuitionistic fuzzy planar graph if the intuitionistic fuzzy planarity value f=(Mf,Nf) of the graph is Mf≥0.5, Nf≤0.5.Theorem 15.
LetG be a strong intuitionistic fuzzy planar graph. The number of points of intersections between strong edges in G is at most one.Proof.
LetG be a strong intuitionistic fuzzy planar graph. Assume that G has at least two points of intersections P1 and P2 between two strong edges in G. For any strong edge (ab,μB(ab)i,νB(ab)i),
(12)μB(ab)i≥12min⁡⁡{μA(a),μA(b)},νB(ab)i≤12max⁡{νA(a),νA(b)}.
This shows that Mab≥0.5 or Nab≤0.5. Thus for two intersecting strong edges (ab,μB(ab)i,νB(ab)i) and (cd,μB(cd)j,νB(cd)j),
(13)Mab+Mcd2≥0.5,Nab+Ncd2≤0.5;
that is, MP1≥0.5, NP1≤0.5. Similarly, MP2≥0.5, NP2≤0.5. This implies that 1+MP1+MP2≥2, 1+NP1+NP2≤2. Therefore, fM=1/(1+MP1+MP2)≤0.5, fN=1/(1+NP1+NP2)≥0.5. It contradicts the fact that the intuitionistic fuzzy graph is a strong intuitionistic fuzzy planar graph. Thus number of points of intersections between strong edges can not be two. Obviously, if the number of points of intersections of strong intuitionistic fuzzy edges increases, the intuitionistic fuzzy planarity value decreases. Similarly, if the number of points of intersection of strong edges is one, then the intuitionistic fuzzy planarity value Mf>0.5, Nf<0.5. Any intuitionistic fuzzy planar graph without any crossing between edges is a strong intuitionistic fuzzy planar graph. Thus, we conclude that the maximum number of points of intersections between the strong edges in G is one.Theorem 16.
LetG be an intuitionistic fuzzy planar graph with intuitionistic fuzzy planarity value f=(Mf,Nf). If Mf≥0.67, Nf≤0.33, G do not contain any point of intersection between two strong edges.Definition 17.
LetG be an intuitionistic fuzzy graph. Let 0<c<0.5 be a rational number. An edge xy is said toconsiderable edge if
(14)μB(xy)min⁡{μA(x),μA(y)}≥c,νB(xy)max⁡{νA(x),νA(y)}≤c.
If an edge is not considerable, it is called nonconsiderable edge. For intuitionistic fuzzy multigraph G, a multiedge xy is said to beconsiderable edge if Mxy≥c, Nxy≤c, for each edge xy in G.Remark 18.
Let0<c<0.5 be a rational number. If (μB(xy)/min⁡{μA(x),μA(y)})≥c, (νB(xy)/max⁡{μA(x),μA(y)})≤c for all edges xy of an intuitionistic fuzzy graph G, then the number c is said to be considerable number of the intuitionistic fuzzy graph. Considerable number of an intuitionistic fuzzy graph may not be unique, but it is countable. Clearly, for a specific value of c, a set of considerable edges is obtained and for different values of c one can obtain different sets of considerable edges. Actually, c is a preassigned number for a specific application.Theorem 19.
LetG be a strong intuitionistic fuzzy planar graph with considerable number c. The number of points of intersections between considerable edges in G is at most [1/c](or 1/c-1).Proof.
LetG be a strong intuitionistic fuzzy planar graph, where E={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V}. Let 0<c<0.5 be the considerable number and let f=(Mf,Nf) be the intuitionistic fuzzy planarity value. For any considerable edge (ab,μB(ab)i,νB(ab)i),
(15)μB(ab)i≥c×min⁡⁡{μA(a),μA(b)},νB(ab)i≤c×max⁡{νA(a),νA(b)}.
This shows that Mab≥c, Nab≤c. Let P1,P2,…,Pn be the n points of intersections between considerable edges. Then for the point P1 between two intersecting considerable edges (ab,μB(ab)i,νB(ab)i) and (cd,μB(cd)j,νB(cd)j), MP1=(Mab+Mcd)/2≥c, NP1=(Nab+Ncd)/2≤c. So ∑i=1nMPi≥n×c, ∑i=1nNPi≤n×c. Hence Mf≤1/(1+nc), Nf≥1/(1+nc). As G is strong intuitionistic fuzzy planar graph, 0.5<Mf≤1/(1+nc), 0.5>Nf≥1/(1+nc). Hence 0.5<1/(1+nc). This implies n<1/c. This inequality will be satisfied for some integral values of n which are obtained from the following expression:
(16)n={[1c],if1cisnotaninteger1c-1,if1cisaninteger.Face of an intuitionistic fuzzy planar graph is an important parameter. Face of an intuitionistic fuzzy graph is a region bounded by intuitionistic fuzzy edges. Every intuitionistic fuzzy face is characterized by intuitionistic fuzzy edges in its boundary. If all the edges in the boundary of an intuitionistic fuzzy face have membership and nonmembership values 1 and 0, respectively, it becomes crisp face. If one of such edges is removed or has membership and nonmembership values 0 and 1, respectively, the intuitionistic fuzzy face does not exist. So the existence of an intuitionistic fuzzy face depends on the minimum value of strength of intuitionistic fuzzy edges in its boundary. A intuitionistic fuzzy face and its membership values and nonmembership values of an intuitionistic fuzzy graph are defined below.Definition 20.
LetG be an intuitionistic fuzzy planar graph and B={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V}. An intuitionistic fuzzy face of G is a region, bounded by the set of intuitionistic fuzzy edges E′⊂E, of a geometric representation of G. The membership and nonmembership values of the intuitionistic fuzzy face are
(17)min⁡{μB(xy)imin⁡⁡{μA(x),μA(y)},i=1,2,…,m∣xy∈E′},max⁡{νB(xy)imax⁡⁡{νA(x),νA(y)},i=1,2,…,m∣xy∈E′}.Definition 21.
An intuitionistic fuzzy face is calledstrong intuitionistic fuzzy face if its membership value is greater than 0.5 or nonmembership value is less than 0.5, and weak face otherwise. Every intuitionistic fuzzy planar graph has an infinite region which is calledouter intuitionistic fuzzy face. Other faces are calledinner intuitionistic fuzzy faces.Example 22.
Consider an intuitionistic fuzzy planar graph as shown in Figure4. The intuitionistic fuzzy planar graph has the following faces: (i)
intuitionistic fuzzy faceF1 is bounded by the edges (v1v2,0.5,0.1), (v2v3,0.6,0.1), and (v1v3,0.5,0.1);(ii)
outer intuitionistic fuzzy faceF2 is surrounded by edges (v1v3,0.5,0.1), (v1v4,0.5,0.1), (v2v4,0.6,0.1), and (v2v3,0.6,0.1);(iii)
intuitionistic fuzzy faceF3 is bounded by the edges (v1v2,0.5,0.1), (v2v4,0.6,0.1), and (v1v4,0.5,0.1).Clearly, the membership value and nonmembership value of an intuitionistic fuzzy face F1 are 0.833 and 0.333, respectively. The membership value and nonmembership value of an intuitionistic fuzzy face F3 are also 0.833 and 0.333, respectively. Thus F1 and F3 are strong intuitionistic fuzzy faces.Figure 4
Faces in intuitionistic fuzzy planar graph.We now introduce dual of intuitionistic fuzzy planar graph. In intuitionistic fuzzy dual graph, vertices are corresponding to the strong intuitionistic fuzzy faces of the intuitionistic fuzzy planar graph and each intuitionistic fuzzy edge between two vertices is corresponding to each edge in the boundary between two faces of intuitionistic fuzzy planar graph. The formal definition is given below.Definition 23.
LetG be an intuitionistic fuzzy planar graph and let
(18)B={(xy,μB(xy)i,νB(xy)i),i=1,2,…,m∣xy∈V×V}.
Let F1,F2,…,Fk be the strong intuitionistic fuzzy faces of G. The intuitionistic fuzzy dual graph of G is an intuitionistic fuzzy planar graph G′=(V′,A′,B′), where V′={xi,i=1,2,…,k}, and the vertex xi of G′ is considered for the face Fi of G. The membership and nonmembership values of vertices are given by the mapping A′=(μA′,νA′):V′→[0,1]×[0,1] such that μA′(xi)=max⁡{μB′(uv)i, i=1,2,…,p∣uv is an edge of the boundary of the strong intuitionistic fuzzy face Fi}, and νA′(xi)=min⁡{νB′(uv)i, i=1,2,…,p∣uv is an edge of the boundary of the strong intuitionistic fuzzy face Fi}.There may exist more than one common edge between two facesFi and Fj of G. Thus there may be more than one edge between two vertices xi and xj in intuitionistic fuzzy dual graph G′. Let μBl(xixj) denote the membership value of the lth edge between xi and xj, and νB1(xixj) denote the nonmembership value of the lth edge between xi and xj. The membership and nonmembership values of the intuitionistic fuzzy edges of the intuitionistic fuzzy dual graph are given by μB′(xixj)l=μBl(uv)j, νB′(xixj)l=νBl(uv)j where (uv)l is an edge in the boundary between two strong intuitionistic fuzzy faces Fi and Fj and l=1,2,…,s, where s is the number of common edges in the boundary between Fi and Fj or the number of edges between xi and xj. If there is any strong pendant edge in the intuitionistic fuzzy planar graph, then there will be a self-loop in G′ corresponding to this pendant edge. The edge membership and nonmembership value of the self-loop is equal to the membership and nonmembership value of the pendant edge. Intuitionistic fuzzy dual graph of intuitionistic fuzzy planar graph does not contain point of intersection of edges for a certain representation, so it is intuitionistic fuzzy planar graph with planarity value (1,1). Thus the intuitionistic fuzzy face of intuitionistic fuzzy dual graph can be similarly described as in intuitionistic fuzzy planar graphs.Example 24.
Consider an intuitionistic fuzzy planar graphG=(V,A,B) as shown in Figure 5 such that V={a,b,c,d}, A=(a,0.6,0.2),(b,0.7,0.2),(c,0.8,0.2),(d,0.9,0.1), and B={(ab,0.5,0.01),(ac,0.4,0.01),(ad,0.55,0.01),(bc,0.45,0.01),(bc,0.6,0.01),(cd,0.7,0.01)}Figure 5
Intuitionistic fuzzy dual graph.The intuitionistic fuzzy planar graph has the following faces:(i)
intuitionistic fuzzy faceF1 is bounded by (ab,0.5,0.01),(ac,0.4,0.01),(bc,0.45,0.01),(ii)
intuitionistic fuzzy faceF2 is bounded by (ad,0.55,0.01),(cd,0.7,0.01),(ac,0.4,0.01),(iii)
intuitionistic fuzzy faceF3 is bounded by (bc,0.45,0.01),(bc,0.6,0.01),(iv)
outer intuitionistic fuzzy faceF4 is surrounded by (ab,0.5,0.01), (bc,0.6,0.01), (cd,0.7,0.01), (ad,0.55,0.01).Routine calculations show that all faces are strong intuitionistic fuzzy faces. For each strong intuitionistic fuzzy face, we consider a vertex for the intuitionistic fuzzy dual graph. So the vertex set V′={x1,x2,x3,x4}, where the vertex xi is taken corresponding to the strong intuitionistic fuzzy face Fi, i=1,2,3,4. Thus
(19)μA′(x1)=max⁡⁡{0.5,0.4,0.45}=0.5,μA′(x2)=max⁡⁡{0.55,0.7,0.4}=0.7,νA′(x1)=min⁡{0.01,0.01,0.01}=0.01,νA′(x2)=min⁡{0.01,0.01,0.01}=0.01,μA′(x3)=max⁡{0.45,0.6}=0.6,μA′(x4)=max⁡{0.5,0.6,0.7,0.55}=0.7,νA′(x3)=min⁡{0.01,0.01}=0.01,νA′(x4)=min⁡{0.01,0.01,0.01,0.01}=0.01.
There are two common edges ad and cd between the faces F2 and F4 in G. Hence between the vertices x2 and x4, there exist two edges in the intuitionistic fuzzy dual graph of G. Membership and nonmembership values of these edges are given by
(20)μB′(x2x4)=μB(cd)=0.7,μB′(x2x4)=μB(ad)=0.55,νB′(x2x4)=νB(cd)=0.01,νB′(x2x4)=νB(ad)=0.01.
The membership and nonmembership values of other edges of the intuitionistic fuzzy dual graph are calculated as
(21)μB′(x1x3)=μB(bc)=0.45,μB′(x1x2)=μB(ac)=0.4,μB′(x1x4)=μB(ab)=0.5,μB′(x3x4)=μB′(bc)=0.6,νB′(x1x3)=μB(bc)=0.01,νB′(x1x2)=νB(ac)=0.01,νB′(x1x4)=νB(ab)=0.01,νB′(x3x4)=νB(bc)=0.01.
Thus the edge set of intuitionistic fuzzy dual graph is
(22)B′={(x1x3,0.45,0.01),(x1x2,0.4,0.01),(x1x4,0.5,0.01),000(x3x4,0.6,0.01),(x2x4,0.7,0.01),(x2x4,0.55,0.01)}.
In Figure 5, the intuitionistic fuzzy dual graph G′=(V′,A′,B′) of G is drawn by dotted line.Weak edges in planar graphs are not considered for any calculation in intuitionistic fuzzy dual graphs. We state the following theorems without their proofs.Theorem 25.
LetG be an intuitionistic fuzzy planar graph whose number of vertices, number of intuitionistic fuzzy edges, and number of strong faces are denoted by n, p, m, respectively. Let G′ be the intuitionistic fuzzy dual graph of G. Then (i)
the number of vertices ofG′ is equal to m,(ii)
number of edges ofG′ is equal to p,(iii)
number of intuitionistic fuzzy faces ofG′ is equal to n.Theorem 26.
LetG=(V,A,B) be an intuitionistic fuzzy planar graph without weak edges and let the intuitionistic fuzzy dual graph of G be G′=(V′,A′,B′). The membership and nonmembership values of intuitionistic fuzzy edges of G′ are equal to membership and nonmembership values of the intuitionistic fuzzy edges of G.We now study isomorphism between intuitionistic fuzzy planar graphs.Definition 27.
LetG1 and G2 be intuitionistic fuzzy graphs. Anisomorphismf:G1→G2 is a bijective mapping f:V1→V2 which satisfies the following conditions: (c)
μA1(x1)=μA2(f(x1)), νA1(x1)=νA2(f(x1)),(d)
μB1(x1y1)=μB2(f(x1)f(y1)), νB1(x1y1)=νB2(f(x1)f(y1)),for all x1∈V1, x1y1∈E1.Definition 28.
LetG1 and G2 be intuitionistic fuzzy graphs. Then, aweak isomorphismf:G1→G2 is a bijective mapping f:V1→V2 which satisfies the following conditions: (e)
f is homomorphism,(f)
μA1(x1)=μA2(f(x1)), νA1(x1)=νA2(f(x1)),for all x1∈V1.Definition 29.
LetG1 and G2 be the intuitionistic fuzzy graphs. Aco-weak isomorphismf:G1→G2 is a bijective mapping f:V1→V2 which satisfies that (g)
f is homomorphism,(h)
μB1(x1y1)=μB2(f(x1)f(y1)), νB1(x1y1)=νB2(f(x1)f(y1)),for all x1y1∈V1.It is known that isomorphism between intuitionistic fuzzy graphs is an equivalence relation. If there is an isomorphism between two intuitionistic fuzzy graphs such that one is an intuitionistic fuzzy planar graph, then the other will be intuitionistic fuzzy graph. We state the following result without its proof.Theorem 30.
LetG be an intuitionistic fuzzy planar graph and let H be an intuitionistic fuzzy graph. If there exists an isomorphism f:G→H, H can be drawn as intuitionistic fuzzy planar graph with same planarity value of G.Two intuitionistic fuzzy planar graphs with same number of vertices may be isomorphic. But the relations between intuitionistic fuzzy planarity values of two intuitionistic fuzzy planar graphs may have the following relations.Theorem 31.
LetG1 and G2 be two isomorphic intuitionistic fuzzy graphs with intuitionistic fuzzy planarity values f1 and f2, respectively. Then f1=f2.Theorem 32.
LetG1 and G2 be two weak isomorphic intuitionistic fuzzy graphs with intuitionistic fuzzy planarity values f1 and f2, respectively. f1=f2 if the edge membership and nonmembership values of corresponding intersecting edges are same.Theorem 33.
LetG1 and G2 be two co-weak isomorphic intuitionistic fuzzy graphs with intuitionistic fuzzy planarity values f1 and f2, respectively. f1=f2 if the minimum of membership values and maximum of nonmembership values of the end vertices of corresponding intersecting edges are same.


## 4. Conclusions

Graph theory has numerous applications to problems in systems analysis, operations research, economics, and transportation. However, in many cases, some aspects of a graph-theoretic problem may be vague or uncertain. It is natural to deal with the vagueness and uncertainty using the methods of fuzzy sets. Since intuitionistic fuzzy set has shown advantages in handling vagueness and uncertainty compared to fuzzy set, we have applied the concept of intuitionistic fuzzy sets to multigraphs and planar graphs in this paper. The natural extension of this research work is application of intuitionistic fuzzy planar graphs in the area of applied soft computing including neural networks, decision making, and geographical information systems. We plan to extend our research of fuzzification to (1) soft fuzzy planar graphs, (2) roughness in planar graphs, (3) vague planar graphs, and (4) bipolar fuzzy planar graphs.



---

*Source: 397823-2014-08-24.xml*