A study on bipolar fuzzy planar graph and its application in image shrinking

Abstract

In this paper, bipolar fuzzy planar graph is defined and studied several properties. The bipolar fuzzy planar graph is defined in a very interesting way. The parameter “degree of planarity” measures the planarity of a bipolar fuzzy graph. The other relevant terms such as strong edges, bipolar fuzzy faces, strong bipolar fuzzy faces are defined here. A very close association of bipolar fuzzy planar graph is bipolar fuzzy dual graph. This is also defined and several properties of it are studied. Bipolar fuzzy planar graph and bipolar fuzzy dual graph have many applications in different fields including design of social network, design of subway tunnel or routes, gas or oil pipelines, image segmentation, etc.

Keywords

Bipolar fuzzy graphs bipolar fuzzy multigraphs bipolar fuzzy planar graphs bipolar fuzzy dual graphs

1 Introduction

Graph theory is now become an important topic in research area due to its application in real world. There are many real world applications of graph theory in which crossing between edges is complicated such as computer networks, circuit designing, subways, utility lines, flyovers, etc. After the development of graph theory, Rosenfeld [26] introduced fuzzy graph theory and then, the fuzzy graph theory is growing rapidly with a large number of branches. In 1998, the concept of bipolar fuzzy set is introduced by Zhang [39] as a generalization of fuzzy set. A bipolar fuzzy set is a generalization of Zadeh’s fuzzy set. Authors may refer [2 , 28–30] for more information on fuzzy sets as well as on fuzzy graphs. Abdul-jabbar et al. [1] and Nirmala and Dhanabal [20] introduced the concept of fuzzy planar graph. Recently, Samanta and Pal [21, 34] introduced fuzzy planar graph in a different way. In these papers, they also introduced fuzzy faces, strong fuzzy planar graphs, fuzzy dual graphs, etc. Pramanik et al. [22] have defined interval-valued fuzzy planar graph and investigated several properties. Also, they have introduced fuzzy φ-tolerance competition graph in [23] and interval-valued fuzzy φ-tolerance competition graph in [24]. Ghorai and Pal [10, 11] have recently worked on m-polar fuzzy planar graphs. They have also discussed certain types of product bipolar fuzzy graphs in [12]. Ghorai et al. [13] have given new concepts of regularity in product m-polar fuzzy graphs. Recently, Sahoo and Pal [27] have discussed on product of intuitionistic fuzzy graphs and degree.

Due to lack of space and huge population, the necessity of flyovers, subway tunnels, metro-lines increases. But crossing of routes can be accepted, since the crossing of subway tunnels, metro-lines, etc. are very expensive in some cases. It is clear that, crossing of one congested and a low congested route is more safer than crossing of two congested route. The term “congested”, “low congested” are vague and hence can not be handled in crisp graph. These vague terms can be dealt better in bipolar fuzzy graph by assigning some positive membership and negative membership values. In general, one can try to place the communication lines at different heights when there is need to cross the lines. In case of electrical wires it is not a big issue, but it causes huge expenses for some type of lines such as, building one flyover over another. Using planar graphs, these type of problems can be modeled and inspected further for reducing the cost and space of construction. In crisp planar graphs, crossing of lines are strictly not allowed. So, in such type of modeling the real applications where crossing of lines are necessary, can not be represented by crisp planar graphs. Using decomposition of planar graphs, various computational challenges including image segmentation or shape matching is solved.athematical sense, strong route means highly congested route and weak route means low congested route. Thus in city planning, crossing between a strong route and a weak route is more safer than crossing between two strong routes.

In this modern age, image analysing, image segmenting, image shrinking, etc. are growing and useful research topic. Images are captured and stored in terms of pixel with some parametric informations such as intensity of colours, distance of pixels, size of pixels, etc. Taking pixels as vertices and intensity and non-intensity of pixels as positive and negative membership values respectively, an image information can be represented as a bipolar fuzzy graph.

Motivated from these ideas, bipolar fuzzy planar graph is introduced, which is itself a bipolar fuzzy graph with some degree of planarity. Two procedural applications namely “image shrinking” and “city planning” are discussed in Section 5.

Recently, the bipolar fuzzy graphs have been discussed in [2 , 9]. In these articles, the concepts of neighbourly irregular bipolar fuzzy graphs, neighbourly totally irregular bipolar fuzzy graphs, highly irregular bipolar fuzzy graphs and highly totally irregular bipolar fuzzy graphs have been introduced. Samanta and Pal [32] have also worked on bipolar fuzzy hypergraphs. There are so many related works found in [31 , 35–37].

In this paper, we defined bipolar fuzzy planar graph and bipolar fuzzy dual graph and presented several properties.

2 Preliminaries

A graph G = (V, E) is a representation of a set V of objects (vertices) where some pairs of objects are connected by links (edges), where the set E of such pairs is defined to be a subset of V × V. G is finite when V and E are finites. An infinite graph is one with an infinite set of vertices or edges or both. Most commonly in graph theory, it is implied that the graphs discussed are finite. A multigraph is a graph containing multiple edges and without self loops. There is no unique geometric representation of a graph.

Embedding is a geometrical representation of a graph in any surface so that no edges intersect. A graph G is planar if it can be embedded in the plane. So the graph is non-planar if it is not planar that is, it can not be drawn without crossing. A planar graph splits the plane into a set of regions, called faces. The length of a face in a planar graph G is the total length of the closed walk in G bounding the face. The portion of the plane lying outside is infinite region.

In graph theory, the dual graph of a given planar graph G is a graph which has a vertex corresponding to each faces of G, and the graph has an edge joining two neighboring faces for each edge in G, for a certain embedding of G.

A fuzzy set A on an universal set X is meant by a mapping m : X → [0, 1], which is called the membership function. A fuzzy set is denoted by A = (X, m).

A fuzzy graph [26] ξ = (V, σ, μ) is a non-empty set V with the 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 ξ respectively. A loop at a vertex x ∈ V in ξ is represented by μ (x, x) ≠0. An edge is non-trivial if μ (x, y) ≠0. A fuzzy graph ξ = (V, σ, μ) is complete if μ (u, v) = min {σ (u) , σ (v)} for all u, v ∈ V, where (u, v) denotes the edge between the vertices u and v.

Several definitions of strong edge are available in literature. Among them the definition of [7] is more suitable for our purpose. The definition is given below:

For the fuzzy graph ξ = (V, σ, μ), an edge (x, y) is called strong [7] if $\frac{1}{2} min {σ (x), σ (y)} \leq μ (x, y)$ and weak otherwise. The strength of the fuzzy edge (x, y) is characterized by the value $\frac{μ (x, y)}{min {σ (x), σ (y)}}$ .

Let V be not an empty set. A bipolar fuzzy set (BFS) [14, 39] B in V is characterized by $B = {(V, μ_{B}^{P} (v), μ_{B}^{N} (v)) | v \in V}$ , where $μ_{B}^{P} : V \to [0, 1]$ and $μ_{B}^{N} : V \to [- 1, 0]$ are positive membership function and negative membership function respectively. The positive membership value $μ_{B}^{P} (v)$ is used to denote the amount which the element v satisfies the property corresponding to a bipolar fuzzy set B, and the negative membership value $μ_{B}^{N} (x)$ to denote the amount which the element v satisfies the implicit counter-property to some extent corresponding to a bipolar fuzzy set B. If $μ_{B}^{P} (v) \neq 0$ and $μ_{B}^{N} (v) = 0$ , then v is considered that it has only positive satisfaction for B. If $μ_{B}^{P} (v) = 0$ and $μ_{B}^{N} \neq 0$ , then v is considered that it does not satisfy the property of B but it satisfies the counter-property of B to some extent. When the membership function of the property overlaps that of its counter property over some portion of V, $μ_{B}^{P} (v) \neq 0$ and $μ_{B}^{N} (v) \neq 0$ .

