Combinatorial Hypermaps vs Topic Maps

1. A Bit of History

The first paper of graph theory is probably the one published by L. Euler in 1736 on the "Königsberg bridges" problem [11]. Although the first problems which have led to the development of graph theory were almost puzzles, they succeeded in gaining the attention of mathematicians, leading to a very productive field of mathematics.

The "Königsberg bridges" problem and the knight problem, with which Euler and Vandermonde pursued the "position study" initiated by Leibniz. This study, augmented by Euler formula (relating the number of edges, nodes and faces of a polyhedron) led to the birth of the new field of mathematics, which name has been suggested by Listing: the Topology.

This later science developed from the study of the generalizations of Euler formula, mainly through the works of Cauchy [6] and Lhuillier [26]. Is autonomous development between 1860 and 1930 conversely fertilized the graph theory, through the works of Jordan, Kuratowski [25] and Whitney [39]. Both fields also proceeded from the use of the techniques of modern algebra. Such a contribution first appeared in the work of G.R. Kirchhoff on the flow theory.

Topological graph theory mainly developed around 1968, from the resolution by Ringel and Youngs [29] of Heawood's conjecture on map coloring [21]. The techniques used for this resolution have then been applied to number of embeddings problems and Arthur White's book ("Graphs, Groups and Surfaces", [38]) made this new field accessible.

With the first graph drawing algorithms, appeared a new field of study in the topological graph theory, namely the Graph Drawing. This field is mainly dedicated to the construction of geometric representation of an abstract graph or network (see [8] for an annotated bibliography, and [9] for an survey). Researches in graph drawing have been quite prolific the last two decades. Recent advances in topological graph theory and in partial order theory accelerated this development and led, in 1993, to the first international Graph Drawing Conference specifically dedicated to it, which took place at Sèvres and organized by the CAMS (CNRS, EHESS).

Further historical informations may be found in [4].

2. Graphs, Maps, Hypergraphs and Hypermaps

The term graph, as the name of a system of points (nodes or vertices) and lines (arcs or edges), came from a chemistry paper published by Sylvester in Nature in 1878.

Formally, a graph is an ordered pair (V,E), where V is a finite, nonempty set whose elements are termed vertices, and where E is a set of unordered pairs of distinct vertices of V. Each element {p,q} in E is called an edge and is said to join p and q (some authors allow an edge to join a vertex to itself, such an edge being termed loop). For a study of basic properties of graphs, we refer the reader to [1] [3] [5] [20] and [16].

Any graph may be represented using a normal drawing: to each vertex corresponds a point, and to each edge correspond an arc joining the points associated with the vertices joined by the edge. Moreover, two edges are allowed to intersect at most once. Whenever no two edges intersect (except maybe at their extremities), the drawing is termed an embedding. Any embedding on a closed compact surface is characterized by the local circular orders of the edges around the vertices; The collection of these circular orders is a map . This construction and the characterization theorem for maps has been first introduced (in dual form) by Heffter (1891, [22]) and extensively used by Ringel in the 50s. Independently, the primal form has been published by Edmonds in (1960, [10]) and its study has been made more accessible by Youngs (1963, [40]). The general modern form of the result has been given by Gross and Alpert (1974, [17]).

Hypergraph theory is a part of the general study of combinatorial properties of finite families of finite sets. Hypergraphs are natural extensions of graphs: elements correspond to nodes, sets correspond to edges which are allowed to connect more than two nodes. Hypergraph theory appeared in the 60s (the term hypergraph has been suggested by Berge at the Tihany Colloquium in 1966) to extend, simplify and unify the results of graphs, in the context of a fast-growing economical interest of discrete mathematics. Hypergraphs turn out to be particularly efficient in discrete optimization problems, offering a large set of minimax-type theorems. For an introduction to hypergraphs, we refer the reader to [2] and [16].

>From a generalization by Zykov [41] of the concept of planarity (existence of an embedding on the plane) to hypergraphs, the relationship between graphs and maps has been extended to a relationship between hypergraphs and hypermaps ( [7] [37], see also [24] and [38]). Formally, a hypermap is an ordered pair of permutations of a finite set F of flags generating a group acting transitively on F. The permutations correspond intuitively to the circular orders of arcs representing the incidences (the flags) around the hypernodes (the elements), and around the hyperedges (the sets), respectively.

3. Applications Fields

We shall give here a fast overview of the diversity of algorithmic problems encountered within the graph (or hypergraph) theory.

• Traveling salesman

  The traveling salesman problem is the problem of a salesman who, starting from his home city, has to find the shortest tour that takes him exactly once through each of a number of other cities and then back home.

• Vehicle routing

  The single-depot vehicle routing problem with time windows basically correspond to the following situation: a number of vehicles are stationed at a single central depot and must serve a prescribed set of dispersed customers. Each vehicle has given capacity; each customer has a given demand and must be served within a specified time interval; the travel times between the depot and the customers are given. The problem is to find a collection of routes for the vehicles, starting and ending at the depot, and collectively visiting all customers, while respecting the capacity constraints of the vehicles and the time constraints of the customers, while minimizing the total travel time.

• Clique partitioning

  The problem is to partition a set of persons into mutually disjoint groups in such a way that two person are allocated to the same group if the sets of problems on which they worked are similar, and to different groups if the sets are dissimilar.

• Minimum cost flow

  The problem is to find a minimum cost flow from a given source s to a given sink t in a network, while respecting given capacities on the arcs, from the knowledge of the cost function specifying the cost of sending an amount of flow for each of the arcs of the network.

• Maximum flow/Minimum cut

  The problem is to find a maximum flow from a given source s to a given sink t in a network with given capacities or, equivalently, to find a minimum cut of the network separating s from t.

• Subgraph isomorphism

  The problem is to locate each of the isomorphic copies of some given small graph or hypergraph in a big one.

• Automorphism enumeration

  The problem is to exhibit all the "symmetries" a a graph.

• Graph drawing

  The problem is to compute a geometric drawing of a graph or a hypergraph on the plane, while respecting some orientation or planarization constraints.

4. Application to Topic Maps

Techniques from topological hypergraph theory may be easily applied to Topic Maps by considering the following correspondence between Topic Maps and hypermaps:

Topic Maps

topic

hypernode, vertex

association

hyperedge, edge

instance of "topic in association"

flag

type, role

color

occurrence, metadata

attached value or property

You may notice that the fundamental building bloc of hypermaps, the flag has no termed equivalent in the universe of Topic Maps.

The interest of the several types of applications described in the previous section should be clear, when considering several possible types of Topic Maps, as:

• Financial Topic Maps,

• Historical Topic Maps,

• Organizational Topic Maps,

• Structural Topic Maps,

• Knowledge Topic Maps,

• etc.

Moreover, the data structures used to implement hypergraph algorithms are naturally effective for Topic Maps.

5. Concluding Remark

There is an higher interest in the hypermap approach of Topic Maps (and more generally in the combinatorial approach of Semantic Web), which is mainly related to:

• two centuries old combinatorial theory, which slowly has lightened the operational and efficient definitions and mathematical tools,

• a huge set of algorithmic studies, from the combinatorial optimization to graph drawing,

• efficient data structures elaborated since two decades

Design and Development by deepX Ltd.