A technique for drawing directed graphs
IEEE Transactions on Software EngineeringPublished 1 March 1993
Emden R. Gansner, E. Koutsofios, Stephen C. North, K.-P. Vo
Citations668
SJR quartileQ1
SJR score1.45
SNIP2.43
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
A four-pass algorithm for drawing directed graphs is presented, which creates good drawings and is fast.
Abstract
A four-pass algorithm for drawing directed graphs is presented. The fist pass finds an optimal rank assignment using a network simplex algorithm. The seconds pass sets the vertex order within ranks by an iterative heuristic, incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm creates good drawings and is fast.>
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.
SIAM Journal on ComputingDepth-First Search and Linear Graph Algorithms
6,021 Citations1972Robert E. Tarjan
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples of an improved version of an algorithm for finding the strongly connected components of a directed graph.
COMBINATORICAA new polynomial-time algorithm for linear programming
4,840 Citations1984Narendra Karmarkar
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.
Computational GeometryAlgorithms for drawing graphs: an annotated bibliography
860 Citations1994Giuseppe Di Battista, Peter Eades +2 more
A bibliographic survey on algorithms whose goal is to produce aesthetically pleasing drawings of graphs is presented, a first attempt to encompass both theoretical and application-oriented papers from disparate areas.
Graphics gems
398 Citations1990Andrew Glassner
Mathematics of Operations ResearchFinding Minimum-Cost Circulations by Successive Approximation
339 Citations1990Andrew V. Goldberg, Robert E. Tarjan
This work develops a new approach to solving minimum-cost circulation problems that combines methods for solving the maximum flow problem with successive approximation techniques based on cost scaling and shows that a minimum- cost circulation can be computed by solving a sequence of On lognC blocking flow problems.
Theoretical Computer ScienceAlgorithms for plane representations of acyclic digraphs
254 Citations1988Giuseppe Di Battista, Roberto Tamassia
This work investigates the problem of representing acyclic digraphs in the plane in such a way that all edges flow in the same direction, e.g., from the left to the right or from the bottom to the top.
Mathematical ProgrammingA network simplex method
205 Citations1976William H. Cunningham
Simple combinatorial modifications are given which ensure finiteness in the primal simplex method for the transshipment problem and the upper-bounded primalsimplexmethod for the minimum cost flow problem.
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.
Software Practice and ExperienceDAG—a program that draws directed graphs
130 Citations1988Emden R. Gansner, Stephen C. North +1 more
DAG is a program that draws directed graphs by reading a list of noeds and edges, computing a layout and then writing a PIC or PostScript description of a picture, which works best on directed acyclic graphs.
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.
Software Practice and ExperienceA browser for directed graphs
116 Citations1987Lawrence A. Rowe, Michael J. Davis +4 more
A general‐purpose browser for directed graphs is described, which provides operations to examine and edit graphs and to generate a layout for a graph automatically that minimizes edge crossings.
International Journal of Pattern Recognition and Artificial IntelligenceON THE PROBLEM OF PLACING NAMES IN A GEOGRAPHIC MAP
34 Citations1987Herbert Freeman, John Kwangho Ahn
The results of a research study are described which have led to the development of AUTONAP, an expert system for automatic name placement that attempts to emulate the manner in which an expert cartographer would place names.