Path: utzoo!attcan!uunet!mcvax!unido!pbinfo!mike
From: mike@pbinfo.UUCP (Michael Utermoehle)
Newsgroups: comp.graphics
Subject: Re: graph drawing algorithm
Message-ID: <783@pbinfo.UUCP>
Date: 9 Nov 88 09:30:52 GMT
References: <gXNq8hy00VQD0O0Gdt@andrew.cmu.edu> <13391@cisunx.UUCP> <1026@psuhcx.psu.edu> <24313@wlbr.EATON.COM> <10091@swan.ulowell.edu>
Reply-To: mike@pbinfo.UUCP (Michael Utermoehle)
Distribution: comp.graphics
Organization: Uni-GH Paderborn, Germany
Lines: 72

In article <10091@swan.ulowell.edu> mschedlb@hawk.ulowell.edu (Martin Schedlbauer) writes:
>In article <24313@wlbr.EATON.COM> mh@wlbr.eaton.com.UUCP (Mike Hoegeman) writes:
>>In article <1026@psuhcx.psu.edu> sbj@psuhcx (Sanjay B. Joshi) writes:
>>   >I'm looking for an algorithm that takes as input a generalized
>>graph, determines the space requirements of a display image of the 
>>    >graph, and finally displays the graph with a minimum of intersecting arcs.
>>    >If any one knows of any such algorithm or references please let me know.
>>    >
>
>I probably won't be of too much help right now, but I'll check my sources
>as soon as get them back. Anyway, I think there is some interesting stuff
>on that subject (in terms of references) in the Proceedings for the 1988
>IEEE International Workshop on Visual Languages held October 10-12 in Pitts-
>burgh, PA (hosted by University of Pittsburgh.). A paper by Frances Newbery
>presented at the conference was concerned with that subject. Maybe that'll 
>help some.
>

EDGE - an extendible directed graph editor is developed (by Frances
Newbery newbery@ira.uka.de) at the Uni. of Karlsruhe. It is written in
C++ and uses the X Window Sytstem (cur. X10). EDGE is available on
Sun workstations, MicroVaxen and IBM RTs. The graph editor consists of
a display engine, a set of layout specs, a user interface and a default
editor. There are cur. four automatic layout algorithm available:
One for min. edge crossing (Sugiyama), cycles in a graph, tree-like
layout in linear time and Reingold/Tilford algorithm. 
There are several demo programs available: A Project Management Editor,
A Program Animator (very simple), Directory Browser, Logic Simulator
(very simple) and Petri Net Editor. 
Some nice features: Applications are very easy to interface (If you adopt
the data structure). Multilevel graphical abstruction - subgraphs with
zoom-in and zoom-out.
Two papers are available:
	1. EDGE: An Extendible Directed Graph Editor
	2. An interface description language for graph editors 
	   (the paper from IEEE 1988 VL-workshop)
University of Karlsruhe, Postfach 6980, D-7500 Karlsruhe, W-Germany

There is another graph editor developed at the University of Paderborn:
                PLEXUS - A system for implementing Hierarchical Graph
                Algorithmus by Egon Wanke and Prof. Dr. Thomas Lengauer PhD
                Such algorithms process hierarchical defined graphs or cellular
                graph grammars. PLEXUS supports the implementation of hierar-
                chical graph algorithms based on the bottom-up method by 
                providing the necessary basic data structures and functions.
                The system is organized in several layers for implementation
                of the basic data-types set,list and object, implementation
                of the necessary graph concepts and routines for hierchical 
                and non-hierachical graph processing and editing routines.
                A graph editor has been implemented that allows the mani-
                pulation of graphs on the screen. Most of the implementation
                algorithms can be called from within the editor. New algorithms
                or commands can easily be integrated into the editor.
                During the interactive generation of new vertices and 
                nonterminals the editor assigns to each new object screen
                coordinates. Several commands within the editor can change 
                these screen coordinates and thus modify the image of the
                graph on the screen. Other commands execute procedures that
                generate expansions of hierarchical graphs and draw the result
                on the screen or store it into files (if the expansion does
                not fit into memory). 
                The system has been implemented in the programming language C
                on a Sun-3 Workstation. All graphic routines are based on the
                SunView system. Currently the non-hierarchical features of the
                system are used as the basis for developing software for
                integrated circuit layout.

(E.Wanke is reachable under ..!uunet!unido!pbinfo!egon)

Greetings
   mike