For the sake of simplicity, we shall use the symbol $B = (μ_{B}^{P}, μ_{B}^{N})$ for the bipolar fuzzy set $B = {(v, μ_{B}^{P} (v), μ_{B}^{N} (v)) | v \in V}$ .

Let V be a nonempty set. Then we call the mapping $B = (μ_{B}^{P}, μ_{B}^{N}) : V \times V \to [0, 1] \times [- 1, 0]$ a bipolar fuzzy relation [2] on V such that $μ_{B}^{P} (u, v) \in [0, 1]$ and $μ_{B}^{N} (u, v) \in [- 1, 0]$ .

A bipolar fuzzy graph [2] (BFG) ξ of a (crisp) graph G = (V, E) is a pair ξ = (A, B, V, E) where $A = (μ_{A}^{P}, μ_{A}^{N})$ is a bipolar fuzzy set on V and $B = (μ_{B}^{P}, μ_{B}^{N})$ is a bipolar fuzzy relation on E = V × V such that $μ_{B}^{P} (u, v) \leq min {μ_{A}^{P} (u), μ_{A}^{P} (v)}$ and $μ_{B}^{N} (u, v) \geq max {μ_{A}^{N} (u), μ_{A}^{N} (v)}$ for all (u, v) ∈ E.

The underlying crisp graph of a BFG ξ = (A, B, V, E) is the crisp graph G = (V, E) where $E = {(u, v) | μ_{B}^{P} (u, v) > 0 or μ_{B}^{N} (u, v) < 0$ }.

A BFG ξ = (V, E, A, B) is said to be complete if $μ_{B}^{P} (u, v) = min {$ $μ_{A}^{P} (u)$ , $μ_{A}^{P} (v)}$ and $μ_{B}^{N} (u, v)$ = max { $μ_{A}^{N} (u)$ , $μ_{A}^{N} (v)}$ for all u, v ∈ V.

A BFG is called strong BFG if $μ_{B}^{P} (u, v) = min {μ_{A}^{P} ($ $u), μ_{A}^{P} (v)}$ and $μ_{B}^{N} (u, v)$ = $max {μ_{A}^{N} (u)$ , $μ_{A}^{N} (v)}$ for all edges (u, v) in the bipolar fuzzy graph.

If the vertex set V of a BFG (V, E, A, B) can be partitioned into two non-empty subsets V₁ and V₂ such that $μ_{B}^{P} (u, v) = 0$ and $μ_{B}^{N} (u, v) = 0$ if u, v ∈ V₁ or u, v ∈ V₂. $μ_{B}^{P} (u, v) > 0$ and $μ_{B}^{N} (u, v) < 0$ or $μ_{B}^{P} (u, v) = 0$ and $μ_{B}^{N} (u, v) < 0$ or $μ_{B}^{P} (u, v) > 0$ and $μ_{B}^{N} (u, v) = 0$ if u ∈ V₁(or u ∈ V₂) and v ∈ V₂(or v ∈ V₁), the bipolar fuzzy graph is said to be a bipolar bipartite fuzzy graph. A bipolar bipartite fuzzy graph is said to complete if $μ_{B}^{P} (u, v) = min {μ_{A}^{P} (u), μ_{A}^{P} (v)}$ and $μ_{B}^{N} (u, v) = max {μ_{A}^{N} (u), μ_{A}^{N} (v)}$ .

Now, we define bipolar fuzzy multi-set. A multiset over a non-empty set V is simply a function d : V → N, where N is the set of natural numbers. Yager [38] first discussed fuzzy multisets, although he used the term “fuzzy bag”. An element of a non-empty set V may come more than once with the same or different membership values. A natural generalization of this elucidation of multiset heads to the notion of fuzzy multiset, or fuzzy bag, over a non-empty set V as a mapping $\tilde{C} : V \times [0, 1] \to N$ . The membership values of v ∈ V are denoted by v_{μ
^j}, j = 1, 2, …, p where p = max {j : v_{μ
^j} ≠ 0} . So the fuzzy multiset can be denoted as M = {(v, v_{μ
^j}) , j = 1, 2, …, p|v ∈ V}. Bipolar fuzzy multiset (BFMS) is another generalisation of multi-set. The definition is given below.

Definition 1. Let V be not an empty set. Also let, $μ_{i}^{P} : V \to [0, 1]$ and $μ_{i}^{N} : V \to [- 1, 0]$ be mappings defined for all v ∈ V and i = 1, 2, …, p where $μ_{p}^{P} (x) \neq 0$ or $μ_{p}^{N} (x) \neq 0$ . The BFMS on V is denoted as ${(V, μ_{i}^{P}, μ_{i}^{N}), i = 1, 2, \dots, p where μ_{p}^{P} (x) \neq 0$ or $μ_{p}^{N} (x) \neq 0$ }.

Example 1. Let V = {a, b, c, d}. A BFMS on V is {(a, 0.5, - 0.3), (a, 0.4, - 0.6), (b, 0.6, - 0.2), (c, 0.6, - 0.3), (d, 0.2, - 0.4), (d, 0.4, - 0.3), (d, 0.3, - 0.5)}. Here $μ_{1}^{P} (a) = 0.5$ , $μ_{2}^{P} (a) = 0.4$ and $μ_{1}^{N} (a) = - 0.3$ , $μ_{2}^{N} (a) = - 0.6,$ etc.

2.1 Bipolar fuzzy multigraph

In this section, bipolar fuzzy multigraph (BFMG) is introduced. Let V be a non-empty set. Also, let $σ_{i}^{P} : V \to [0, 1], σ_{i}^{N} : V \to [- 1, 0]$ be the mappings such that $A = {(V, σ_{i}^{P}, σ_{i}^{N}), i = 1, 2, \dots, p$ where $σ_{p}^{P} (x) \neq 0 or σ_{p}^{N} (x) \neq 0, x \in V}$ be the BFMS on V. Let $B = {(V \times V, μ_{j}^{P}, μ_{j}^{N}), j = 1, 2, \dots, q$ where $μ_{q}^{P} (x, y) \neq 0$ or $μ_{q}^{N} (x, y) \neq 0, x, y \in V \times V}$ be a bipolar fuzzy multi-set on V × V. (A, B, V, E) is said to be BFMG if $μ_{j}^{P} (x, y) \leq min {σ_{i}^{P} (x), σ_{i}^{P} (y)}$ and $μ_{j}^{N} \geq max {σ_{i}^{N} (x), σ_{i}^{N} (y)}, i = 1, 2, \dots, p$ , j = 1, 2, …, q for all x, y ∈ V. An example of bipolar fuzzy multigraph is given below.

