pq@fctunl.rccn.pt (Paulo Quaresma) (06/05/90)
Hi, Is there an algorithm (or paper) to layout the nodes of a graph ? Something to avoid cluttering... Please post or email (and I'll resume) -- --- Paulo Quaresma BITNET/Internet: pq@fctunl.rccn.pt +---------------------------------+ UUCP: pq@unl.uucp | Departamento de Informatica +----------------------------------+ | Universidade Nova de Lisboa 2825 Monte Caparica, PORTUGAL | +--------------------------------------------------------------------+
ekberg@nomad.csc.ti.com (Tom Ekberg) (06/07/90)
Ok, twist my arm :-)
I have been doing some research on graph layout algorithms, which
started with generating a bibliography. The following BibTeX file
(i.e. a .bib file for TeX) contains just that, and some notes others
have provided to me as the initial comments. Currently I am looking at
EDGE (see below) which runs on my Sun4 and talks to X11R4.
--------------------------- bibliography.bib --------------------------
% Several people have written in asking about graph drawing algorithms,
% especially those that minimize edge crossings. For planar graphs,
% this is easy and fast; there are linear-time (in the number of nodes)
% algorithms for planar graph embedding (drawing with no edge
% crossings) that have been developed by Booth and Lueker, and by
% Hopcroft and Tarjan - see the references below for more details. For
% trees it is also obviously easy to do. In the general case, the
% answer is not so hopeful. The `crossing number' of a graph G, denoted
% v(G), is the minimum number of edge crossings when G is drawn in the
% plane. Garey and Johnson have shown that the general crossing number
% decision problem "given an arbitrary graph G, and an integer k, is
% v(G) <= k?" is NP-complete, and so is probably intractable. As a
% consequence, much of the recent research has concentrated either on
% finding upper and lower bounds for crossing numbers, or on finding
% exact values for special graphs.
%
% 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 [TWE: the real mail address contains an
% `at' character between `newbery' and `ira' instead of the `dot'
% character. Since bibtex croaks on this character here, it isn't
% present.]) at the Uni. of Karlsruhe. It is written in C++ and uses
% the X Window System (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 abstraction - subgraphs with zoom-in and
% zoom-out.
%
% I (Frances J. Newbery) have been working on a customizable graph
% editor as part of my doctoral research at the University of Karlsruhe
% (West Germany). The implementation is in C++ and X (X11 version will
% be ready very soon). A customizable graph editor provides a
% consistent user interface to several applications. Several graph
% layout algorithms are available to display the graph. The user can
% group nodes/edges into subgraphs and view them zoomed-in or
% zoomed-out. For more information, e-mail to newbery.ira.uka.de [TWE:
% the real mail address contains an `at' character between `newbery'
% and `ira' instead of the `dot' character. Since bibtex croaks on
% this character here, it isn't present.] (but please try to keep it
% short as e-mail is very expensive for us, both sending and
% receiving).
%
% There is another graph editor developed at the University of
% Paderborn: PLEXUS - A system for implementing Hierarchical Graph
% Algorithms by Egon Wanke and Prof. Dr. Thomas Lengauer PhD Such
% algorithms process hierarchical defined graphs or cellular graph
% grammars. PLEXUS supports the implementation of hierarchical
% 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-hierarchical
% graph processing and editing routines. A graph editor has been
% implemented that allows the manipulation 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.
@article{akin87,
author="O. Akin and C. Baykan and D. R. Rao",
title="Structure of a directory space: a case study with a {UNIX}
operating system",
journal="IJMMS",
volume=26,
number=3,
note="Visualization of Data Structures",
year=1987}
% An alternate title is "Proceedings of the Fifth Quadrennial International
% Conference on the Theory and Applications of Graphs with special emphasis on
% Algorithms and Computer Science Applications held at Western Michigan
% University in Kalamazoo, June 4-8, 1984".
@inproceedings{barnes85,
author="Earl R. Barnes",
title="Partitioning the Notes of a Graph",
booktitle="Graph Theory with Applications to Algorithms and Computer
Science",
year=1985,
publisher="John Wiley and Sons",
editor="Y. Alavi and G. Chartrand and L. Lesniak and D. R. Lick and C.
% E. Wall",
pages="57--72"}
@article{batini84.1,
author="Carlo Batini and M. Talamo and Roberto Tamassia",
title="Computer Aided Layout of Entity Relationship Diagrams",
journal="Journal of Systems and Software",
volume=4,
year=1984,
note="Entity Relationship Diagram Layout",
pages="163--173"}
@inproceedings{batini84.2,
author="Carlo Batini and Enrico Nardelli and M. Talamo and Roberto
Tamassia",
title="A graph theoretic approach to aesthetic layout of information
systems diagrams",
booktitle="10th International Workshop on Graphtheoretic Concepts in
Computer Science",
year=1984,
address="Berlin"}
@article{batini86,
author="Carlo Batini and Enrico Nardelli and Roberto Tamassia",
title="A Layout Algorithm for Data Flow Diagrams",
journal="IEEE Transactions on Software Engineering",
volume="SE-12",
number=4,
month="April",
year=1986,
note="Graph Editors and Layout Algorithms for Graphs",
pages="538--546"}
@techreport{battista87,
author="G. Di Battista and R. Tamassia and E. Nardelli",
title="Plane Representations of Acyclic Digraphs",
institution="Dipartimento Di Informatica E Sistemistica, Universita
Degli Studi Di Roma",
number="6.87",
month="March",
note="Planar Graph Layout",
year=1987}
@article{bauer89,
author="Boecker Bauer and Herberg Bunzenhaeuser and Rathke Maier and
Schwab Ressel",
title="Einsatz einer anwendungsneutralen Benutzerschnittstelle in einer
Bueroanwendung als Beispiel fuer wissensbasierte M-C-Kommunikation",
journal="Angewandte Informatik",
month="July",
note="Visualization of Data Structures",
year=1989}
@article{bhatt84,
author="S. Bhatt and Frank Thomson Leighton",
title="A framework for solving {VLSI} graph layout problems",
journal="Journal Comput. System Sci.",
year=1984,
volume=28,
note="Graph drawing",
pages="300--343"}
@inproceedings{boecker86,
author="Boecker and Fischer and Nieper",
title="The Enhancement of Understanding through Visual Representation",
booktitle="CHI 86 Proceedings",
note="Visualization of Data Structures",
year=1986}
@misc{boehringer89,
author="Karl-Friedrich Boehringer",
title="Stabilitaet von Algorithmen fuer Graphenumbruch",
month="July",
year=1989,
note="Graph Editors and Layout Algorithms for Graphs",
address="Diplomarbeit, Uni Karlsruhe, 26"}
@article{booth76,
author="K. S. Booth and G. S. Lueker",
title="Testing the consecutive ones property, interval graphs, and
graph planarity using PQ-tree algorithms",
journal="Journal Comput. System Sci.",
year=1976,
note="Graph drawing",
pages="335--379"}
@techreport{brandenburger88,
author="Franz J. Brandenburger",
title="Nice Drawings of graphics and of trees are computationally
hard",
number="MIP-8820",
month="September",
year=1988,
note="Tree Layout Algorithms",
institution="Uni Passau, Fak. f. Mathematik u. Informatik"}
@article{canter85,
author="David Canter and Rod Rivers, Graham Storrs",
title="Characterizing user navigation through complex data structures",
journal="Behavior and information technology",
year=1985,
volume=4,
number=2,
note="Visualization of Data Structures",
pages="93--102"}
@article{carpano80,
author="Marie-Jose Carpano",
title="Automatic Display of Hierarchized Graphs for Computer-Aided
Decision Analysis",
journal="IEEE Transactions on Systems, Man, and Cybernetics",
volume="SMC-10",
number=11,
pages="705--715",
month="November",
note="Graph Editors and Layout Algorithms for Graphs",
year=1980}
@article{carroll82,
author="J. M. Carroll",
title="Learning, using and designing filenames and command paradigms",
journal="BIT",
volume=1,
number=4,
note="Visualization of Data Structures",
year=1982}
@inproceedings{casner88,
author="Stephen Casner and Jeffrey Bonar",
title="Using the expert's diagrams as a specification of expertise",
booktitle="IEEE Workshop on visual languages",
month="May",
note="Visualization of Data Structures",
year=1988}
@article{chiba85.1,
author="Norishige Chiba and Takao Nishizeki and S. Abe and
T. Ozawa",
title="A linear algorithm for embedding planar graphs using PQ-trees",
journal="Journal Comput. System Sci.",
year=1985,
note="Graph drawing",
pages="54--76"}
@article{chiba85.2,
author="Norishige Chiba and Kazunori Onoguchi and Takao Nishizeki",
title="Drawing Plane Graphs Nicely",
journal="Acta Informatica",
volume=22,
year=1985,
note="Planar Graph Layout",
pages="187--201"}
% The following is noted as an M.S. Project Report, but msthesis seems close
% enough.
@mastersthesis{davis84,
author="Michael Davis",
title="A Layout Algorithm for a Graph Browser",
school="EECS Department, University of California, Berkeley",
year=1984}
@techreport{dearholt85,
author="D. R. Dearholt and Schvaneveldt and F. Durso",
title="Properties of networks derived from proximities",
institution="Computing Research Laboratory, New Mexico State
University",
year=1985,
note="Graph drawing",
number="MCCS-85-14"}
@article{ding90,
author="Chen Ding and Prabhker Mateti",
title="A Framework for the Automated Drawing of Data Structure
Diagrams",
journal="IEEE Transactions on Software Engineering",
volume=16,
number=5,
month="May",
year=1990,
pages="543--557"}
@unpublished{eades84.1,
author="P. EADES",
title="A heuristic for graph drawing",
note="Graph drawing",
year=1984}
@techreport{eades84.2,
author="P. Eades and N. Wormald",
title="An {NP}-hard graph drawing problem",
institution="Department of Computer Science, University of Queensland",
number=52,
note="Graph drawing",
year=1984}
@techreport{eades87,
author="Peter Eades and Roberto Tamassia",
title="Algorithms for Automatic Graph Drawing: An Annotated
Bibliograph",
institution="University of Queensland, Dept. of Computer Science",
address="St. Lucia, Queensland, 4067, Australia",
number=82,
month="July",
note="Graph Editors and Layout Algorithms for Graphs",
year=1987}
@article{esposito88,
author="C. Esposito",
title="Graph graphics: theory and practice",
journal="Computers and Mathematics",
volume=15,
number=4,
note="Graph drawing",
year=1988}
@article{even76,
author="S. Even and R. E. Tarjan",
title="Computing an st-numbering",
journal="Theoretical Computer Science",
volume=2,
year=1976,
note="Graph drawing",
pages="339--344"}
@article{fairchild88,
author="Kim M. Fairchild and Steven E. Poltrock and George W. Furnas",
title="SemNet",
journal="Cognitive Science And Its Applications for Human-Computer
Interaction",
editor="Raymonde Guidon",
address="Hillsdale, New Jersey",
note="Visualization of Data Structures",
year=1988}
@article{fraser81,
author="C. W. Fraser and A. A. Lopez",
title="Editing Data Structures",
journal="ACM Transactions on Programming Languages and Systems",
volume=3,
number=2,
month="April",
year=1981,
note="Visualization of Data Structures",
pages="115--125"}
@article{furnas86,
author="George W. Furnas",
title="Generalized Fisheye Views",
journal="Human Factors in Computing Systems III, ACM Proceedings of the
CHI 86 Conference",
address="Boston, MA",
month="April 13-17",
year=1986,
note="Visualization of Data Structures",
pages="16--23"}
@article{gansner88,
author="E. R. Gansner and S. C. North and K. P. Vo",
title="{DAG}: A Program that Draws Directed Graphs",
journal="Software - Practice and Experience",
volume=18,
number=11,
month="November",
note="Graph Editors and Layout Algorithms for Graphs",
year=1988}
@article{garey83,
author="M. R. Garey And D. S. Johnson",
title="Crossing number is {NP}-complete",
journal="SIAM Journal of Algebraic Discrete Methods",
year=1983,
note="Graph drawing",
pages="312--316"}
@inproceedings{goldstein63,
author="A. J. Goldstein",
title="An efficient and constructive algorithm for testing whether a
graph can be embedded in a plane",
booktitle="Proceedings of the Graph and Combinatorics Conference",
institution="Office of Naval Research Logistics Projects and
Department of Mathematics, Princeton University",
note="Graph drawing",
year=1963}
@book{harary69,
author="Frank Harary",
title="Graph Theory",
publisher="Addison-Wesley",
address="Reading, MA",
note="Graph drawing",
year=1969}
@article{halewood88,
author="K. Halewood and R. Woodward",
title="{NSEDIT}: A syntax-directed Editor and Testing Tool based on
Nassi-Shneiderman Charts",
journal="Software - Practice and Experience",
volume=18,
number=10,
month="October",
note="Visualization of Data Structures",
year=1988}
@article{helttula89,
author="Helttula and Hyrskykari and Raiha",
title="Graphical Specification of Algorithm Animations with ALADDIN",
journal="Proc HICCS-22 (22nd Annual Hawaii International Conf. on
System Sciences)",
address="Kailua/Kona,Hawaii",
publisher="IEEE Computer Press",
month="January 3-6",
year=1989,
note="Visualization of Data Structures",
pages="892--901"}
@article{hopcroft74,
author="John. E. Hopcroft And Robert. E. Tarjan",
title="Efficient planarity testing",
journal="Journal of the ACM",
volume=21,
number=4,
year=1974,
note="Graph drawing",
pages="549--568"}
@article{hudlicka89,
author="Eva Hudlicka",
title="Visual System Browser",
journal="SIGCHI",
month="April",
year=1989,
volume=20,
note="Visualization of Data Structures",
number=4}
@article{jablonowski89,
author="Guarna Jablonowski",
title="{GMB}: A Tool for Manipulating and Animating Graph Data
Structures",
journal="Software - Practice and Experience",
volume=19,
number=3,
month="March",
note="Graph Editors and Layout Algorithms for Graphs",
year=1989}
@article{kamada89,
author="T. Kamada and S. Kawai",
title="An Algorithm for Drawing General Undirected Graphs",
journal="Information Processing Letters",
volume=31,
number=1,
year=1989,
note="Graph Editors and Layout Algorithms for Graphs",
pages="7--15"}
@techreport{kindermann,
author="C. Kindermann and Q. Quantz",
title="Graphikorientierte Wissensrepraesentation fuer KL-ONE",
institution="TU-Berlin",
year="unknown year",
note="Visualization of Data Structures",
number=63}
@book{leighton83,
author="Frank Thomson Leighton",
title="Complexity Issues in {VLSI}, Optimal Layouts for the
Shuffle-Exchange Graph and Other Networks",
publisher="MIT Press",
year=1983}
@inproceedings{leiserson80,
author="C. E. Leiserson",
title="Area-efficient Layouts for {VLSI}",
booktitle="Twenty-First Annual Symposium on Foundations of Computer
Science, IEEE",
address="New York",
note="Graph drawing",
year=1980}
@book{leiserson83,
author="C. E. Leiserson",
title="Area-efficient {VLSI} Computation",
address="Cambridge, MA",
publisher="MIT Press",
note="Graph drawing",
year=1983}
@inproceedings{lempel66,
author="A. S. Lempel and S. Even And I. Cederbaum",
title="An Algorithm for Planarity Testing of Graphs",
booktitle="Theory of Graphs: International Symposium",
editor="P. Rosenstiel",
publisher="Gordon and Breach",
address="New York",
year=1967,
note="Graph drawing",
pages="215--232"}
@unpublished{lipton77,
author="R. J. Lipton and R. E. Tarjan",
title="Applications of a Planar Separator Theorem",
note="Graph drawing",
year=1977}
@inproceedings{lipton85,
author="R. J. Lipton and S. C. North and J. S. Sandberg",
title="A Method for Drawing Graphs",
booktitle="Proceedings of the Symposium on Computational Geometry",
address="Baltimore, MD",
month="June",
year=1985,
pages="153--160",
note="Planar Graph Layout.
Also available as ACM 0-89791-163-6, 85/006/0153"}
@mastersthesis{meyer83,
author="Carl Meyer",
title="A Browser for Directed Graphs",
year=1983,
school="EECS Department, University of California, Berkeley",
month="December"}
@techreport{manning86,
author="Joseph Manning and Mikhail J. Atallah",
title="Fast Detection and Display of Symmetry in Outplanar Graphs",
number="CSD-TR-606",
month="June",
year=1986,
institution="Department of Computer Science, Purdue University",
note="Visualization of Data Structures",
address="West Lafayette, IN, USA"}
@article{miller85,
author="Zevi Miller and J. B. Orlin",
title="{NP}-completeness for Minimizing Maximum Edge Length in Grid
Embeddings",
journal="Journal of Algorithms",
year=1985,
note="Graph drawing",
pages="10--16"}
@techreport{myers80,
author="Brad A. Myers",
title="Displaying Data Structures for Interactive Debugging",
institution="Xerox Palo Alto Research Center",
number="CSL-80-7",
month="June",
note="Visualization of Data Structures",
year=1980}
@article{myers83,
author="Brad A. Myers",
title="INCENSE: A system for displaying data structures",
journal="Computer graphics",
volume=17,
number=3,
month="July",
note="Visualization of Data Structures",
year=1983}
@article{myers86,
author="Brad A. Myers",
title="Visual Programming, Programming by Example and Program
Visualization: A Taxonomy",
journal="CHI'86 Proceedings",
month="April",
year=1986,
note="Visualization of Data Structures",
pages="59--66"}
@phdthesis{newbery88.1,
author="Frances J. Newbery",
title="An interface description language for graph editors",
school="University of Karlsruhe",
note="Visualization of Data Structures",
year=1988}
@techreport{newbery88.2,
author="Frances J. Newbery",
title="{EDGE}: An Extendible Directed Graph Editor",
institution="Department of Informatics, University of Karlsruhe",
address="7500 Karlsruhe 1, West Germany",
number="8/88",
year=1988,
note="Graph drawing",
month="June"}
@inproceedings{newbery88.3,
author="Frances J. Newbery",
title="An Interface Description Language For Graph Editors",
booktitle="1988 IEEE Workshop on Visual Languages",
month="October 10--12",
year=1988,
address="Pittsburgh, PA",
pages="144--149",
note="ISBN 0-8186-0876-5, UTD library call number T385.I19 1988",
annotate="This paper contains an overview of EDGE (Extendible Directed
Graph Editor). Part of EDGE is an interface description language which
allows one to textually specify attribute values for a graph, such as
the graph layout algorithm and edge arrow style. This package is built
using C++ and X11R3"}
@manual{newbery89,
author="Frances J. Newbery",
title="Graph Description Language: Reference Manual (draft)",
month="April 17",
note="Visualization of Data Structures",
year=1989}
@techreport{nieper85,
author="Helga Nieper",
title="TRISTAN: A Generic Display and Editing System for Hierarchical
Structures",
institution="Department of Computer Science, University of Colorado",
note="Visualization of Data Structures",
year=1985}
@techreport{oberquelle81,
author="Horst Oberquelle",
title="Communication by Graphic Net Representations",
number=75,
institution="Institut fuer Informatik, Universitaet Hamburg
Schlueterstr. 70",
address="D-2 HH 13",
month="March",
note="Visualization of Data Structures",
year=1981}
@inproceedings{pintado,
author="X. Pintado and D. Tsichritzis",
title="An Affinity Browser",
booktitle="Active Object Environments",
editor="D. Tsichritzis",
note="Visualization of Data Structures",
year="unknown year",
pages="172--186"}
@inproceedings{read,
author="R. C. Read",
title="A survey of graph graphics",
booktitle="Proceedings Indiana Conference on Graph Theory",
note="Graph drawing",
year="unknown year"}
@article{reggiani88,
author="Marcello G. Reggiani and Franco E. Marchetti",
title="A Proposed Method for Representing Hierarchies",
journal="IEEE Transactions on Systems, Man, and Cybernetics",
volume=18,
number=1,
year=1988,
month="January/February",
note="Visualization of Data Structures",
pages="1--8"}
@article{reingold81,
author="Edward M. Reingold and John S. Tilford",
title="Tidier Drawings of Trees",
journal="IEEE Transactions on Software Engineering",
volume=7,
number=2,
month="March",
year=1981,
note="Tree Layout Algorithms",
pages="223--228"}
@inproceedings{robins87,
author="Gabriel Robins",
title="The {ISI} Grapher: a Portable Tool for Displaying Graphs
Pictorially",
booktitle="Symboliikka '87",
month="August 17-18",
year=1987,
address="Helsinki, Finland",
note="Graph Editors and Layout Algorithms for Graphs",
institution="Information Sciences Institute, Marina Del Rey, CA"}
@article{rowe87,
author="Lawrence A. Rowe and Michael Davis and Eli Messinger and
Carl Meyer and Charles Spirakis and Allen Tuan",
title="A Browser for Directed Graphs",
journal="Software - Practice and Experience",
month="January",
year=1987,
volume=17,
number=1,
pages="61--76",
note="UTD call number QA76.5 s653",
annote="This paper is a good introduction to graph layout as it
describes problems as well as successes. It is a bit weak in
technical details of the algorithms, but those should be available
through the references."}
@phdthesis{shirey69,
author="R. W. Shirey",
title="Implementation and analysis of efficient graph planarity testing
algorithms",
school="University of Wisconsin",
note="Graph drawing",
year=1969}
@inbook{swamy81,
author="M. N. S. Swamy and K. Thulasiraman",
title="Graphs, Networks, and Algorithms",
year=1981,
publisher="John Wiley and Sons",
pages="428--430"}
@inproceedings{sugiyama78,
author="Kozo Sugiyama and Toshisuke Hiramatsu and Yasuo Shimazu",
title="Toward Development of Earthquake Disaster Relational Model",
booktitle="Proceedings International Conference on
Cybernetics and Society",
address="New York",
month="November",
year=1978,
pages="788--793"}
@inproceedings{sugiyama79,
author="Kozo Sugiyama and Shojiro Tagawa and Mitsuhiko Toda",
title="Effective representations of {ISM} Hierarchies",
booktitle="Proceedings International Conference on
Cybernetics and Society",
address="New York",
month="October",
year=1979,
pages="413--418"}
@article{sugiyama81,
author="Kozo Sugiyama and Shojiro Tagawa and Mitsuhiko Toda",
title="Methods for Visual Understanding of Hierarchical System
Structures",
journal="IEEE Transactions on Systems, Man, and Cybernetics",
volume="SMC-11",
number=2,
month="February",
year=1981,
note="Graph Editors and Layout Algorithms for Graphs",
pages="109--125"}
@techreport{sugiyama84,
author="Kozo Sugiyama",
title="A Readability Requirement in Drawing Digraphs: Level Assignment
and Edge Removal for Reducing Total Length of Lines",
institution="International Institute for Advanced Study of Social
Information Science",
address="Numazu, Japan",
number=45,
month="March",
note="Graph Editors and Layout Algorithms for Graphs",
year=1984}
@article{sugiyama85,
author="Kozo Sugiyama and Mitsuhiko Toda",
title="Structuring Information for Understanding Complex Systems: A
Basis for Decision Making",
journal="FUJITSU Scientific and Technical Journal",
volume=21,
number=2,
month="June",
year=1985,
note="Graph Editors and Layout Algorithms for Graphs",
pages="144--158"}
@article{sugiyama87,
author="Kozo Sugiyama",
title="A Cognitive Approach for Graph Drawing",
journal="Cybernetics and Systems: An International Journal",
volume=18,
year=1987,
note="Graph Editors and Layout Algorithms for Graphs",
pages="447--488"}
@article{supowit83,
author="Kenneth J. Supowit and Edward M. Reingold",
title="The Complexity of Drawing Trees Nicely",
journal="Acta Informatica",
volume=18,
year=1983,
note="Tree Layout Algorithms",
pages="377--392"}
@inbook{tamassia83,
author="R. Tamassia and C. Batini and M. Talamo",
title="An algorithm for automatic layout of entity relationship
diagrams, Entity-Relationship Approach to Software Engineering",
publisher="North-Holland Publishing Co.",
year=1983,
note="Entity Relationship Diagram Layout",
pages="421--439"}
@inproceedings{tamassia85,
author="Roberto Tamassia",
title="New layout techniques for Entity-Relationship diagrams",
booktitle="IEEE 1985, proceedings of the 4th International Conference
on Entity-Relationship Approach",
address="Chicago",
note="Visualization of Data Structures",
year=1985,
pages="304--322"}
@article{tamassia87,
author="Roberto Tamassia",
title="On Embedding a Graph in the Grid with the Minimum Number of
Bends",
journal="SIAM J. Computing",
volume=16,
number=3,
month="June",
year=1987,
note="Graph Editors and Layout Algorithms for Graphs",
pages="421--444"}
@article{tamassia88,
author="Roberto Tamassia and Guuseppe Di Battista and Carlo Batini",
title="Automatic Graph Drawing and Readability of Diagrams",
journal="IEEE Transactions on Systems, Man, and Cybernetics",
volume="SE-18",
number=1,
month="January/February",
year=1988,
pages="61--79",
note="UTD call number 300.I43",
annote="Good overview of existing graph drawing algorithms. Classifies
aesthetics (e.g. minimizing crossings) and constraints of layout
algorithms."}
@inproceedings{tichy87.1,
author="Walter F. Tichy and Frances J. Newbery",
title="Knowledge-based Editors for Directed Graphs",
booktitle="Proceedings of the 1st European Software Engineering
Conference",
month="September 9-11",
year=1987,
publisher="Springer Verlag",
editor="Howard K. Nichols and Dan Simpson",
note="Graph drawing, Lecture Notes in Computer Science No. 289",
pages="101--109"}
@techreport{tichy87.2,
author="Walter F. Tichy and Blake Ward",
title="A Knowledge-Based Graphical Editor",
institution="Department of Informatics, University of Karlsruhe",
address="7500 Karlsruhe 1, West Germany",
number="3/87",
month="January",
note="Graph drawing",
year=1987}
@inproceedings{trickey88,
author="Howard Trickey",
title="DRAG: A Graph Drawing System",
booktitle="Proceedings of the International Conference on Electronic
Publishing, Document Manipulation and Typography",
publisher="Cambridge University Press",
month="April",
note="Graph Editors and Layout Algorithms for Graphs",
year=1988}
@inproceedings{tutte63,
author="W. T. Tutte",
title="How to draw a graph",
booktitle="Proceedings London Math. Society",
year=1963,
note="Graph drawing",
pages="743--768"}
@book{ullman84,
author="J. Ullman",
title="Computational Aspects of {VLSI}",
publisher="Computer Science Press",
address="Rockville",
note="Graph drawing",
year=1984}
@article{vaucher80,
author="J. G. Vaucher",
title="Pretty Printing of Trees",
journal="Software - Practice and Experience",
volume=10,
year=1980,
note="Tree Layout Algorithms",
pages="553--561"}
@article{watanabe89,
author="Hiroyuki Watanabe",
title="Heuristic graph displayer for {G}-{BASE}",
journal="Int. J. Man-Machine Studies",
year=1989,
volume=30,
note="Visualization of Data Structures",
pages="287--302"}
@article{wetherell79,
author="Charles Wetherell and Alfred Shannon",
title="Tidy Drawings of Trees",
journal="IEEE Transactions on Software Engineering",
volume=5,
number=5,
month="September",
year=1979,
note="Tree Layout Algorithms",
pages="514--520"}
@inproceedings{wolf88,
author="G. W. Wolf",
title="Weighted Surface Networks and their Application to Cartographic
Generalization",
editor="W. Barth",
booktitle="Visualisierungstechniken und Algorithmen Fachgespraech
Wien",
volume="26./27.",
month="September",
year=1988,
note="Visualization of Data Structures",
pages="199--212"}
@article{woo69,
author="Lin Woo",
title="An Algorithm for Straight-line Representation of Simple Planar
Graphs",
journal="Journal of The Franklin Institute",
volume=287,
number=3,
month="March",
year=1969,
note="Planar Graph Layout",
pages="197--208"}
@phdthesis{woods81,
author="Donald R. Woods",
title="Drawing Planar Graphs",
month="June",
year=1981,
number="STAN-CS-82-943",
note="Planar Graph Layout",
school="Department of Computer Science, Stanford University"}
@inproceedings{znotinas79,
author="M. N. Znotinas and P. H. Roe",
title="A Preprocessor for Algorithms to Determine Minimum Feedback
Vertex Sets",
month="October",
year=1979,
booktitle="Proceedings International Conference on Cybernetics and
Society",
pages="409--412"}
-----------------------------------------------------------------------
-- tom (aisle C-4Q), ekberg@csc.ti.comhimsolt@trillian-gw.fmi.uni-passau.de (Michael Himsolt) (06/07/90)
There is a bibliography on graph layout by P. Eades and R. Tamassia : P. Eades, R. Tamassia : "Algorithms for Automatic Graph Drawing: An Annotated Bibliography", Technical Report CS-89-09, Dept. of Computer Science, Brown Univ., 1989 It contains short descriptions of the various methods developed for graph layout. Roughly speaking, there are layout algorithms for trees, hierarchies, planar graphs, and general graphs. We are currently implementing some of the algorithms mentioned in this paper and some new ones in our graph editor GraphEd. -- Michael Himsolt -- Michael Himsolt, Universitaet Passau, Innstrasse 33, D-8390 Passau, W GERMANY himsolt@unipas.fmi.uni-passau.de graphed@unipas.fmi.uni-passau.de