Algorithms for drawing graphs: an annotated bibliography
Computational GeometryPublished 1 October 1994
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis
Citations860
SJR quartileQ3
SJR score0.40
SNIP0.77
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 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.
Abstract
Several data presentation problems involve drawing graphs so that they are easy to read and understand. Examples include circuit schematics and software engineering diagrams. In this paper we present a bibliographic survey on algorithms whose goal is to produce aesthetically pleasing drawings of graphs. Research on this topic is spread over the broad spectrum of Computer Science. This bibliography constitutes an attempt to encompass both theoretical and application oriented papers from disparate areas.
Keywords
Computer Science
Journal of the Operational Research SocietyIntroduction to Algorithms
16,942 Citations1991V. J. Rayward‐Smith, Thomas H. Cormen +2 more
Information Processing LettersAn algorithm for drawing general undirected graphs
2,771 Citations1989Tomihisa Kamada, Satoru Kawai
Society for Industrial and Applied Mathematics eBooksData Structures and Network Algorithms
2,067 Citations1983Robert E. Tarjan
This paper presents a meta-trees tree model that automates the very labor-intensive and therefore time-heavy and therefore expensive process of manually selecting trees to grow in a graph.
ACM Transactions on GraphicsAutomating the design of graphical presentations of relational information
1,620 Citations1986Jock D. Mackinlay
The goal of the research described in this paper is to develop an application-independent presentation tool that automatically designs effective graphical presentations (such as bar charts, scatter plots, and connected graphs) of relational information.
Journal of Computer and System SciencesTesting for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
1,498 Citations1976Kellogg S. Booth, George S. Lueker
The consecutive ones test for the consecutive ones property in matrices and for graph planarity is extended to a test for interval graphs using a recently discovered fast recognition algorithm for chordal graphs.
Communications of the ACMOn visual formalisms
1,269 Citations1988David Harel
The higraph, a general kind of diagramming object, forms a visual formalism of topological nature that is suited for a wide array of applications to databases, knowledge representation, and the behavioral specification of complex concurrent systems using the higraph-based language of statecharts.
Journal of the ACMEfficient Planarity Testing
1,079 Citations1974John E. Hopcroft, Robert E. Tarjan
An efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane is described, which used depth-first search and has time and space bounds.
Algorithmic graph theory
830 Citations1985Alan Gibbons
SIAM Journal on Algebraic and Discrete MethodsCrossing Number is NP-Complete
661 Citations1983M. R. Garey, David S. Johnson
This paper shows that there is not likely to be any efficient way to design an optimal embedding of a graph or network in a planar surface, and hence this problem is NP-complete.
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.
Parallel tree contraction and its application
409 Citations1985Gary L. Miller, John H. Reif
A bottom-up algorithm to handle trees which has two major advantages over the top-down approach: the control structure is straight forward and easier to implement facilitating new algorithms using fewer processors and less time; and problems for which it was too difficult or too complicated to find polylog parallel algorithms are now easy.
SIAM Journal on Algebraic and Discrete MethodsThe Complexity of the Partial Order Dimension Problem
404 Citations1982Mihalis Yannakakis
IEEE Transactions on ComputersUniversality considerations in VLSI circuits
389 Citations1981Leslie G. Valiant
The problem of embedding the interconnection pattern of a circuit into a two-dimensional surface of minimal area is discussed and restricted classes of graphs have to be considered in order to achieve compact embeddings.
IEEE Transactions on Systems Man and CyberneticsAutomatic graph drawing and readability of diagrams
378 Citations1988Roberto Tamassia, Giuseppe Di Battista +1 more
The algorithm presented draws graphs on a grid and is suitable for both undirected graphs and mixed graphs that contain as subgraphs hierarchic structures.
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.
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.
Canadian Journal of MathematicsTransitive Orientation of Graphs and Identification of Permutation Graphs
255 Citations1971Amir Pnueli, A. Lempel +1 more
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.
Theoretical Computer ScienceComputing an st-numbering
252 Citations1976Shimon Even, Robert E. Tarjan
This paper provides a linear-time algorithm for computing an st-numbering for any biconnected graph and can be combined with some new results by Booth and Lueker to provide alinear-time implementation of the Lempel-Even-Cederbaum planarity-testing algorithm.
Journal of Computer and System SciencesA linear algorithm for embedding planar graphs using PQ-trees
198 Citations1985Norishige Chiba, Takao Nishizeki +2 more
A simple linear algorithm for embedding (or drawing) a planar graph in the plane based on the “vertex-addition” algorithm of Lempel, Even, and Cederbaum that can find all the embeddings of aPlanar graph.
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.
IEEE Transactions on Circuits and SystemsPlanar grid embedding in linear time
175 Citations1989Roberto Tamassia, Ioannis G. Tollis
A new algorithm is presented that runs in O(n) time and produces grid embeddings with the following properties: the total number of bends is at most 2.4n+2; the number of bending along each edge is at least 4; the length of every edge is O( n); and the area of the embedding is O (n/sup 2/).
Small sets supporting fary embeddings of planar graphs
161 Citations1988Hubert de Fraysseix, János Pach +1 more
It is shown that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n, which settles a problem of Mohar.
Incremental planarity testing
134 Citations1989Giuseppe Di Battista, Roberto Tamassia
An efficient technique for incremental planarity testing that uses O(n) space and supports tests and insertion of vertices and edges in O(log n) time is presented.
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 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.
Characterizing bar line-of-sight graphs
128 Citations1985Stephen Wismath
A restricted version of the problem (using line segments and a single line-of-sight) is discussed and the associated graphs are characterized.
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.
Software Practice and ExperienceInteracting with the field environment
104 Citations1990Steven P. Reiss
The key concepts behind FIELD are an integration mechanism based on a simple, central message server, an annotation editor for integrating access to the source file with the other tools, and the use of a high‐level user interface toolset.
AlgorithmicaA linear algorithm to find a rectangular dual of a planar triangulated graph
99 Citations1988Jayaram Bhasker, Sartaj Sahni
AnO(n) algorithm is developed to construct a rectangular dual of ann-vertex planar triangulated graph and it is shown that this dual can be implemented as a discrete-time polynomial.
Journal of Graph TheoryRectilinear drawings of graphs
95 Citations1988Carsten Thomassen
A complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segments is obtained.
SIAM Journal on ComputingParallel Algorithms in Graph Theory: Planarity Testing
89 Citations1982Joseph F. JáJá, Janoš Šimon
This work presents efficient $(O(\log ^2 n)$ parallel algorithms for two classical graph problems: planarity testing and finding triconnected components, using only a polynomial number of processors.
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.
Discrete MathematicsFundamentals of planar ordered sets
85 Citations1987David R. Kelly
It is proved it is equivalent to allow instead an arc from a to b as long as the arc does not go below the level of a or above thelevel of b (whenever a is covered by b ).
Journal of Graph TheoryHypergraph planarity and the complexity of drawing venn diagrams
76 Citations1987David S. Johnson, H. O. Pollak
This work introduces two new notions of planarity for hypergraphs based on dual generalizations of the standard Venn diagram, and shows that the general problem of determining whether such diagrams exist is NP-complete.
COMBINATORICAHow to make a digraph strongly connected
71 Citations1981András Frank
AnO(n5) primal-dual algorithm is presented for finding a minimum weight covering of an edge-weighted digraph and a constructive proof for a min-max theorem due to Lucchesi and Younger is provided.
DSpace@MIT (Massachusetts Institute of Technology)Planar Embedding of Planar Graphs
70 Citations1983Danny Dolev, Frank Thomson Leighton +1 more
It is shown that an N-node planar graphs has a planar embedding with area 0(NF), where F is a bound on the path length from any node to the exterior face, and finding a minimal embedding area is shown to be Nu-complete for forests, and hence for more general types of graphs.
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsO(n/sup 2/) algorithms for graph planarization
70 Citations1989R. Jayakumar, K. Thulasiraman +1 more
The authors present two O(n/sup 2/) planarization algorithms, PLANARIZE and MAXIMAL-PLANARIZE, based on A. Cederbaum's (1967) planarity testing algorithm and its implementation using PQ-trees.
Journal of Combinatorial Theory Series BPlanar lattices and planar graphs
69 Citations1976Craig Platt
It is shown that a finite lattice is planar if and only if the graph obtained from its (Hasse) diagram by adding an edge between its least and greatest elements is a planar graph.
IEEE Transactions on ComputersCrossing minimization in linear embeddings of graphs
67 Citations1990Shinya Masuda, K. Nakajima +2 more
The authors show that the problem of embedding a graph in the plane with the minimum number of edge crossings remains NP-hard even if, in addition to these constraints, the positions of the vertices on l are predetermined.
Discrete MathematicsRepresenting a planar graph by vertical lines joining different levels
67 Citations1983Pierre Duchet, Yahya Ould Hamidoune +2 more
It is proved that every planar graph can be represented by horizontal segments corresponding to vertices and vertical segments correspondingto edges in such a way that no crossing appears.
IEEE Transactions on Systems Man and CyberneticsHierarchies and planarity theory
67 Citations1988Giuseppe Di Battista, Enrico Nardelli
An efficient algorithm for testing if a hierarchy is planar (i.e. if it can be drawn without edge crossings) is proposed and a complete combinatorial characterization of the class of planar hierarchies is given.
SIAM Journal on ComputingRectilinear Graphs and Their Embeddings
58 Citations1985Gopalakrishnan Vijayan, Avi Wigderson
The embedding problem for a class of graphs called rectilinear graphs, which have applications in many VLSI Layout Problems, is discussed and an interesting topological characterization of these graphs lead to efficient algorithms for recognizing and embedding rectilInear graphs which are embeddable on the plane.
Edge concentration: a method for clustering directed graphs
56 Citations1989F. J. Newbery
This paper proposes the elimination of some edges by replacing sets of edges that have the same set of source and target nodes by a special node called an edge concentration node.
Drawing planar graphs
47 Citations1981Donald R. Woods
This work examines the general problem of drawing a planar graph, and looks at various constraints that have been found to yield useful drawings in some applications, and develops a fast algorithm for producing drawings meeting those constraints.
Discrete MathematicsA note on visibility graphs
43 Citations1987Fabrizio Luccio, S. Mazzone +1 more
It is proved that any visibility graph G is ipo-triangular, that is, it can be transformed into a planar multigraph with all triangular finite faces, by successive duplications of existing edges of G.
North-Holland mathematics studiesA Depth-First-Search Characterization of Planarity
43 Citations1982Hubert de Fraysseix, Pierre Rosenstiehl
A property of the Tremaux trees of a graph is displayed, which constitutes a new characterization of planarity and justifies the so-called left-right algorithm for planarity testing and embedding and enlightens in general terms why a Tremaux tree allows a linear computing time.
An optimal parallel algorithm for graph planarity
42 Citations1989Vijaya Ramachandran, John H. Reif
The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar.
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.
Information Processing LettersUnit-length embedding of binary trees on a square grid
39 Citations1989A. Gregori
A proof of the fact that determining whether or not a given binary tree has a grid embedding with edges of unit length is an NP-complete problem is given.
Area requirement and symmetry display in drawing graphs
30 Citations1989Giuseppe Di Battista, Roberto Tamassia +1 more
This work has shown that every n-vertex planar graph admits a planar straight-line drawing with vertices placed at grid points and 0 (n2) area.
Automatic layout of PERT diagrams with X-PERT
30 Citations2003Giuseppe Di Battista, E. Pietrosanti +2 more
Techniques for visualizing PERT diagrams are presented and these techniques are used in the graphics tool X-PERT, which provides an integrated environment to construct, display, and analyze Pert diagrams.
IEEE NetworkHeuristic layout algorithms for network management presentation services
28 Citations1988Gautam Kar, Brendan Madden +1 more
An approach is presented that uses the divide-and-conquer principle: a preprocessing step called heuristic clustering is used to partition a large network into logical groups, and a multiphase placement algorithms are used to produce coordinates for the nodes.
An interface description language for graph editors
27 Citations2003F. J. Newbery
The use of this interface description language is being incorporated into the EDGE graph editor, which will simplify the customization of graph editors.
SIAM Journal on ComputingOn the Optimal Layout of Planar Graphs with Fixed Boundary
27 Citations1987Bernd Becker, G. Hotz
For a large class of graphs, which, for example, occur in chip layout problems as the abstract structure of switching circuits, the existence and uniqueness of the optimal layout are shown.
Communications of the ACMAlgorithm design
26 Citations1987Robert E. Tarjan
The quest for efficiency in computational methods yields not only fast algorithms, but also insights that lead to elegant, simple, and general problem-solving methods.
International Journal of Computer MathematicsOn circular layouts<sup>∗</sup>
24 Citations1988Erkki Mäkinen
It is shown that also the circular variants of the linear cutwidth and linear dilation minimization problems are NP-complete and a method for drawing graphs is proposed based on the use of circular layouts.
Journal of AlgorithmsNP-completeness for minimizing maximum edge length in grid embeddings
24 Citations1985Zoe S Miller, James B. Orlin
It is shown that the determination of B2(G) for arbitrary G is NP-complete and the same proof can be used in showing the NP-completeness of minimizing |f| over all embeddings f: G → Z n of G into the n-dimensional integer lattice for any fixed n ≥ 2.
Graphical Data Structures for Ordered Sets
23 Citations1989Ivan Rival
Attention is shifting from the usual optimization themes to data structures; indeed, there is emerging a need for efficient data structures to code and store ordered sets.
IEEE Transactions on Circuits and SystemsPlanar embedding: linear-time algorithms for vertex placement and edge orderings
21 Citations1988R. Jayakumar, K. Thulasiraman +1 more
A linear-time algorithm to construct a very compact horvert representation of a planar graph that does not require the construction of the dual of the original graph.
IEEE Transactions on Systems Man and CyberneticsA proposed method for representing hierarchies
21 Citations1988M.G. Reggiani, F.E. Marchetti
A novel diagram helpful in displaying several types of hierarchies is defined and examples of mapping hierarchies taken from the existing literature are provided.
Lecture notes in computer scienceO(n2) algorithms for graph planarization
21 Citations1989R. Jayakumar, K. Thulasiraman +1 more
Two O(n2) planarization algorithms based on Lempel, Even, and Cederbaum's planarity testing algorithm and its implementation using PQ-trees are presented.
Geometry of planar graphs with angles
21 Citations1986V Vijayan
Some necessary conditions for the planarity of general angle-graphs are described, and necessary and sufficient conditions for some special classes of angle- graphs are given.
Optimal parallel algorithms for transitive closure and point location in planar structures
20 Citations1989Roberto Tamassia, Jeffrey Scott Vitter
This work presents parallel algorithms for several graph and geometric problems, including transitive closure and topological sorting in planar $st$-graphs, preprocessing planar subdivisions for point location queries, and construction of visibility representations and drawings of planar graphs.
Automatic layout of large directed graphs
20 Citations1988Eli Benjamin Messinger, Robert H. Henry
This dissertation studies algorithms that automatically produce aesthetically pleasing drawings of relational information using vertex and edge graphs, useful for building user-interfaces for tools that create and manipulate relational information, such as PERT chart editors.
Computers & Mathematics with ApplicationsGraph graphics: Theory and practice
20 Citations1988Chris Esposito
A graph-theoretic characterization of some of the problems described, followed by a discussion of their complexity, and several algorithms and heuristics for graph layout will be discussed.
Lecture notes in computer scienceKnowledge-based editors for directed graphs
19 Citations2006Walter F. Tichy, F. J. Newbery
Research in knowledge-based editors for the direct, visual manipulation of directed graphs produces an aesthetically pleasing layout of the graph automatically, freeing the user from cut-and-paste work after changes.
Lecture notes in computer scienceWeighted visibility graphs of bars and related flow problems
19 Citations1989David Kirkpatrick, Stephen Wismath
This paper provides a polynomial time solution to the problem of determining, for a given edge-weighted graph, whether there exists a corresponding layout of bars, and if so constructing such a layout.
International Journal of Man-Machine StudiesHeuristic graph displayer for G-Base
18 Citations1989Hiroyuki Watanabe
A proto-type graph displaying system for a data base management system based on a graph data model, which uses a heuristic algorithm for drawing a graph and which is portable to any workstation which supports the X-window system.
Lecture notes in computer scienceComputational complexity of geometric symmetry detection in graphs
17 Citations1991Joseph Manning
The central results show that for general graphs, however, detecting the presence of even a single axial or rotational symmetry is NP-complete.
Design Automation ConferenceAutomatic Generation of Digital System Schematic Diagrams
17 Citations1985Anjali Arya, Anshul Kumar +2 more
Software Practice and ExperienceGMB: A tool for manipulating and animating graph data structures
16 Citations1989D. Jablonowski, Vincent A. Guarna
This paper describes a tool graph originally developed for the Faust environment, GMB, which included providing an abstract graph data type for general use and animating graphs efficiently.
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.
Integration Mechanisms in the FIELD Environment
15 Citations1988Steven P. Reiss
FIELD is a mechanism that allows a wide variety of programming tools to be combined in an integrated environment that follows the UNIX philosophy of allowing independent tools to cooperate easily though simple conventions while at the same time providing the functionality necessary to a complex programming environment.
IEEE Transactions on Circuits and SystemsOn maximal planarization of nonplanar graphs
13 Citations1986K. Thulasiraman, R. Jayakumar +1 more
Journal of the ACMNote on Hopcroft and Tarjan's Planarity Algorithm
11 Citations1976Narsingh Deo
Errata are given for “Efficient Planarity Testing” by John Hopcroft and Robert Tarjan.
Journal of Combinatorial Theory Series BEdges without crossings in drawings of complete graphs
11 Citations1974Heiko Harborth, Ingrid Mengersen
On the Automated Drawing of Graphs
11 Citations1981Margaret Bernard
This paper considers the procedure for the automatic drawing of trees, and graphs displaying symmetry properties, based on a computer system for the adrawing of graphs.
Fundamenta InformaticaeA Note on the Median Heuristic for Drawing Bipartite Graphs
10 Citations1989Erkki Mäkinen
Computer-Aided DesignCASE: automatic generation of electrical diagrams
9 Citations1986Férid Aoudja, Marc Laborie +1 more
Part of an aircraft electrical circuit diagram generation process integration scheme (Aerospatiale CIRCE scheme), consisting of the automatic generation of wiring diagrams, is concerned.
Lecture notes in computer scienceCabri, an interactive system for graph manipulation
8 Citations1987Michel Dao, Masood Habib +2 more
Some characteristics of a toolset for the realization of interactive applications dealing with graphs and networks for a UNIX workstation are presented.
Software Practice and ExperienceA planar graph drawing program
5 Citations1971A.K. Hope
This paper describes a program, written in FORTRAN, for a 64K I.C.L. 4130 which will accept data describing the ordering of nodes and branches within the regions of a planar graph, and generate a two‐dimensional representation, without crossovers, from these data.
Lecture notes in computer scienceCentipede graphs and visibility on a cylinder
4 Citations1987Roberto Tamassia, Ioannis G. Tollis
A complete characterization of the class of graphs that admit a cylindric visibility representation, where vertices are represented by intervals parallel to the axis of the cylinder so that the edges of the graph correspond to visible intervals.
…