Editing Graph theory (section)

== Representation ==
A graph is an abstraction of relationships that emerge in nature; hence, it cannot be coupled to a certain representation. The way it is represented depends on the degree of convenience such representation provides for a certain application. The most common representations are the visual, in which, usually, vertices are drawn and connected by edges, and the tabular, in which rows of a table provide information about the relationships between the vertices within the graph.

=== Visual: Graph drawing ===
{{main|Graph drawing}}
Graphs are usually represented visually by drawing a point or circle for every vertex, and drawing a line between two vertices if they are connected by an edge. If the graph is directed, the direction is indicated by drawing an arrow. If the graph is weighted, the weight is added on the arrow.

A graph drawing should not be confused with the graph itself (the abstract, non-visual structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practice, it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.

The pioneering work of [[W. T. Tutte]] was very influential on the subject of graph drawing. Among other achievements, he introduced the use of linear algebraic methods to obtain graph drawings.

Graph drawing also can be said to encompass problems that deal with the [[Crossing number (graph theory)|crossing number]] and its various generalizations. The crossing number of a graph is the minimum number of intersections between edges that a drawing of the graph in the plane must contain. For a [[planar graph]], the crossing number is zero by definition. Drawings on surfaces other than the plane are also studied.

There are other techniques to visualize a graph away from vertices and edges, including [[circle packing theorem|circle packings]], [[intersection graph]], and other visualizations of the [[adjacency matrix]].

=== Tabular: Graph data structures ===
{{main|Graph (abstract data type)}}
The tabular representation lends itself well to computational applications. There are different ways to store graphs in a computer system. The [[data structure]] used depends on both the graph structure and the [[algorithm]] used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for [[sparse graph]]s as they have smaller memory requirements. [[Matrix (mathematics)|Matrix]] structures on the other hand provide faster access for some applications but can consume huge amounts of memory. Implementations of sparse matrix structures that are efficient on modern parallel computer architectures are an object of current investigation.<ref>{{Cite book | last1 = Kepner | first1 = Jeremy| last2 = Gilbert | first2 = John| title = Graph Algorithms in the Language of Linear Algebra| date = 2011| pages = 1171458|isbn=978-0-898719-90-1| publisher = SIAM | url = https://my.siam.org/Store/Product/viewproduct/?ProductId=106663}}</ref>

List structures include the [[edge list]], an array of pairs of vertices, and the [[adjacency list]], which separately lists the neighbors of each vertex: Much like the edge list, each vertex has a list of which vertices it is adjacent to.

Matrix structures include the [[incidence matrix]], a matrix of 0's and 1's whose rows represent vertices and whose columns represent edges, and the [[adjacency matrix]], in which both the rows and columns are indexed by vertices. In both cases a 1 indicates two adjacent objects and a 0 indicates two non-adjacent objects. The [[degree matrix]] indicates the degree of vertices. The [[Laplacian matrix]] is a modified form of the adjacency matrix that incorporates information about the [[degree (graph theory)|degrees]] of the vertices, and is useful in some calculations such as [[Kirchhoff's theorem]] on the number of [[spanning tree]]s of a graph.
The [[distance matrix]], like the adjacency matrix, has both its rows and columns indexed by vertices, but rather than containing a 0 or a 1 in each cell it contains the length of a [[shortest path]] between two vertices.