A Review on Applications of Graph Theory in Computer Science

Mathematics had a significant influence in this. It is vital to understand graph theory, which is employed in structural models. In the present context, new advances and improvements in these disciplines are spurred by the functional design of numerous things and technologies. In 1735, the bridge of Koinsberg issue sparked interest in field map theory for the first time. An overview of graph theory applications in a wide range of domains is provided in this work, however the focus is mostly on computer science applications based on visual conceptual ideas. The Eulerian Map principle has its origins in the Koinsber bridge issue, which is where graph theory got its start.1

The Eulerian map was developed by Euler as a solution to the Koinsberg Bridge puzzle. Complete graph and bipartite graph were invented in 1840 by A. F. Mobius, who demonstrated that they are planar by solving leisure puzzles with them. A connected loop without loops was first proposed by Gustav Kirchhoff in 1845, and he employed visual theoretical principles from electrical network and circuit estimates to support his theory of a circle. Thomas Gutherie discovered the four-color issue in 1852. It was for this reason that in 1856, Thomas P. Kirkman and William R. Hamilton began researching Polyhydra cycles and developing the Hamiltonian chart theory. On a query from 1913, H.Dudeney provided an amusing answer in the form of an elaborate riddle. The four-color issue was found by Kenneth Appel and Wolfgang Haken, but it wasn't solved for another century. This time period is regarded to be the beginning of visual philosophy.

Discrete mathematics encompasses all of Graph Theory. In computer science and many other subjects, graphs are employed as a mathematical framework. The focus is on two key areas of concern. Graph theory is used to characterize the basic problem in terms of connectedness, cut, route, and flow, as well as colororing issues and other graph drawing concepts. Application-related issues are around experimental study and implementation of graph theory methods. In order to convey information visually, graphs are essential. Many words' worth of information can be displayed in a single graph. Graphic theory may readily address many issues that are thought to be difficult to determine or apply. Graph theory encompasses a wide variety of graph types. There is a correlation between each graph type and a certain attribute. Many apps for troubleshooting make use of one of these graphs. An important part of graph theory is the study of how to create a mathematical model that has a pair-wise link between its objectives. This is done through the study of graphs. There are two components to a graph. There are two sets of points (vertices and edges) Graphs allow us to define and solve real-world issues while providing a wide range of strategies and flexibility. The following are some of the numerous characteristics available in graphs:2

• Helps in decision making.

As far back as 250 years, graph theory has had a theory in place. Leonhard Euler, a well-known mathematician, had a problem traversing the seven bridges of Konigsberg, which ushered in the period of graph theory. He's been searching for a stroll in Konigsberg that connects seven bridges since he was a kid.3 Since then, it's been dubbed "the first graph theory issue." Because of the wide variety of applications that graph theory has seen since its inception, it has grown and matured. Numerous prominent mathematicians have found it easy to solve every difficult problem in the world. It was a pioneer in discovering answers to many unresolved issues because of its way of portraying every problem using drawings or graphs. In computer science, graph theory is becoming more and more relevant. Graphs may be used to make the development and testing of any software or program easier. A major benefit of directed graphs is that they can be used to model the control and data flows in any program, regardless of complexity. Other applications include microprocessor design, circuits, operating system scheduling challenges, file management in a database system, and data flow control between networks. The theory of graphs had led to the development of graph theoretical algorithms in the world of computers. Many computer science problems can be solved with the help of this methods.4 Some algorithms are as follows:

Graph theory has been used in a wide range of fields, including transportation issues. VLSI design applied to social networking systems. An emphasis on graphs with nodes that are physically located on the plane or higher dimensional spaces is being paid. Objects like road, rail, and airline networks are well-recognized natural representations. Edges in geometric representations are clearly defined by their length in this article, which focuses on the unique property of the geometric representation of graphs known as rigidity. Applications: Graph stiffness may be used in a variety of ways. There are always new domains being added from many fields of research and technology. It's possible that the mobile devices in a reconfigurable sensor network must retain a specified configuration in order to collect data. A regularly spaced polygon, for example, is a desirable structure for reconfigurable sensor networks. In multirobot networks, pattern pattern. The idea of graph stiffness and the problem of pattern development are inextricably linked.