Example 2. Let V = {a, b, c} be a set of vertices. Let σ^P (a) =0.7, σ^N (a) = -0.1, σ^P (b) =0.8, σ^N (b) = -0.3, σ^P (c) =0.5, σ^N (c) = -0.4 and $μ_{1}^{P} (a, b) = 0.5$ , $μ_{1}^{N} (a, b) = - 0.2$ , $μ_{2}^{P} (a, b) = 0.6$ , $μ_{2}^{N} (a, b) = - 0.2$ , $μ_{3}^{P} (a, b) = 0.7$ , $μ_{3}^{N} = - 0.1$ , $μ_{4}^{P} (b, c) = 0.3$ , $μ_{4}^{N} (b, c) = - 0.2$ , $μ_{5}^{P} (b, c) = 0.2$ , $μ_{5}^{N} (b, c) = - 0.1$ , $μ_{6}^{P} (b, c) = 0.4$ , $μ_{6}^{N} (b, c) = - 0.3$ , $μ_{7}^{P} (c, a) = 0.4$ , $μ_{7}^{N} (c, a) = - 0.1$ , $μ_{8}^{P} (c, a) = 0.3$ , $μ_{8}^{N} (c, a) = - 0.2$ , $μ_{9}^{P} (c, a) = 0.1$ , $μ_{9}^{N} (c, a) = - 0.1$ . Then A = {(a, 0.7, - 0.2) , (b, 0.4, - 0.5) , (c, 0.5, - 0.4)} and B = {((a, b) , 0.5, - 0.2) , ((a, b) , 0.6, - 0.2) , ((a, b) , 0.7, - 0.1) , ((b, c) , 0.3, - 0.2) , ((b, c) , 0.2, - 0.1) , ((b, c) , 0.4, - 0.3), ((c, a) , 0.4, - 0.1) , ((c, a) , 0.3, - 0.2) , ((c, a) , 0.1, - 0.1)}. Thus, (A, B, V, E) is a BFMG (see Fig. 1).

Fig.1

An example of bipolar fuzzy multigraph.

3 Bipolar fuzzy planar graphs

Planarity is foremost problem in connecting the water lines, wire lines, printed circuit design, gas lines, etc. But, some times little crossing may be accepted to these design of such lines or circuits. So bipolar fuzzy planar graph (BFPG) is an important topic for these connections.

If there is atleast one intersection of edges in all possible geometrical representation of a crisp graph, the graph is called non-planar graph. Let a crisp graph G has an intersection between two edges (a, b) and (c, d) for a certain geometrical representation. In fuzzy concept, we say that these two edges have membership value 1. If we remove the edge (c, d), the graph becomes planar. In fuzzy sense, the membership values of the edges (a, b) and (c, d) are 1 and 0 respectively.

Let ξ = (A, B, V, E) be a BFG and the graph has only one crossing between two edges $((w, x), μ_{B}^{P} (w, x), μ_{B}^{N} (w, x))$ and $((y, z), μ_{B}^{P} (y, z), μ_{B}^{N} (y, z))$ for a certain geometric representation. If $μ_{B}^{P} (w, x) = 1$ (or $μ_{B}^{N} (w, x) = - 1$ ) and $μ_{B}^{P} (y, z) = 0 = μ_{B}^{N} (y, z)$ , then we say that the graph has no crossing. Similarly, if the value of $μ_{B}^{P} (w, x)$ is near to 1 and $μ_{B}^{P} (y, z)$ and $μ_{B}^{N} (y, z)$ have values near to 0, the crossing is not be important for the planarity. If $μ_{B}^{P} (w, x)$ has value near to 1 and $μ_{B}^{P} (y, z)$ has value near to 1, then the crossing becomes very indispensable for the planarity.

Before going to the main definition, some co-related terms are discussed below.

3.1 Intersecting value in bipolar fuzzy multigraph

The positive-strength of an edge (a, b) is measured by $I_{(a, b)}^{P} = \frac{μ_{B}^{P} (a, b)}{min {μ_{A}^{P} (a), μ_{A}^{P} (b)}}$ . Similarly, the negative-strength of the edge (a, b) is measured by $I_{(a, b)}^{N} = \frac{| μ_{B}^{N} (a, b) |}{| max {μ_{A}^{N} (a), μ_{A}^{N} (b)} |}$ . So, positive-strength and negative-strength belongs to the unit interval [0,1]. Therefore, $I_{(a, b)}^{P} - I_{(a, b)}^{N} \in [- 1, 1]$ .

Based on the values of $I_{(a, b)}^{P}$ and $I_{(a, b)}^{N}$ , four types of edges are defined.

Definition 2. Let ξ = (A, B, V, E) be a BFMG. An edge (a, b) in ξ is said to be

p-strong if $I_{(a, b)}^{P} \geq 0.5$

n-strong if $I_{(a, b)}^{N} \geq 0.5$

very p-strong if $I_{(a, b)}^{P} - I_{(a, b)}^{N} \geq 0.5$

very n-strong if $I_{(a, b)}^{N} - I_{(a, b)}^{P} \geq 0.5$

In BFMG, when two edges intersect at a point, the value associated to that point is calculated in the following way. Let a BFMG contains two edges ((a, b), $μ_{B}^{P} (a, b)$ , $μ_{B}^{N} (a, b))$ and ((c, d), $μ_{B}^{P} (c, d)$ , $μ_{B}^{N} (c, d))$ which are intersected at a point T. Now, we calculate $I_{(a, b)}^{P} - I_{(a, b)}^{N}$ and $I_{(c, d)}^{P} - I_{(c, d)}^{N}$ for the respective edges. Then, the average of these values is calculated as $g = \frac{(I_{(a, b)}^{P} - I_{(a, b)}^{N}) + (I_{(c, d)}^{P} - I_{(c, d)}^{N})}{2} .$

We define the intersecting value at the point T by $I_{T} = 1 + g$ . It is noted that $0 \leq I_{T} \leq 2$ . If strengths of two edges are large, then intersecting value is large and so on. Planarity is inversely proportional to the number of point of intersections in a BFMG. Based on this concept, a new defintion is introduced below in BFMG.

Definition 3. Let ξ be a BFMG and for a certain geometrical representation T₁, T₂, …, T_k be the point of intersections between the edges. ξ is said to be bipolar fuzzy planar graph (BFPG) with degree of planarity f, where $f = \frac{1}{1 + {I_{T_{1}} + I_{T_{2}} + \dots + I_{T_{k}}}} .$

It is easy to verify that the range of f is 0 < f ≤ 1.

In a certain geometrical representation of a BFPG, if there is no point of intersection then the degree of planarity of the BFPG is 1. In this case, the underlying graph of this BFPG is the crisp planar graph. If f decreases, then the number of point of intersections between the edges increases and obviously the nature of planarity decreases. From this analogy, one can say that every BFG is a BFPG graph with some degree of planarity.

The degree of planarity for the bipolar fuzzy complete graph is calculated from the following theorem.

Theorem 1. Let ξ be a complete BFPG. The degree of planarity, f of ξ is given by $f = \frac{1}{1 + N_{p}}$ , where N_p is the number of point of intersections between the edges in ξ.

Proof. Let ξ = (V, E, A, B) be a complete BFPG. For the complete BFPG, $μ_{B}^{P} (x, y) = min {μ_{A}^{P} (x), μ_{A}^{P} (y)}$ and $μ_{B}^{N} (x, y) = max {μ_{A}^{N} (x), μ_{A}^{N} (y)}$ for all x, y ∈ V. Let T₁, T₂, …, T_k, be the point of intersections between the edges in ξ, k being an integer. For any edge (a, b) in a bipolar fuzzy complete multigraph, strength of an edge = $I_{(a, b)}^{P} - I_{(a, b)}^{N} = 0$ . Thus g = 0 and $I_{T_{1}} = 1 + g = 1$ . Hence $I_{T_{i}} = 1$ for i = 1, 2, …, k . Now, $f = \frac{1}{1 + I_{T_{1}} + I_{T_{2}} + \dots + I_{T_{k}}} = \frac{1}{1 + (1 + 1 + \dots + 1)} = \frac{1}{1 + N_{p}}$ , where N_p is the number of point of intersections between the edges in ξ. ■

