The underground network of Barcelona, Spain. metropolitan subway maps are graphs that show the connectivity of the stations.  Source: TMB (Transports Metropolitans de Barcelona). Click on the image to enlarge it.

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:

• A set V of points called vertices or nodes.
  
  
• A set of pairs of vertices called edges or arcs that show which nodes are related.

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.

The problem of the Königsberg bridges.  The Pregel river crosses the city creating two islands. Is it possible to walk through the city crossing only once each and every one of the seven bridges that connect the four parts of the city?.  Source: graphic made by the author. Click on the image to enlarge it.	Euler's solution. The famous mathematician abstracted the details of the city and its bridges in order to keep only the information about connectivity giving birth to one of the first graphs. The degree of all the vertices is odd, what indicates that it's impossible to cross all of them only once. Source: graphic made by the author.

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:

• Basic rules: that refer to elementary aspects like avoiding overlapping among vertices, edges or both.

Basic Rules
KO	OK		KO	OK		KO	OK
Avoid overlapping among vertices			Avoid overlapping among edges			Avoid overlapping among vertices and edges

• Semantic rules: rules for vertex placement or routing of arcs and edges derived from the meaning of vertices and arcs. For example drawing the size of a vertex or the width of an arc depending of its importance. Usually they are user driven or derived from the information of its associated labels.

Semantic Rules
Align specified vertices			Place specified vertices along a curve			Draw vertices with specified size.
Place specified vertices at the boundary			Group specified vertices			Center specified vertices

• Structural rules: placement and routing rules related only to the features of graph theory. For example, placing the higher degree vertices in the centre of the drawing or minimising the total length of the edges, the number of crossings between edges, etc.

Structural Rules
KO	OK		OK	KO                     OK		KO	OK
Center high degree vertices			Place isomorphic subgraphs in identical layout			Placment in hierarchical layout
KO	OK		KO	OK		KO	OK
Minimise edge crossings			Look for balance in the dimensions of the drawing.			Organise symmetrically
KO	OK		KO	OK		KO	OK
Minimise corners of edges			Darw faces as convex poligons			Place children symmetrically
KO	OK		KO	OK		KO	OK
Avoid crossings among outlines			Uniform placement			Minimise the drawing area
KO	OK		KO	OK		KO	OK
Minimise total edge length			Minimise the difference in vertex sizes			Minimise average length of edges
All the drawings by the author, inspired in those existing on Sugiyama's book.

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: