|InfoVis.net>Magazine>message nº 137||Published 2004-01-05|
|También disponible en Español|
The digital magazine of InfoVis.net
Graphs are mathematical artefacts that allow us to visually express, in a simple and effective form, the relationships that appear between elements of a very diverse nature. A simple graph consists of two sets:
In a more informal way we can say that a graph is a set of nodes with links between them called edges or arcs.
In a simple graph there’s only one arc between two nodes. If there’s more than one arc we talk about a multigraph. If arcs can be followed in only one specific direction but not in the other we call it a directed graph or digraph and arcs become edges. If arcs begin and end in the same node making a loop the resulting graph is called a pseudograph.
Despite a graph seeming a very elementary structure, there are many features of graphs whose study has lead to a complete mathematical theory. (For more information you can take a look at the graph glossary by Chris Caldwell or the introduction to graph theory of the wikipedia).
It was Leonhard Euler who invented graphs as a powerful and elegant way to solve the problem of Königsberg bridges.
Königsberg (today known as Kaliningrad in Russia) was in the time of Euler (18th century) a Prussian city crossed by seven bridges. At that time the unsolved question of going through the city crossing each and every bridge only once was at stake. If we draw the city schematically we can see that the bridges join four different pieces of land. Searching by trial and error gave no result.
Euler made a further abstraction of the problem representing the four pieces of land as points, drawing an arc for every bridge connecting them. He called degree of a vertex to the number of arcs joining it and he observed that the degree of each vertex visited in a continuous path had to be even (one arc goes in, the other goes out). This is so except for two points: the one where you begin the journey and the one where you end it. If you begin and end at the same point, then all the vertices must have even number degree.
In the Königsberg problem the degree of all the vertices is 3, this is an odd number, meaning that there’s no solution to the problem. No path could visit all the city crossing all the bridges only once.
The interest of this example is in that besides giving birth to a powerful mathematical theory, graphs can be drawn resulting in very intuitive plots, specially when you deal with a low number of vertices. We all know some examples of graphs, like the organisation charts that explicit the formal structure of a company, genealogy trees or the electronic circuits of computer chips. They are used regularly to solve problems related to the efficiency of transport, in sociology, electronics, fraud detection and, in general, in those fields where connectivity is important.
In fact we all live in an interconnected society where, by definition, networks (just a form of directed graphs in which every edge has an associated value) increasingly make up part of our daily experience. Internet is the archetype of the network and its connectivity reaches all of us.
As an anecdote, it appears that the capture of Saddam Hussein was made possible in part thanks to the work of the construction of the graph depicting his support network, based on the functional relations with members of his party but, above all, on the tribal and family relationships that link him to his natal city of Tikrit. See for example "Learning to break the rules" by Bruce Berkowitz or "How Army Sleuths Stalked the Adiviser who led to Hussein" by Eric Schmitt both for The New York Times. (I owe the information to Jim Wise)
It’s not easy to properly draw a graph. In fact it’s not easy to adequately represent anything useful. Nevertheless the study of the many possibilities that the automating representation of graphs provides has lead to a series of rules that is worth mentioning here.
According to Kozo Sugiyama in his book “Graph Drawing and Applications”* the static rules (to draw only one graph instead of a succession of them in dynamic form) can be divided into:
These rules pursue the optimisation of the drawing, trying to find the simplest and clearest possible way to draw it. That this is not easy becomes clear by looking at the advances shown every year in the “Graph Drawing” conferences (this year’s will take place in New York next September)
“Graph Drawing and Applications” by Kozo Sugiyama, World Scientific Series on Software Engineering and Knowledge Engineering Vol 11.
Links of this issue:
Subscribe to the free newsletter