As Koen pointed out there can be a lot of interesting things added to the svg maps. e.g.

• display the paths of interlinking in the svg - plot the path between two selected nodes - select two actors on the map, and then activate a show path functions
• which nodes are in the majority of paths between each of the pairs of nodes on the map (discovering the 'hubs')

With graph theoretic notions a lot more is possible. Below i summarised a couple of notions and theories that may be usefull for a better visualisation of what is going on in the issuemaps. These notions can all be applied on the result network so there is no need for adjustments of the crawler algorithm. As svg maps got an underlying structure of javascripts we can add/change the javascript so it calculates these notions on the fly by a simple click on a button in the map. This will not have a major impact on the loading time of the maps as the only extra loading is that of the javascript code.

terminology:

• vertex = node
• arc = edge
• path: a path between between two vertices v1 and v2 in a graph is a finite sequence of vertices and edges of the form v1, e1, v2, e2, ... , en, vn, where ek is an edge betwee vk-1 and vk In general, the vertices and edges in a path need not be distinct.
• graph: structure consisting of a finite set V of vertices and a finite set E of edges such that each edge e is associated with a pair of vertices v and w

nodes:

• domain and range
• reflexive relations
• symmetric relations
• transitive relations
• anti-symmetric relations
• equivalence relations (symmetric, transitive en reflexive)
• maximum and minimum relations
• implications, if then relations
• converse relations
• which sites are included / excluded in a given cluster of size n
• strongly connected pair: if each vertice in the pair is connected to the other
• unilaterally connected pair: if one of the vertices is connected to the other

paths:

• simple: if its vertices and edges are distinct
• closed path: is there is a path between a vertex and itself
• existence problem: does there exist at least one arrangement of a given kind?
• counting problem: find the number of possible arrangements or configurations of a certain pattern
• optimization problem: find the most efficient arrangement of a given pattern

graphs:

• complete: is there an edge between every pair of vertices?
• is the digraph complete? is the underlying graph complete
• is there a bipartite graph: can the vertices be partitioned in two disjoint sets V and W such that each edge is an edge between a (group of) vertex V and a vertex W.
• is there a bipartite digraph: is every arc from a vertex in V to a vertex in W?
• complete bipartite graph: if there is an edge between every vertex in V and every vertex in W
• connected graph: if there is a path between every pair of vertices in it
• the graph is not connected if it is not possible to label all the n vertices by a depth first search technique
• circuit: if al the edges in the graph are distinct
• cycle: if all the vertices in a circuit are distinct
• bridge: an edge in a connected graph if the removal of that edge, but not its end vertices, makes the graph disconnected
• acyclic graph or forest: a graph with no cycles. A forest is a graph in which any two vertices are connected by at most one path. An equivalent definition is that a forest is a disjoint union of trees (hence the name).
• tree, connected forest: a tree is a graph in which any two vertices are connected by exactly one path.
• stronly orientable graph: if and only if the directed graph is connected and bridgeless
• interval graph: is a graph that captures the intersections among a set of intervals on the real line. That is, the nodes of the graph are the intervals and there is an edge corresponding to each pair of intersecting intervals. Interval graphs are useful in modeling resource allocation problems in operations research. Each interval represents a request for a resource for a specific period of time.
• planar graph: is a graph that can be embedded in a plane so that no edges intersect.
• Regular graph has all vertices of the same valency. An edge connects two vertices; these two vertices are said to be incident to the edge. The valency (or degree) of a vertex is the number of edges incident to it, with loops being counted twice.
• a clique in a undirected graph G, is a set of vertices V' such that for every two vertices in V, there exists an edge connecting the two. Additionally, this means that a clique is simply a complete subgraph of G. The size of a clique is the number of vertices it contains. The clique problem refers to the problem of finding the largest clique in any graph G. This problem is NP-complete, and as such, many consider that it is unlikely that an efficient algorithm for finding the largest clique of a graph exists. The opposite of a clique is an independent set. If we already know that the independent set problem is NP-complete, then it is easy to prove, as the size of the largest clique is the same as the size of the largest independent set in the inverse graph.

• eularian path: if every edge of the graph appears as an edge in the path exactly once
• eularian circuit: a closed eularian circuit

• hamiltonian path: a path between two vertices in a graph that passes through each vertex exactly once
• hamiltonian cycle: a closed path that passes through each vertex exactly once and in which all edges are distinct
• hamiltonian graph: if the graph has a Hamiltonian cycle
• There are no clear ways known to see if a given graph has a Hamiltonian cycle, it mostly boils down to check if it has a lot of edges.

for more information see

• http://en.wikipedia.org/wiki/Graph_(mathematics) wikipedia on graph theory
• http://en.wikipedia.org/wiki/Glossary_of_graph_theory wikipedia glossary of graph theory
• http://en.wikipedia.org/wiki/List_of_graph_theory_topics wikipedia list of graph theory topics

-- ErikBorra - 10 May 2004