Depending on the degree of planarity, the number of point of intersections of a BFPG can be found. The following theorem proves that there is no point of intersection between very p-strong edges if the degree of planarity is greater than 0.4.

Theorem 2. Let ξ be a BFPG with degree of planarity f. If f > 0.4, ξ has no point of intersection between very p-strong edges.

Proof. Let ξ be a BFPG with degree of planarity f > 0.4. Let, if possible, there be atleast one point of intersection, say at T, between two very p-strong edges (a, b) and (c, d). As (a, b) is very p-strong, $I_{(a, b)}^{P} - I_{(a, b)}^{N} \geq 0.5$ and similarly for (c, d), $I_{(c, d)}^{P} - I_{(c, d)}^{N} \geq 0.5$ . Thus g ≥ 0.5 and $I_{T} \geq 1.5$ . Hence, $f \leq \frac{1}{1 + 1.5}, i . e . f \leq 0.4$ . A contradiction arises as f > 0.4. This concludes that ξ has no point of intersection between very p-strong edges. ■

From Theorem 2, one can identify a special kind of BFPG whose degree of planarity is more than 0.4. This type of BFPG is defined below.

Definition 4. A BFPG is said to be very p-strong, if its degree of planarity is more than 0.4.

Theorem 3. Let ξ be a BFPG with degree of planarity f. If f < 0.67, ξ has no point of intersection between very n-strong edges.

Proof. Let ξ be a BFPG with degree of planarity f < 0.67. Let, if possible, there be atleast one point of intersection, say at T, between two very n-strong edges (a, b) and (c, d). As (a, b) is very n-strong, $I_{(a, b)}^{N} - I_{(a, b)}^{P} \geq 0.5$ and similarly for (c, d), $I_{(c, d)}^{N} - I_{(c, d)}^{P} \geq 0.5$ . Then obviously, $I_{(a, b)}^{P} - I_{(a, b)}^{N} \leq - 0.5$ and similarly for (c, d), $I_{(c, d)}^{P} - I_{(c, d)}^{N} \leq - 0.5$ . Thus g ≤ -0.5 and $I_{T} \leq 0.5$ . Hence, $f \geq \frac{1}{1 + 0.5}, i . e . f \geq 0.67$ . A contradiction arises as f < 0.67. This concludes that ξ has no point of intersection between very n-strong edges. ■

From Theorem 3, one can identify a special kind of BFPG whose degree of planarity is less than 0.67. This type of BFPG is defined below.

Definition 5. A BFPG is said to be very n-strong, if its degree of planarity is less than 0.67.

Definition 6. (Very strong BFPG) A BFPG is said to be very strong, if its degree of planarity is more than 0.4 and less than 0.67.

Example 3. Let us consider an example of a bipolar fuzzy planar graph shown in Fig. 2. In this BFPG, there are two points of intersections T₁ and T₂ of crossing of edges.

Fig.2

An example of very p-strong BFPG as well as very strong BFPG.

For the intersecting point T₁,

the edges (a, d) and (b, f) are intersected at T₁,

the positive-strength ( $I_{(a, d)}^{P}$ ) and negative-strength ( $I_{(a, d)}^{N}$ ) of the edge (a, d) are 1 and 1 respectively,

the positive-strength ( $I_{(b, f)}^{P}$ ) and negative-strength ( $I_{(b, f)}^{N}$ ) of the edge (b, f) are 0.43 and 1 respectively,

then the intersecting value at the point T₁ is $I_{T_{1}} = 1 + \frac{(1 - 1) + (0.43 - 1)}{2} = 1 - 0.285 = 0.715 ≃ 0.72 .$

For the intersecting point T₂,

the edges (a, d) and (c, f) are intersected at T₂,

the positive-strength ( $I_{(a, d)}^{P}$ ) and negative-strength ( $I_{(a, d)}^{N}$ ) of the edge (a, d) are 1 and 1 respectively,

the positive-strength ( $I_{(c, f)}^{P}$ ) and negative-strength ( $I_{(c, f)}^{N}$ ) of the edge (c, f) are 0.125 and 1 respectively,

then the intersecting value at the point T₂ is $I_{T_{2}} = 1 + \frac{(1 - 1) + (0.125 - 1)}{2} = 1 - 0.4375 = 0.5625 ≃ 0.56 .$

Therefore, the degree of planarity of the fuzzy graph shown in Fig. 2 is

\frac{1}{1 + 0.72 + 0.56} ≃ 0.44

which lies between 0.4 and 0.67. Thus this fuzzy graph is a very p-strong BFPG and also a very n-strong BFPG and hence it is a very strong BFPG.

Theorem 4. Let ξ be a BFPG with degree of planarity f. If f > 0.25, ξ has at most one point of intersection between very p-strong edges.

Proof. Let ξ be a BFPG with degree of planarity f > 0.25. Let, if possible, there is atleast two point of intersections. First, consider T₁ is one of the intersections, between two very p-strong edges (a, b) and (c, d). As (a, b) is very p-strong, $I_{(a, b)}^{P} - I_{(a, b)}^{N} \geq 0.5$ and similarly for (c, d), $I_{(c, d)}^{P} - I_{(c, d)}^{N} \geq 0.5$ . Thus g ≥ 0.5 and $I_{T_{1}} \geq 1.5$ . Similarly, for another intersection T₂, $I_{T_{2}} \geq 1.5$ . Hence, $f \leq \frac{1}{1 + 1.5 + 1.5}, i . e . f \leq 0.25$ . A contradiction arises as f > 0.25. This concludes that ξ has at most one point of intersection between very p-strong edges. ■

Theorem 5. Let ξ be a BFPG with degree of planarity f. If f < 0.5, ξ has at most one point of intersection between very n-strong edges.

Proof. Let ξ = (A, B, V, E) be a BFPG with degree of planarity f < 0.5. Let, if possible, there is atleast two point of intersections. First, consider T₁ is one of the intersections, between two very n-strong edges (a, b) and (c, d). As (a, b) is very n-strong, $I_{(a, b)}^{N} - I_{(a, b)}^{P} \geq 0.5$ and similarly for (c, d), $I_{(c, d)}^{N} - I_{(c, d)}^{P} \geq 0.5$ . Then obviously, $I_{(a, b)}^{P} - I_{(a, b)}^{N} \leq - 0.5$ and similarly for (c, d), $I_{(c, d)}^{P} - I_{(c, d)}^{N} \leq - 0.5$ . Thus g ≤ -0.5 and $I_{T_{1}} \leq 0.5$ . Similarly, for another point of intersection T₂, $I_{T_{2}} \leq 0.5$ . Hence, $f \geq \frac{1}{1 + 0.5 + 0.5}, i . e . f \geq 0.5$ . A contradiction arises as f < 0.5. This concludes that ξ has at most one point of intersection between very n-strong edges. ■ Strength of an edge plays an important role to model some types of problems. If the strength of an edge is very low, the edge should not be considered to design any kind of model. So the edges with sufficient strengths are useful to model such problems. We call these edges as considerable edges, the formal definition is given below.

Definition 7. ξ = (A, B, V, E) be a BFG. Let 0 < c < 0.5 be a rational number. An edge (x, y) is said to p-considerable edge if $I_{(a, b)}^{P} - I_{(a, b)}^{N} \geq c$ .

