Designing Graph Drawings by Layout Graph Grammars

Brandenburg, Franz J. (1995) Designing Graph Drawings by Layout Graph Grammars. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 416-427(Official URL:

Full text not available from this repository.


Layout graph grammars are a grammatical or rule-based method for the construction of graphs and of their drawings. As such they are representatives of the so-called declarative approach. A layout graph grammar consists of an underlying context-free graph grammar and of layout specifications. These are attached to the productions and consist of position relations and distances between the vertices of the productions. The layout specifications are often derived from drawings of the productions and can be defined in terms of labelled graphs. Layout graph grammars have been used unnoticed in many examples. They respect the underlying tree-like structure of their graphs and make it visible. This is a new effect, which makes them incompatible with most other graph drawing algorithms. Given a context-free layout graph grammar, there is a polynomial time algorithm which for every specification. The capabilities of layout graph grammars are illustrated by some tree drawings, which range from drawings with quadratic area to area optimal h-v drawings.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_395
Classifications: Z Theory > Z.001 General

Actions (login required)

View Item View Item