Drawing Graphs by Example Efficiently: Trees and Planar Acyclic Digraphs (Extended Abstract)

Cruz, Isabel F. and Garg, Ashim (1995) Drawing Graphs by Example Efficiently: Trees and Planar Acyclic Digraphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 404-415 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_394).

Full text not available from this repository.


Constraint-based graph drawing systems provide expressive power and flexibility. Previously proposed approaches make use of general constraint solvers, which are inefficient, and of textual specification of constraints, which can be long and difficult to understand. In this paper we propose the use of a constraint-based visual language for constructing planar drawings of trees, series-parallel graphs, and acyclic digraphs in linear time. A graph drawing system based on our approach can therefore provide the power of constraint-based graph drawing, the simplicity of visual specifications, and the computational efficiency that is typical of the algorithmic-based approaches.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_394
Classifications:S Software and Systems > S.001 General
M Methods > M.900 Tree
M Methods > M.500 Layered
G Algorithms and Complexity > G.630 Labeling
ID Code:240

Repository Staff Only: item control page


P. Bertolazzi, R. F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. How to Draw a Series-parallel Digraph. In Proc. 3rd Scand. Workshop Algorithm Theory, Lecture Notes in Computer Science, vol. 621, pages 272-283. Springer-Verlag, 1992.

P. Bertolazzi and G. Di Battista. On Upward Drawing Testing Triconnected Digraphs. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 272-280, 1991.

P. Bertolazzi, G. Di Battista, and G. Liotta. Parametric Graph Drawing. Technical Report 6/67, Consiglio Nazionale delle Ricerche, Rome, Italy, July 1992.

A. Borning. The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory. ACM Transactions on Programming Languages and Systems, 3(4):353-387, October 1981.

F. Brandenburg. Layout Graph Grammars: the Placement Approach. In Graph Grammars and their Application to Comp. Sc.. LNCS 532, Springer Verlag, 1991.

M. Brown, J. Domingue, B. Price, and J. Stasko, editors. ACM SIGCHI '94 Workshop on Software Visualization, Boston, MA, April 1994.

R. F. Cohen, G. Di Battista, R. Tamassia, and I.G. Tollis. A Framework for Dynamic Graph Drawing. SIAM J. Comput., to appear.

I.F. Cruz. DOODLE: A Visual Language for Object-Oriented Databases. In ACM-SIGMOD Intl. Conf. on Management of Data, pages 71-80, 1992.

I.F. Cruz. User-defined Visual Query Languages. In IEEE Symposium on Visual Languages (VL '94), 1994.

I.F. Cruz. Expressing Constraints for Data Display Specification: A Visual Approach. In V. Saraswat and P. V. Hentenryck, editors, Principles and Practices of Constraint Programming, pages 443-468. The MIT Press, 1995.

I.F. Cruz, R. Tamassia and P. Van Hentenryck. A Visual Approach to Graph Drawing. In Graph Drawing '93, Sèvres, France, September 1993.

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Tech. report, Dept. of Comp. Sc., Brown University, March 1993. To appear in Comp. Geometry: Theory and Applications.

G. Di Battista, A. Gianmarco, G. Santucci, and R. Tamassia. The Architecture of Diagram Server. In Proc. of IEEE Workshop on Visual Languages, 1990.

G. Di Battista and R. Tamassia. Algorithms for Plane Representations of Acyclic Digraphs. Theoret. Comput. Sci., 61:175-198, 1988.

G. Di Battista, R. Tamassia, and I.G. Tollis.Area Requirement and Symmetry Display of Planar Upward Drawings. Discrete Comput. Geom., 7:381-401, 1992.

P. Eades and T. Lin Algorithmic and Declarative Approaches to Aestetic Layout. In Graph Drawing '93, Sèvres, France, September 1993.

A. Garg and R. Tamassia. On the Computational Complexity of Upward and Rectilinear Planarity Testing. Graph Drawing '94 (DIMACS workshop on Graph Drawing), 1994.

J. G. Greeno. Conceptual Entities. Mental Models, D. Genter and A. L. Stevens, ed., Lawrence Erlbaum Associates, Hillsdale, N.J., pp. 227-252.

T. Kamada. Visualizing Abstract Objects and Relations - A Constraint-Based Approach. World Scientific, Singapore, 1989.

P. C. Kanellakis, G. M. Kuper, and P.Z. Revesz. Constraint Query Languages. Technical Report CS-90-31, Dept. of Comp. Sc., Brown University, November 1990.

D. Kelly. Fundamentals of Planar Ordered Sets. Discrete Math., 63:197-216, 1987.

M. Kifer, G. Lausen, and J. Wu. Logic Foundations of Object-Oriented and Frame-Based Languages. Technical Report 90/14 (2-nd revision), Department of Computer Science, SUNY Stony Brook, 1990. To appear in JACM.

T. Lin. A General Schema for Diagrammatic User Interface. PhD thesis, Department of Computer Science, University of Newcastle, Australia, 1993.

J. Marks. A Formal Specification for Network Diagrams That Facilitates Automated Design. Journal of Visual Languages and Computing, 2:395-414, 1991.

I. Rival. Reading, Drawing, and Order. In I.G. Rosenberg and G. Sabidussi, editors, Algebras and Orders, pages 359-404. Kluwer Academic Publishers, 1993.

R. Tamassia, G. Di Battista, and C. Batini. Automatic Graph Drawing and Readability of Diagrams. IEEE Trans. on Sys., Man and Cyber., 18(1):10-21, 1988.

R. Tamassia and I. G. Tollis. A Unified Approach to Visibility Representations of Planar Graphs. Discrete Comput. Geom., 1(4):321-341, 1986.

E. R. Tufte. The Visual Display of Quantitative Information. Graphics Press., Cheshire, Conn., 1993.

J. D. Ullman. Principles of Database and Knowledge-Base Systems, volume II. Computer Science Press, Inc., Rockville, Maryland, 1989.