Let 0 < c < 0.5 be a rational number. If $I_{(a, b)}^{P} - I_{(a, b)}^{N} \geq c$ for all edges (a, b) of a BFG, then the number c is said to be p-considerable number of the BFG. p-considerable number of a BFG may not be unique.

Obviously, for a specific value of c, a set of p-considerable edges is obtained and for different values of c, one can obtain different sets of p-considerable edges. Actually, c is a pre-assigned number for a specific application. For example, a social network is viewed as a BFG, where a social unit (people, organisation, etc.) is taken as a vertex and the relation between them is represented by an edge. The amount of friendship (measured within unit scale) is taken as positive membership value of the edge and similarly the amount of animosity is taken as negative membership value. Now for this network, if we choose c = 0.25, then we get a set of p-considerable edges, say C. This set gives a group of people who have some p-considerable amount (0.25 in this case) of relationship.

Similarly, the definition of n-considerable edges is given below.

Definition 8. Let ξ be a BFG. Let 0 < c < 0.5 be a rational number. An edge (a, b) is said to be n-considerable edge if $I_{(a, b)}^{N} - I_{(a, b)}^{P} \geq c$ .

The number of point of intersections between p-considerable edges and n-considerable edges can be determined from the following theorems.

Theorem 6. Let ξ be a very p-strong BFPG with p-considerable number c. The number of point of intersections between p-considerable edges in ξ is at most 1.

Proof. Let ξ be a very p-strong BFPG. Let 0 < c < 0.5 be a p-considerable number and f be the degree of planarity. For any p-considerable edge (a, b), $I_{(a, b)}^{P} - I_{(a, b)}^{N} \geq c$ . Let T₁, T₂, …, T_k be the k point of intersections between the p-considerable edges. Thus, for the point T₁ between two intersecting p-considerable edges (a, b) and (c, d), $I_{T_{1}} = 1 + \frac{(I_{(a, b)}^{P} - I_{(a, b)}^{N}) + (I_{(c, d)}^{P} - I_{(c, d)}^{N})}{2}$ ≥1 + c. So $\sum_{i = 1}^{k} I_{T_{i}} \geq k \times (1 + c)$ . Hence $f \leq \frac{1}{1 + k (1 + c)}$ . Since ξ is a very p-strong BFPG, $0.4 < f \leq \frac{1}{1 + k (1 + c)}$ , i.e., $0.4 < \frac{1}{1 + k (1 + c)}$ . This implies $k < \frac{3}{2 (1 + c)}$ . This inequality will be satisfied for integral values k = 0, 1. Thus the number of point of intersections between p-considerable edges in ξ is at most 1. This proves the result. ■

Theorem 7. Let ξ be a very n-strong BFPG with n-considerable number c. The number of point of intersections between n-considerable edges in ξ is at least 1.

Proof. Let ξ be a very n-strong BFPG. Let 0 < c < 0.5 be an n-considerable number and f be the degree of planarity. For any n-considerable edge (a, b), $I_{(a, b)}^{N} - I_{(a, b)}^{P} \geq c$ . Therefore, $I_{(a, b)}^{P} - I_{(a, b)}^{N} \leq - c$ . Let T₁, T₂, …, T_k be the k point of intersections between the n-considerable edges. Thus, for the point T₁ between two intersecting n-considerable edges (a, b) and (c, d), $I_{T_{1}} = 1 + \frac{(I_{(a, b)}^{P} - I_{(a, b)}^{N}) + (I_{(c, d)}^{P} - I_{(c, d)}^{N})}{2}$ ≤1 - c. So $Σ_{i = 1}^{k} I_{T i} \leq k ⨉ (1 - c)$ . Hence $f \geq \frac{1}{1 + k (1 - c)}$ . Since ξ is a very n-strong BFPG, $\frac{1}{1 + k (1 - c)} \leq f < 0.67$ , i.e., $\frac{1}{1 + k (1 - c)} < 0.67$ . This implies $k > \frac{0.49}{1 - c}$ . This inequality will be satisfied for integral values k = 1, 2, 3, …. Thus number of point of intersections between n-considerable edges in ξ is at least 1. This proves the result. ■

In crisp sense, K₅ and K_3,3 cannot be drawn without crossing of edges. So, any graph containing K₅ or K_3,3 is non-planar, in conventional sense.

Note 1. A bipolar fuzzy complete graph of five vertices $K_{5}$ or bipolar fuzzy complete bipartite graph $K_{3, 3}$ are very strong BFPG. This statement is justified below.

Let ξ = (V, E, A, B) be a bipolar fuzzy complete graph of five vertices where V = {a, b, c, d, e}.

From Theorem 1, it is known that the degree of planarity of a bipolar fuzzy complete graph is $f = \frac{1}{1 + N_{p}}$ , where N_p is the number of point of intersections of the edges in ξ. We know that the geometric representation of the underlying crisp graph of a bipolar fuzzy complete graph of five vertices is non-planar and one point of intersection can not be avoided for any representation. So $f = \frac{1}{1 + 1} = 0.5$ . Hence ξ is very strong BFPG.

Similarly, it can be shown that a bipolar fuzzy complete bipartite graph $K_{3, 3}$ is a very strong BFPG.

Face of a planar graph is an important parameter. We now introduce the face of a BFPG. Face in a BFG is a region bounded by edges. Every face is represented by edges in its boundary. If positive membership values of all the edges in the boundary of a face are 1 or negative membership values of that edges are -1, then the face becomes a crisp face. If one of such edges is removed or has positive membership value 0 or negative membership value 0, the face does not exist. So the existence of a face depends on the minimum value of strength of edges in its boundary. A face in BFG is defined below.