Network Engineering: There is a wide range of uses for graph theory when it comes to networking. Graph representation and network theory are both taken into account while examining the use of graph theory in networking. For example, it provides a distinct perspective; it simplifies the problem; and it provides a more accurate description. However, network theory provides a collection of methodologies for the analysis and application of network theory in the context of a graph. In computing, there is no distinction between the terms "graph" and "network". Both describe a structure with nodes (also known as "dots") and edges (also known as "vertices").6 A wide variety of graphs and networks exist, each with varying degrees of structure. The usefulness of these two words allows for a distinction to be drawn between them. Mathematicians use the term graph, while physicists use the term network. A graph-based networking technique, Additional uses for graph theoretic principles include network engineering, where the terms "graph" and "network" are interchangeable, such as connecting devices, gathering data, reducing consumption, traffic analysis, and finding the shortest path. Links and lines are utilized in networking, whereas nodes and edges are used in graph theory. Mathematicians use the term graph, while engineers use the term network. Electrical Engineering: Source, Wires, Load, and Switches create a closed loop in an electrical circuit. Switching on the power causes a full electrical circuit to occur. The negative terminal of the power source is where the current flows from then on. Solving electrical circuit problems with the use of Graph Theory is what we do here. Electric circuit application of graphs, We'll have a look at yet another use of graphs in the electric field using the definitions of a link and cycle matrix.7 Computer Science Engineering: Computer science can benefit from the study of graph theory. In this article, the various ways graphs are put to use in computer engineering are discussed. In addition to that, a few other examples are given. Data structure, image processing, web design, data mining, clustering, etc. are some examples. Digital Image Processing: Digital image processing techniques are used to extract information from photos through image analysis. Improvements to image processing can be made through the use of a graph theoretic method. Graph search strategies in segmentation may be used to

• To determine the picture's alignment.

• Finding mathematical restrictions, such as entropy, may be done with the minimal spanning tree.

• For example, finding distance transforms of pixels and utilizing shortest route techniques to compute distance between inside pixels.

Operating System: Many practical issues in operating systems may be handled using graphs, including work scheduling and resource allocation. An operating system's job scheduling method involves distributing system resources to a variety of different activities. The graph coloring idea may be used to CPU job scheduling difficulties, where tasks are thought to be vertices on a graph and an edge connects them, as well as a one-to-one link between graphs that can be scheduled. Operating system: Graphing.9

• Graphs are used to depict system processes.

• A powerful query tool for graphs

• In the context of object-oriented programming, graph databases are ideal for storing associative data sets.

Chemistry: Graphs are used to represent molecular structures for computer processing. Bonds link the vertices of an atom network, which is referred to as a "edge." Compound characteristics are used to generate these structures, which are subsequently subjected to further examination and processing. Molecule structure may be studied, as well as the degree of similarity between different molecules.10 Web Page Designing: When creating a website, a graph comes in handy. While online pages are represented by vertices in the network, hyperlinks represent edges. You may think of it as a "web graph." Graphs may also be seen in online forums and discussion groups. In this diagram, the vertices indicate different kinds of things. This means that every vertex that represents one type of item is linked to every vertex that represents another. In graph theory, a complete bipartite graph is one that has all of its edges connected. When developing a website, we may use graph representation to gain the following results:

• Search and discovery of the community.

• Evaluating a website's usefulness and building links in graph form.

• Provides quick identification of all connected components.

Mathematically speaking, a graph is an abstraction that may be used to solve a wide range of issues. A graph is made up of vertices and edges, with an edge serving as a link between two vertices on the graph. (V,E) is a collection of nodes and a binary relation on that node. Graph: G = (V, E) is a collection of V nodes connected by E links. This graph description is a bit ambiguous; it doesn't specify what a vertex or an edge means. The cities and roads that connect them might be cities, or they could be online sites with links. Path: It is possible to organize the vertices of a path so that two points are only near if they are listed consecutively. Undirected Graph: An unordered, transitive relationship between two nodes is represented by the graph's edges. Plain lines or arcs are used to represent these types of edges.

Directed Graph/Digraph: The edges of a graph represent the non-transitive, ordered relationships that exist between the nodes. An arrowhead is placed at the end of a line or arc to represent these edges.

Loop: Unlike other edges, a loop links two or more points. In street network graphs, loops are not utilized very often.12 Un-weighted edge: In a graph where all of the relationships represented by the edges are regarded to be equal Plain lines or arcs are used to represent these types of edges. Weighted edge: Distance or lag time, for example, are reflected in the weighted edges that connect the nodes in the graph. In most cases, these edges are

In the realm of computer science, algorithms play a critical role in the creation and improvement of software programs. To ensure that their programs are error-free, software developers typically design their programs from the ground up before beginning development. Algorithm design is greatly aided by the use of GT. Graph-based algorithms have been used to tackle a variety of real-world challenges. These include: (1) algorithms for finding a node in a directed or undirected graph using Depth First Search (DFS) and Breath First Search (BFS) in the data structure; (2) the MST (Minimum Spanning Tree) algorithm; (3) algorithms for locating the shortest path through a network; (4) the graph planarity algorithm; and (5) algorithms for visualizing data transfer in complex applications. It is possible to work with graph theory topics using any number of different computer programming languages. The following is a list of some of the graph programming languages:13

