Graph Abstractions as the basis of an Extensible Graph Editing Tool

Paper by Niels C. Larsen, Martin K. Molz and Kurt Nørmark: ps, pdf.

Abstract

A wide variety of computer tools are based on graphs. In many modern applications, graphs also play an important role in the user interfaces of the tools. Although such tools, in a foundational sense, are based on the mathematical graph concept, it is frequently the case that a richer and more practical graph concept is needed for user interface purposes. The richness comes from several sources, but the variation in the ways the edges are rendered is of particular importance. In this paper we will demonstrate that a variety of relationships among nodes (one-to-one through many-to-many) can be understood as composite edges, the parts of which are particular kinds of subgraphs of the overall graph. We will also demonstrate how composite edges can be structured and managed in terms of two design patterns known from the area of object-oriented design. The paper is organized in two parts, the first of which lays the mathematical foundation of the latter.
See also The Ginger home page and Kurt Nørmark's home page.