Automatic graph drawing and readability of diagrams
IEEE Transactions on Systems Man and CyberneticsPublished 1 January 1988
Roberto Tamassia, Giuseppe Di Battista, Carlo Batini
Citations378
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The algorithm presented draws graphs on a grid and is suitable for both undirected graphs and mixed graphs that contain as subgraphs hierarchic structures.
Abstract
The state of the art in automatic graph drawing is reviewed, with special attention to the readability of information system diagrams. Existing results in the literature are compared, and a comprehensive algorithmic approach to the problem is proposed. The algorithm presented draws graphs on a grid and is suitable for both undirected graphs and mixed graphs that contain as subgraphs hierarchic structures. Several applications of GIOTTO, a graphic tool that embodies the aforementioned facility, are shown.>
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
IEEE Transactions on Systems Man and CyberneticsMethods for Visual Understanding of Hierarchical System Structures
1,234 Citations1981Kozo Sugiyama, Shojiro Tagawa +1 more
Two kinds of new methods are developed to obtain effective representations of hierarchies automatically: theoretical and heuristic methods that determine the positions of vertices in two steps to improve the readability of drawings.
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
SIAM Journal on ComputingOn Embedding a Graph in the Grid with the Minimum Number of Bends
535 Citations1987Roberto Tamassia
An algorithm is presented that computes a region preserving grid embedding with the minimum number of bends in edges with use of network flow techniques, and runs in time $O(n^2 \log n)$, where n is the number of vertices of the graph.
IEEE Transactions on Software EngineeringTidier Drawings of Trees
503 Citations1981Edward M. Reingold, J.S. Tilford
It is shown that various algorithms for producing tidy drawings of trees contain some difficulties that lead to aesthetically unpleasing, wider than necessary drawings, and a new algorithm is presented with comparable time and storage requirements that produces tidier drawings.
Discrete & Computational GeometryA unified approach to visibility representations of planar graphs
333 Citations1986Roberto Tamassia, Ioannis G. Tollis
This work studies visibility representations of graphs, which are constructed by mapping vertices to horizontal segments, and edges to vertical segments that intersect only adjacent vertex-segments, and considers three types of visibility representations.
Information & ManagementInformation systems design methodologies - A comparative review
317 Citations1983
When you read more every page of this information systems design methodologies a comparative review, what you will obtain is something great.
Discrete & Computational GeometryRectilinear planar layouts and bipolar orientations of planar graphs
297 Citations1986Pierre Rosenstiehl, Robert E. Tarjan
This work proposes a linear-time algorithm, a variant of one by Otten and van Wijk, that generally produces a more compact layout than theirs and allows the dual of the graph to be laid out in an interlocking way.
Proceedings of the IEEECircuit layout
210 Citations1981Jiří Soukup
A general overview of circuit layout, taking a unified approach to various styles of integrated circuits, printed circuit boards, and hybrid circuits, and problems associated with the implementation of a hierarchical system are discussed.
IEEE Transactions on Systems Man and CyberneticsCrossing Theory and Hierarchy Mapping
183 Citations1977John Warfield
Techniques are introduced which are applicable to machine construction of digraph maps and oriented toward reduction of the number of crossings in a map as a means of improving the readability of hierarchical structures.
Journal of Combinatorial Theory Series BPlanarity and duality of finite and infinite graphs
181 Citations1980Carsten Thomassen
It is proven that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, the infinite graphs satisfying MacLane's condition are characterized completely, and it is proved that the 3-connected locally finite ones have convex representations.
IEEE Transactions on Software EngineeringA layout algorithm for data flow diagrams
130 Citations1986Carlo Batini, Enrico Nardelli +1 more
A layout algorithm is presented that allows the automatic drawing of data flow diagrams, a diagrammatic representation widely used in the functional analysis of information systems.
IEEE Transactions on Systems Man and CyberneticsAutomatic Display of Hierarchized Graphs for Computer-Aided Decision Analysis
122 Citations1980Marie-Jose Carpano
A study of questions raised by the conception of a tool for computer-aided decision analysis that would facilitate interactive structural systems analysis and the tool itself, named GT1VX, are presented.
IEEE Transactions on Software EngineeringTidy Drawings of Trees
116 Citations1979C. S. Wetherell, Avram R. Shannon
Two naive tree drawers are surveyed, formalize aesthetics for tidy trees, and two algorithms which draw tidy trees are discussed, one of which may be shown to require the minimum possible paper width.
Structured Systems Analysis
113 Citations2020John Gaylord
Acta InformaticaDrawing plane graphs nicely
90 Citations1985Norishige Chiba, Kazunori Onoguchi +1 more
Two efficient algorithms for drawing plane graphs nicely draw all edges of a graph as straight line segments without crossing lines if possible, in a way that every inner face and the complement of the outer face are convex polygons.
Acta InformaticaThe complexity of drawing trees nicely
89 Citations1983Kenneth J. Supowit, Edward M. Reingold
There is no obvious “principle of optimality” that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees, and the problem is NP-hard.
Journal of Systems and SoftwareComputer aided layout of entity relationship diagrams
88 Citations1984Carlo Batini, Maurizio Talamo +1 more
An algorithm that allows computer aided layout of entity relationship diagrams on a grid and a standard for the representation of symbols is introduced and aesthetic criteria that should be achieved by a layout algorithm are proposed.
NetworksOn minimal‐node‐cost planar embeddings
88 Citations1984James A. Storer
A third cost measure is considered, called the node cost measure, which is the total number of bends that are present along edges of the embedding, which has applications to light or microwave circuits where it requires a separate device each time a corner is turned.
Software Practice and ExperiencePretty‐printing of trees
42 Citations1980Jean Vaucher
A suitable general binary tree printing algorithm is presented and its adaptation to other types of trees is shown.
Proceedings of the IEEEComputer-aided design of VLSI circuits
27 Citations1981A. Richard Newton
This paper presents a review of the CAD techniques which have been used in the design of IC's, as well as a number of design methods to which the application of computer aids has proven most successful.
Lecture notes in computer scienceAn algorithm for testing planarity of hierarchical graphs
15 Citations1987Giuseppe Di Battista, Enrico Nardelli
An algorithm for k-line planarity testing of hierarchical graphs is described, which has time complexity O(∣V∣), and some forbidden patterns are identified, whose existence is necessary and sufficient for a hierarchical graph to be not k- line planar.