Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!ut-emx!infotel!smunews!ti-csl!nomad.csc.ti.com!ekberg
From: ekberg@nomad.csc.ti.com (Tom Ekberg)
Newsgroups: comp.graphics
Subject: Re: Graph node layout (long)
Message-ID: <126842@ti-csl.csc.ti.com>
Date: 6 Jun 90 20:45:40 GMT
Sender: news@ti-csl.csc.ti.com
Organization: TI Computer Science Center, Dallas
Lines: 964

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.com