We can leverage GT principles in network security to model real-time/offline network threats. For instance, and edges should be able to function as routing servers and connect other routing servers. In the event that this is not the case, a worm circulation solution must be developed, and a network security plan against worm circulation can be devised. A graph G is said to cover another graph G if every vertex of the first graph G appears on at least one of the edges of the second graph G.

A wireless sensor network (WSN) may be used for a variety of purposes, including military applications and the tracking of various mobile objects. The Voronoi graph is an unique sort of graph that decomposes a metric space based on distance to find the different collection of objects inside the space. A Voronoi graph is built in a plane using polygons in which distinct nodes are given as sensors and the edges of the polygon are viewed as the range of each sensor.. The WSN as a Voronoi graph is depicted in this diagram. Sensor locations are represented by the alphabets a-p and the coverage areas are represented by cells. The placement of sensors and the extent to which they cover an area of interest (AOI) may be accurately predicted using graphs.

Figure 4: Pictorial overview of a wireless sensor network (WSN) in a graph form

The popularity of social networking sites like Facebook and Twitter is skyrocketing as a result of advances in information and communication technology (ICT). Adolescents are increasingly using social media (SN) to exchange information and communicate. The SN is also being used by businesses and service providers for different objectives, including as recommending new brands and running marketing. Analytics organizations largely rely on SN user data to analyze social trends, user views towards new brands, intent mining, sentiment analysis, and personality profiling. Studies discuss in detail the SN-related principles, applications, usage, and technical breakthroughs. If U and V are lists of users or entities in an SNS and their connections between them are shown in a graph G (U, V), then the SNS is described as a network with many nodes and many edges.15 A Facebook buddy, lover, family member, or sibling relationship might be the basis of the connection.

The computer science and social networks, both of which make use of graph theory ideas (GT). The analysis of graph attributes and the selection of the most appropriate combination of graphs in light of the situation at hand will be helpful to a wide range of academics. Beginner researchers can benefit from a well-illustrated overview of GT's prospective applications in CS and SN fields, which can help them understand its ideas and current use. Analysis of visual theoretical principles in diverse sectors of computer use requires the use of scientific design thinking. Analysts can explain the importance of graph theory and how it is being used in computers, as well as some of their own research interests. The students of computer science to get a deeper understanding of graph theory and its connection to other computer science courses, such as operating systems, networks, databases, software engineering, biology, chemistry, operation research, and digital image processing.

1. Ain, B.J.; Obermayer, K. Graph quantization. Comput. Vis. Image

Underst. 2018, 115, 946–961. Appl. 2020, 539, 122894.

3. Sahu, S.; Mhedhbi, A.; Salihoglu, S.; Lin, J.; Özsu, M.T. The ubiquity of large graphs and surprising challenges of graph processing: Extended survey. VLDB J. 2019, 29, 1–24 4. Can, U.; Alatas, B. A new direction in social network analysis: Online social network analysis problems and applications. Phys. A

Stat. Mech. Appl. 2019, 535, 122372. 5. Kumar Bisen, Sanjay. "Application of Graph Theory in Transportation Networks." International Journal of Scientific Research and Management 5.7 (2017): 6197-6201. 6. N. Bhandri and A. Sharma, Graph Theory and its Applications in Diverse Domain: A Survey Paper, International Journal of Contemporary Technology and Management 6(7) (2017), 1-6. 7. B. Tosuni, Graph Theory in Computer Science-An Overview, International Journal of Academic Research and Reflection 3(4) (2016), 55-62. 8. R. P. Singh and Vandana, Application of Graph Theory in Computer Science and Engineering, International Journal of Computer Applications 104(1) (2017), 10-13. 9. Singh, Rishi Pal. "Application of graph theory in computer science and engineering." International Journal of Computer Applications 104.1 (2017). 10. S. S. Sonawane and P. A. Kulkarni, Graph based Representation and Analysis of Text Document: A Survey of Techniques, International Journal of Computer Applications (IJCA) 96(19) (2017), 1-8. 11. Samai‘la Abdullah, An Application of Graph theory to the Electric Circuit Using Matrix Method, ISRO Journal of Mathematics, 10(2),MarApr 2017. 12. Rishi Pal Singh, Vandana, Application of Graph Theory in Computer Science and Engineering, 104(1), October 2017. 13. Patel, Pranav, and Chirag Patel. "Various graphs and their applications in real world." International Journal of Engineering Research and Technology 2.12 (2018): 1499-1504. 14. Sarma, S. Venu Madhava. "Applications of graph theory in human life." International Journal of Computer Application 1.2 (2018): 21-30. 15. B. Sadavare, R V Kulkarni, A Review of Application of Graph Theory for Network, International Journal of Computer science and Information technologies, 3(6), 2018.

Multanimal Modi PG College, Modinagar, District- Ghaziabad, State- Uttar Pradesh