Given two integers V and E which represent the number of Vertices and Edges of a Planar Graph. The Task is to find the number of regions of that planar graph.
Planar Graph: A planar graph is one in which no edges cross each other or a graph that can be drawn on a plane without edges crossing is called planar graph.
Region: When a planar graph is drawn without edges crossing, the edges and vertices of the graph divide the plane into regions.
Examples:Â Â
Input: V = 4, E = 5Â
Output: R = 3Â
Â
Input: V = 3, E = 3Â
Output: R = 2Â
Â
Approach: Euler found out the number of regions in a planar graph as a function of the number of vertices and number of edges in the graph i.e.Â
Â
Below is the implementation of the above approach:Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
// Function to return the number// of regions in a Planar Graphint Regions(int Vertices, int Edges){Â Â Â Â int R = Edges + 2 - Vertices;Â
    return R;}Â
// Driver codeint main(){Â Â Â Â int V = 5, E = 7;Â
    cout << Regions(V, E);Â
    return 0;} |
Java
// Java implementation of the approachimport java.io.*;Â
class GFG {Â
    // Function to return the number    // of regions in a Planar Graph    static int Regions(int Vertices, int Edges)    {        int R = Edges + 2 - Vertices;Â
        return R;    }Â
    // Driver code    public static void main(String[] args)    {Â
        int V = 5, E = 7;        System.out.println(Regions(V, E));    }}Â
// This code is contributed by akt_mit |
Python3
# Python3 implementation of the approach Â
# Function to return the number # of regions in a Planar Graph def Regions(Vertices, Edges) : Â
    R = Edges + 2 - Vertices; Â
    return R; Â
# Driver code if __name__ == "__main__" : Â
    V = 5; E = 7; Â
    print(Regions(V, E)); Â
# This code is contributed # by AnkitRai01 |
C#
// C# implementation of the approachusing System;Â
class GFG {Â
    // Function to return the number    // of regions in a Planar Graph    static int Regions(int Vertices, int Edges)    {        int R = Edges + 2 - Vertices;Â
        return R;    }Â
    // Driver code    static public void Main()    {Â
        int V = 5, E = 7;        Console.WriteLine(Regions(V, E));    }}Â
// This code is contributed by ajit |
PHP
<?php// PHP implementation of the approachÂ
// Function to return the number// of regions in a Planar Graphfunction Regions($Vertices, $Edges){Â Â Â Â $R = $Edges + 2 - $Vertices;Â
    return $R;}Â
// Driver code$V = 5; $E = 7;echo(Regions($V, $E));Â
// This code is contributed// by Code_Mech?> |
Javascript
<script>Â
// Javascript implementation of the approachÂ
// Function to return the number// of regions in a Planar Graphfunction Regions(Vertices, Edges){Â Â Â Â var R = Edges + 2 - Vertices;Â
    return R;}Â
// Driver codevar V = 5, E = 7;Â
document.write( Regions(V, E));Â
// This code is contributed by itsokÂ
</script> |
4
Â
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
