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, Princeton, New Jersey, USA , pp. 416-427 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_395).

Full text not available from this repository.

Abstract

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
ID Code:241

Repository Staff Only: item control page

References

W. Bachl, F.J. Brandenburg, T. Hickl "Hierarchical Graph Design Using HiGraD" Technical Report, University of Passau, MIP 9405 (1994)

F.J. Brandenburg "On polynomial time graph grammars" Lecture notes in Computer Science 294 (1988), pp. 227-236

F.J. Brandenburg "Layout Graph Grammars: the Placement Approach" Lecture Notes in Computer Science 532 (1991), pp. 144-156

B. Courcelle "Graph rewriting: An algebraic and logic approach" Handbook of Theoret. Comput. Science, Vol. B, Elsevier (1990), pp. 193-242

B. Courcelle "On the structure on context-free sets of graphs generated by vertex replacement" Research Report 91-44, Bordeaux University (1991)

B. Courcelle, J. Engelfriet "A logical characterization of the sets of hypergraphs defines by hyperedge replacement grammars" Research Report 91-41, Bordeaux University (1991)

P. Crescenzi, G. Di Battista, A. Piperno "A note on optimal area algorithms for upward drawings of binary trees" Comput. Geometry: Theory and Applications 2(1992), pp. 187-200

G. Di Battista, P. Eades, R. Tamassia, I. Tollis "Algorithms for Drawing Graphs: an Annotated Bibliography" Technical Report, Brown University, Providence (1993)

P. Eades, T. Lin "Algorithmic and declarative approaches to aesthetic layout" Proc. Graph Drawing '93 (1993), pp. 95-96

P. Eades, T. Lin, X. Lin "Minimum Size h-v Drawings" Proc. Advanced Visual Interfaces (1992) World Scintific Series in Computer Science Vol. 36, pp. 386-394

H. Ehrig, H.-J. Kreowski, G. Rozenberg (Eds.) "Graph Grammars and their Application to Computer Science" Lecture Notes in Computer Science 532 (1991)

J. Engelfriet "Context-free NCE graph grammars" Lecture Notes in Computer Science 380 (1989), pp. 148-161

E.J. Golin, S.P. Reiss "The Specification of Visual Language Syntax" J. Visual Languages 1 (1990), pp. 141-157

T. Hickl "Rechtwinkeliges Layout von hierarchisch strukturierten Graphen" University of Passau (1994)

M. Himsolt "Konzeption and Implementierung von Grapheneditoren" Dissertation, University of Passau (1993)

J.E. Hopcroft, J.D. Ullman "Introduction to Automata Theory, Languages and Computation" Addison/Wesley (1979)

C.L. McGreary, C.L. Combs, D.H. Gill, J.V. Warren "An automated graph drawing system using graph decomposition" Proc. Graph drawing '93 (1993), pp. 119-120

G. Rozenberg, E. Welzl "Boundary NLC graph grammars - basic definitions, normal forms and complexity" Inform. Control 69 (1986), pp. 136-167

R. Schuster "Graph Grammatiken und Graph Einbettungen: Algorithmen und Komplexität" Technical Report, University of Passau, MIP 8711 (1987)

J. D. Ullman "Computational Aspects of VLSI" Computer Science Press (1984)

G. Zinßmeister "Layout of trees with attribute graph grammars" Proc. Graph Drawing '93 (1993), pp. 99-102