Definition 9. Let ξ = (A, B, V, E) be a BFPG. A face is a region of ξ, surrounded by the set of edges E′ ⊂ B of a geometric representation of ξ. The strength of a face is given by $m = min {| I_{(a, b)}^{P} - I_{(a, b)}^{N} | : for all (a, b) \in E^{'}} .$

Strength of faces in BFG belongs to [0,1]. If the strength of a face greater than 0.5, the face is called strong otherwise it is weak face. Every BFPG has an infinite region which is called outer face. Other faces are called inner faces.

Example 4. In Fig. 3, a BFPG is considered whose vertex and edge membership values are listed in Table 1. Here F₁, F₂, F₃ and F₄ are four faces and

Table 1

Vertex and edge membership values of the BFPG considered in Fig. 3

Vertices	Membership Values	Edges	Membership Values
v ₁	[0.6, - 0.1]	(v₁, v₂)	[0.50, - 0.02]
v ₂	[0.7, - 0.2]	(v₂, v₃)	[0.60, - 0.04]
		(v₂, v₄)	[0.50, - 0.03]
v ₃	[0.8, - 0.1]	(v₃, v₅)	[0.30, - 0.01]
		(v₃, v₁)	[0.40, - 0.02]
v ₄	[0.5, - 0.3]	(v₄, v₁)	[0.46, - 0.01]
v ₅	[0.4, - 0.2]	(v₅, v₁)	[0.38, - 0.02]

F₁ is bounded by the edges (v₁, v₂), (v₂, v₃) and (v₁, v₃),

F₂ is bounded by the edges (v₂, v₃), (v₂, v₄), (v₃, v₅) and has an infinite region (this face is an outer face),

F₃ is bounded by the edges (v₁, v₂), (v₂, v₄) and (v₁, v₄),

F₄ is bounded by the edges (v₁, v₅), (v₁, v₃) and (v₃, v₅).

Fig.3

Example of faces in BFPG.

Strengths of all these faces are calculated and listed in Table 2.

Table 2

Strengths of the faces of the BFPG shown in Fig. 3

Faces	F ₁	F ₂	F ₃	F ₄
Strengths	0.46	0.46	0.63	0.47

From Table 2 it is observed that, F₃ is a strong face. The face F₃ is surrounded by very p-strong edges. Therefore a conclusion can be drawn that, every strong face is surrounded by either very p-strong edges or very n-strong edges.

4 Bipolar fuzzy dual graph

In this section, we introduce the dual of a BFPG whose degree of planarity is 1. In bipolar fuzzy dual graph, a vertex corresponds to each face and there is an edge between two vertices if the faces corresponding to the vertices are adjacent by an edge. The formal definition is given below.

Definition 10. Let ξ = (A, B, V, E) be a BFPG with degree of planarity 1 where, $A = (V, μ_{A}^{P}, μ_{A}^{N})$ and $B = (V \times V, μ_{B}^{P}, μ_{B}^{N})$ . Again, let F₁, F₂, …, F_k be the strong faces of ξ. The bipolar fuzzy dual graph (BFDG) of ξ is a BFPG ξ′ = (A′, B′), where A′ is a BFS on V′ = {x_i, i = 1, 2, …, k}, x_i is considered for the face F_i of ξ and B′ is a BFS on V′ × V′. The positive membership values of vertices are given by the mapping $μ_{A^{'}}^{P} : V^{'} \to [0, 1]$ such that $μ_{A^{'}}^{P} (x_{i}) = max {μ_{B}^{P} (u, v) : (u, v)$ is an edge of the boundary of the face F_i}. The negative membership values of the vertices are taken as $μ_{A^{'}}^{N} : V^{'} \to [- 1, 0]$ such that $μ_{A^{'}}^{N} (x_{i}) = min {μ_{B}^{N} (u, v) : (u, v)$ is an edge of the boundary of the face F_i}.

Between two faces F_i and F_j of ξ, there may exist more than one common edge. Thus between two vertices x_i and x_j in BFDG ξ′, there may be more than one edge. We denote $μ_{B^{'}}^{l (P)} (x_{i}, x_{j})$ be the positive membership value of the l-th edge between x_i and x_j. The membership values of the edges of the BFDG are given by $μ_{B^{'}}^{l (P)} (x_{i}, x_{j}) = μ_{B}^{P} (u, v)^{l}$ where (u, v) ^l is an edge adjacent to each of the two faces F_i and F_j and l = 1, 2, …, s, where s is the number of common edges adjacent to each of the faces F_i and F_j (i.e. the number of edges between x_i and x_j). Similarly, we denote $μ_{B^{'}}^{l (N)} (x_{i}, x_{j})$ be the negative membership value of the l-th edge connecting x_i and x_j. The negative membership values of the edges of the BFDG are given by $μ_{B^{'}}^{l (N)} (x_{i}, x_{j}) = μ_{B}^{N} (u, v)^{l}$ where (u, v) ^l is an edgeadjacent to each of the two faces F_i and F_j and l = 1, 2, …, s, where s is the number of common edges adjacent to each of the faces F_i and F_j (i.e. the number of edges between x_i and x_j).

If there be any pendant edge in the BFPG, then there is a self loop in ξ′ corresponding to this pendant edge. The membership value of the self loop is same as to the membership value of the pendant edge.

Example 5. In Fig. 4, the dual of the BFPG shown in Fig. 3 (vertex and edge membership values are given in Table 1) is depicted. The filled circles are the vertices of BFPG and plain lines represent the edges of the BFPG. The circles represents the vertices of dual of the BFPG considered and dashed lines represents the edges of dual of the said BFPG. All the computations for vertex membership values and edge membership values of the dual of BFPG are shown as follows.

Fig.4

Bipolar fuzzy dual graph of a bipolar fuzzy graph.

Vertex x₁ is corresponding to the face F₁ which is bounded by the edges (v₁, v₂), (v₂, v₃) and (v₁, v₃).

Therefore, $\begin{matrix} μ_{A}^{P} (x_{1}) & = & max {0.5, 0.4, 0.6} = 0.6 \\ μ_{A}^{N} (x_{1}) & = & min {- 0.02, - 0.02, - 0.04} \\ = & - 0.04 . \end{matrix}$

Vertex x₂ is corresponding to the face F₂ which is bounded by the edges (v₂, v₃), (v₂, v₄), (v₃, v₅) and has an infinite region.

Therefore, $\begin{matrix} μ_{A}^{P} (x_{2}) & = & max {0.6, 0.5, 0.3} = 0.6 \\ μ_{A}^{N} (x_{2}) & = & min {- 0.04, - 0.03, - 0.01} \\ = & - 0.04 . \end{matrix}$

Vertex x₃ is corresponding to the face F₃ which is bounded by the edges (v₁, v₂), (v₂, v₄) and (v₁, v₄).

Therefore, $\begin{matrix} μ_{A}^{P} (x_{3}) & = & max {0.5, 0.5, 0.46} = 0.5 \\ μ_{A}^{N} (x_{3}) & = & min {- 0.02, - 0.03, - 0.01} \\ = & - 0.03 . \end{matrix}$

Vertex x₄ is corresponding to the face F₄ which is bounded by the edges (v₁, v₅), (v₁, v₃) and (v₃, v₅).

Therefore, $\begin{matrix} μ_{A}^{P} (x_{4}) & = & max {0.4, 0.3, 0.38} = 0.4 \\ μ_{A}^{N} (x_{4}) & = & min {- 0.02, - 0.01, - 0.02} \\ = & - 0.02 . \end{matrix}$

The edges of the dual of BFPG and their membership values are

$μ_{B}^{P} (x_{1}, x_{2}) = μ_{B}^{P} (v_{2}, v_{3}) = 0.6$ and $μ_{B}^{N} (x_{1}, x_{2}) = μ_{B}^{N} (v_{2}, v_{3}) = - 0.04$ ,

$μ_{B}^{P} (x_{1}, x_{3}) = μ_{B}^{P} (v_{1}, v_{2}) = 0.5$ and $μ_{B}^{N} (x_{1}, x_{3}) = μ_{B}^{N} (v_{1}, v_{2}) = - 0.02$ ,

$μ_{B}^{P} (x_{1}, x_{4}) = μ_{B}^{P} (v_{1}, v_{3}) = 0.4$ and $μ_{B}^{N} (x_{1}, x_{4}) = μ_{B}^{N} (v_{1}, v_{3}) = - 0.02$ ,

$μ_{B}^{P} (x_{2}, x_{3}) = μ_{B}^{P} (v_{2}, v_{4}) = 0.5$ and $μ_{B}^{N} (x_{2}, x_{3}) = μ_{B}^{N} (v_{2}, v_{4}) = - 0.03$ ,

$μ_{B}^{P} (x_{2}, x_{4}) = μ_{B}^{P} (v_{3}, v_{5}) = 0.3$ and $μ_{B}^{N} (x_{2}, x_{4}) = μ_{B}^{N} (v_{3}, v_{5}) = - 0.01$ .

Theorem 8. Let ξ = (A, B, V, E) be a BFPG with degree of planarity 1 containing only very p-strong edges. Then the dual of BFPG ξ′ is also a BFPG whose degree of planarity is 1.

Proof. Given ξ = (A, B, V, E) be a BFPG with degree of planarity 1 containing only very p-strong edges. Then every vertex of the BFDG of ξ′ is corresponding to a face which is surrounded by very p-strong edges. Also, the BFPG has no point of intersection and hence the corresponding BFDG contains no point of intersection. Hence, the BFDG ξ′ is a BFPG whose degree of planarity is 1. ■

Theorem 9. Let ξ = (A, B, V, E) be a BFPG with degree of planarity 1 containing only very p-strong edges and the BFDG of ξ be ξ′ = (A′, B′, V, E′). The positive membership values and negative membership values of the edges of ξ′ are equal to positive membership values and negative membership values of the edges of ξ respectively.

Proof. Let ξ = (A, B, V, E) be a BFPG with degree of planarity 1 containing only very p-strong edges. The BFDG of ξ is ξ′ = (A′, B′, V, E′) which is also a BFPG whose degree of planarity is 1. Let {F₁, F₂, …, F_k} be the set of strong faces of ξ. From the definition of BFDG, we know that $μ^{l (P)} (x_{i}, x_{j}) = μ_{j}^{P} (u, v)^{l}$ and $μ^{l (N)} (x_{i}, x_{j}) = ν_{j}^{N} (u, v)^{l}$ where (u, v) ^l is an edge adjacent to each of the two strong faces F_i and F_j and l = 1, 2, …, s, where s is the number of common edges adjacent to each of the faces F_i and F_j.

The number of edges of two BFG ξ and ξ′ are same as ξ has only very p-strong edges. For each edge of ξ there is an edge in ξ′ with same membership value. ■

5 Bipolar fuzzy planar graphs in image shrinking

Image segmentation is one of the important step in partitioning any digital image. Also, image segmentation is used to recognize digital objects. Therefore, image segmentation is helpful process in computer vision, remote sensing, etc. The aim of image segmentation is to extrapolate the objects for different interest from background of the image. Images are segmented by different procedures. In this section, a methodology is described for image shrinking by segmenting each portions of an image by using BFPG.

An image is characterized by pixels and it has some homogeneous sections. It can be represented by a graph described below. Each pixel is represented by a vertex and its positive membership value (negative membership value) is determined by its intensity i.e. gray value (dullness or non-intensity). Two neighbouring pixels (vertices) are joined by edges. The positive membership value (negative membership value) of the edge is determined by the dissimilarity (similarity) value of the corresponding pixels (vertices). Several methods are available to measure the dissimilarity or similarity between two pixels. One of them is used to measure the edge membership values. Thus the entire image (see Fig. 5 for example) is converted to a BFG (see Fig. 6) where each coloured vertices signifies the corresponding segmented coloured portion of the image of Fig. 5. The edge membership values for the edges of the graph shown in Fig. 6 is given in Table 3. Obviously, this graph is a BFPG. Also, in the representation, no edges cross other. So the degree of planarity of the graph is 1 (then the graph is strong BFPG). The background of the image is represented by the unbounded face. The BFDG of this BFPG can be drawn by the method described in the Section 4 (see Fig. 7). The vertex and edge membership values of the BFDG shown in Fig. 7 is given in Table 4.

Fig.5

An example of a color image for image shrinking.

Fig.6

BFPG corresponding to the image shown in Fig. 5.

Fig.7

Corresponding BFDG of the BFPG shown in Fig. 6.

Table 3

The edge membership values of the edges of graph shown in Fig.6

Edge	(a, b)	(a, c)	(a, d)	(a, e)	(b, c)
Membership Value	[0.7, - 0.3]	[0.3, - 0.4]	[0.5, - 0.5]	[0.4, - 0.5]	[0.3, - 0.3]
Edge	(b, e)	(c, d)	(c, g)	(d, e)	(d, g)
Membership Value	[0.4, - 0.3]	[0.3, - 0.4]	[0.3, - 0.4]	[0.4, - 0.5]	[0.5, - 0.5]
Edge	(e, f)
Membership Value	[0.4, - 0.6]

Table 4

Vertex and edge membership values of the BFDG shown in Fig. 7

Vertices	Membership Values	Edges	Membership Values
x	[0.5, - 0.5]	(x, y)	[0.5, - 0.5]
		(x, u)	[0.4, - 0.5]
y	[0.5, - 0.5]	(y, z)	[0.3, - 0.4]
		(y, v)	[0.3, - 0.4]
z	[0.7, - 0.4]	(z, w)	[0.7, - 0.3]
		(z, u)	[0.3, - 0.3]
w	[0.7, - 0.5]	(w, x)	[0.4, - 0.5]
		(w, u)	[0.4, - 0.3]
u	[0.5, - 0.6]	(u, u)	[0.4, - 0.6]
		(u, v)	[0.3, - 0.4]
v	[0.5, - 0.6]	(v, u)	[0.5, - 0.5]

Now, we define some related terms such as edge and kernel shrinking.

Let ξ = (A, B) be a BFG and (a, b) be an edge. Suppose, this edge is shrinked, then a new vertex, say c, is created such that all the edges incident to a and b are now incident to c, and the edge (a, b) is removed from the graph. Also the positive membership value of the vertex c is given by σ^P (c) = max {σ^P (a) , σ^P (b)}. The negative membership value of the vertex is given as σ^N (c) = max {σ^N (a),σ^N (b)}.

If more than a pair of vertices are shrinked, then an extended shrinking method, called kernel shrinking is used. Suppose the edges (a, b), (a, c), (a, d), (a, e) are to be shrinked simultaneously. Also let, σ^P (i) = m_i, σ^N (i) = n_i, where i = a, b, c, d, e be given and all these edges are shrinked to a single vertex, say h. The positive membership value of the vertex h is given by max {m_i, i = b, c, d, e} and negative membership value of the vertex is given by max {n_i, i = b, c, d, e}. Note that the vertices b, c, d, e are merged to the vertex h.

Collection of some homogeneous pixels forms a homogeneous section. Two pixels or two homogeneous sections are said to be nearly homogeneous section if the difference between the membership values of the pixels or sections is less than some pre-assigned positive number. Nearly homogeneous sections (non-considerable edges) are shrinked in different levels and each level is obtained from its previous level. From Fig. 6, it is clear that an image is divided into some regions and a region is bounded by lines. In the BFDG, the edges are the boundary of the images.

Let us consider Fig. 8. In level 1 of the image pyramid, each pixel is represented as vertex. Two continuous homogeneous or nearly homogeneous pixels or sections are shrinked into a single section. This process is done by edge/kernel shrinking on the BFG. Also, by this process, the corresponding edges of the dual graph are removed. The final shrinked image is shown in the top level of the pyramid (see Fig. 8).

Fig.8

An example of image pyramid.

5.1 Another application of BFPG

Suppose, in a city planning, city routes are to be so designed that the number of accidents should be minimized. Now, the number of accidents depends on many factors, like traffic system, road conditions, number of crossing between routes, etc. To solve this route planning problem, keeping in mind these factors, in a mathematical way, we convert the problem into a bipolar fuzzy graph model shown in Fig. 9.

Fig.9

Bipolar fuzzy planar graph corresponding to a city route planning.

In this bipolar fuzzy graph consider routes as edges and vertices are the transporting points. As the transporting points has no contribution to this problem, the membership values for all the vertices are taken as [1, - 1]. The positive membership values of edges are assigned some grade between 0 and 1 depending on chances of accidents in the corresponding route. The negative membership values of edges are assigned some grade between -1 and 0 depending on traffic system available for that route. The gradation corresponding to traffic system is conceptually taken as negative since a better traffic system can decrease the chances of accidents. Thus, the membership values of the edges (A, E) and (C, E) are [0.5, - 0.2] and [0.6, - 0.5] respectively, which means the traffic system of (C, E) is more strong than (A, E) and the chances of accidents for the route (C, E) is more than (A, E). Now, our problem is to find how much this model is acceptable in the context of accident? For this, we compute the degree of planarity. After usual computations, the degree of planarity for this graph is approximately 0.30. Greater the degree of planarity means the chances of accident is less and vice-versa. So, we conclude that there are approximately 70% chances of accident.

6 Conclusion

This study describes the bipolar fuzzy multigraphs, bipolar fuzzy planar graphs, and a very important consequence of bipolar fuzzy planar graph known as bipolar fuzzy dual graphs. A new term “degree of planarity” is defined. This parameter characterizes a bipolar fuzzy graph in many ways. Several properties can be investigated on regular bipolar fuzzy planar graph, irregular bipolar fuzzy planar graph.

References

Abdul-Jabbar

, Naoom

J.H.

and Ouda

E.H.

, Fuzzy dual graph, Journal Of Al-Nahrain University 12(4) (2009), 168–171.

Akram

, Bipolar fuzzy graphs, Information Sciences 181 (2011), 5548–5564.

Akram

, Bipolar fuzzy graphs with applications, Knowledge Based Systems 39 (2013), 1–8.

Akram

and Karunambigai

M.G.

, Metric in bipolar fuzzy graphs, World Applied Sciences Journal 14 (2011), 1920–1927.

Bhutani

K.R.

and Battou

, On M-strong fuzzy graphs, Information Sciences 155(1-2) (2003), 103–109.

Bhutani

K.R.

and Rosenfeld

, Strong arcs in fuzzy graphs, Information Sciences 152 (2003), 319–322.

Eslahchi

and Onaghe

B.N.

, Vertex strength of fuzzy graphs, International Journal of Mathematics and Mathematical Sciences 2006 (2006), 1–9.

Fazzolari

and Ishibuchi

, A review of the application of multiobjective evolutionary fuzzy systems: Current status and further directions, IEEE Transection on Fuzzy Systems 21(1) (2013), 45–65.

Ghorai

and Pal

, A note on “Regular bipolar fuzzy graphs”, Neural Computing and Applications 21(1) (2012), 197–205. DOI: 10.1007/s00521-016-2771-0, (2016).

10.

Ghorai

and Pal

, A study on-polar fuzzy planar graphs, International Journal of Computing Science and Mathematics 7(3) (2016), 283–292.

11.

Ghorai

and Pal

, Faces and dual of-polar fuzzy planar graphs, Journal of Intelligent & Fuzzy Systems 31(3) (2016), 2043–2049.

12.

Ghorai

and Pal

, Certain types of product bipolar fuzzy graphs, International Journal of Applied and Computational Mathematics 3(2) (2017), 605–619.

13.

Ghorai

, Pal

, Rashmanlou

and Borzooei

R.A.

, New concepts of regularity in product-polar fuzzy graphs,, International Journal of Mathematics & Computation^TM 28(4) (2017), 9–20.

14.

Lee

K.M.

, Bipolar-valued fuzzy sets and their basic operations, in: Proceedings of the International Conference, Bangkok, Thailand; 2000, pp. 307–317.

15.

Liang

and Mendel

J.M.

, MPEG VBR video traffic modelling and classification using fuzzy technique, IEEE Transection on Fuzzy Systems 9(1) (2001), 183–193.

16.

Lin

K.C.

and Chern

M.-S.

, The fuzzy shortest path problem and its most vital arcs, Fuzzy Sets and Systems 58 (1993), 343–353.

17.

Mathew

and Sunitha

M.S.

, Strongest strong cycles and theta fuzzy graphs, IEEE Transections on Fuzzy Systems 21(6) (2013), 1096–1104.

18.

Manjusha

O.T.

and Sunitha

M.S.

, Strong domination in fuzzy graphs, Fuzzy Information and Engineering 7(3) (2015), 369–377.

19.

Nagoor Gani

, and Shajitha Begum

, Degree order and size in intuitionistic fuzzy graphs, International Journal of Algorithms, Computing and Mathematics 3(3) (2010), 11–16.

20.

Nirmala

and Dhanabal

, Special planar fuzzy graph configurations, International Journal of Scientific and Research Publications 2(7) (2012), 1–4.

21.

Pal

, Samanta

and Pal

, Concept of fuzzy planar graphs, Proceedings of Science and Information Conference 2013, October 7-9, London, UK, 2013, pp. 557–563.

22.

Pramanik

, Samanta

and Pal

, Interval-valued fuzzy planar graphs, International Journal of Machine Learning and Cybernetics 7(4) (2016), 653–664.

23.

Pramanik

, Samanta

, Sarkar

and Pal

, Fuzzy φ-tolerance competition graphs, Soft Computing 21(13) (2017), 3723–3734.

24.

Pramanik

, Samanta

, Pal

, Mondal

and Sarkar

, Interval-valued fuzzy φ-tolerance competition graphs, Springer-Plus 5(1) (2016), 1981.

25.

Pramanik

, Pal

and Mondal

, Interval-valued fuzzy threshold graph, Pacific Science Review A: Natural Science and Engineering 18(1) (2016), 66–71.

26.

Rosenfeld

, Fuzzy graphs, in: Zadeh

L.A.

, Fu

K.S.

, Shimura

(Eds.), Fuzzy Sets and Their Applications, Academic Press, New York; 1975, pp. 77–95.

27.

Sahoo

and Pal

, Product of intuitionistic fuzzy graphs and degree, Journal of Intelligent & Fuzzy Systems 32(1) (2017), 1059–1067.

28.

Samanta

and Pal

, Fuzzy-competition graphs and-competition fuzzy graphs, Fuzzy Engineering and Information 5(2) (2013), 191–204.

29.

Samanta

and Pal

, Fuzzy tolerance graphs, International Journal of Latest Trends in Mathematics 1(2) (2011), 57–67.

30.

Samanta

and Pal

, Fuzzy threshold graphs, CIIT International Journal of Fuzzy Systems 3(12) (2011), 360–364.

31.

Samanta

and Pal

, Irregular bipolar fuzzy graphs, Inernational Journal of Applications of Fuzzy Sets 2 (2012), 91–102.

32.

Samanta

and Pal

, Bipolar fuzzy hypergraphs, International Journal of Fuzzy Logic Systems 2(1) (2012), 17–28.

33.

Samanta

, Pal

and Pal

, Some more results on bipolar fuzzy sets and bipolar fuzzy intersection graphs, The Journal of Fuzzy Mathematics 22(2) (2014), 253–262.

34.

Samanta

, Pal

and Pal

, New concepts of fuzzy planar graph, International Journal of Advanced Research in Artificial Intelligence 3(1) (2014), 52–59.

35.

Samanta

, Akram

and Pal

, m-step fuzzy competition graphs, Journal of Applied Mathematics and Computing 47(1-2) (2015), 461–472.

36.

Samanta

and Pal

, A new approach to social networks based on fuzzy graphs, Turkish Journal of Fuzzy Systems 5(2) (2014), 78–99.

37.

Samanta

and Pal

, Telecommunication system based on fuzzy graphs, Telecommunications System & Management 3(1) (2013), 1–6.

38.

Yager

R.R.

, On the theory of bags, International Journal of General Systems 13(1) (1986), 23–37.

39.

Zhang

W.R.

, Bipolar fuzzy sets, in: Proceedings of FUZZIEEE, 1998, pp. 835–840.