Area requirement and symmetry display in drawing graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Area requirement and symmetry display in drawing graphs

Full text

Pdf (926 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fifth annual symposium on Computational geometry table of contents

Saarbruchen, West Germany

Pages: 51 - 60

Year of Publication: 1989

ISBN:0-89791-318-3

Authors

G. Di Battista	Dipartimento di Informatica e Sistemistica - University of Rome, Via Buonarroti, 12 - 00185 Rome, Italy
R. Tamassia	Department of Computer Science - Brown University, Box 1910 - Providence, RI
I. G. Tollis	Department of Computer Science - The University of Texas at Dallas, P.O. Box 830688, MP 3.1- Richardson, TX

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73833.73839 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Chiba, K. Onoguchi, and T. Nishizeki, "Drawing Planar Graphs Nicely," Acta Informatica, vol. 22, pp. 187-201, 1985.
	2	Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, Journal of Computer and System Sciences, v.30 n.1, p.54-76, Feb. 1985 [doi>10.1016/0022-0000(85)90004-2]
	3	M. Chrobak, "A Linear-Time Algorithm for Drawing a Planar Graph on a Grid," Manuscript, Univ. California, Riverside, 1988.
	4	Giuseppe Di Battista , Roberto Tamassia, Algorithms for plane representations of acyclic digraphs, Theoretical Computer Science, v.61 n.2-3, p.175-198, Nov. 1988 [doi>10.1016/0304-3975(88)90123-5]
	5	D. Dolev, F.T. Leighton, and H. Trickey, "Planar Embedding of Planar Graphs," in Advances in Computing Research, vol. 2, F.P. Preparata (Ed.), JAI Press Inc., pp. 147-161.1984.
	6	P. Eades, "A Heuristic for Graph Drawing," Congressus Numerantium, vol. 42, pp. 149-160, 1984.
	7	Peter Eades , Roberto Tamassia, Algorithms for Drawing Graphs: An Annotated Bibliography, Brown University, Providence, RI, 1988
	8	I. Fary, "On Straight Lines Representations of Planar Graphs," Acta Sci. Math. Szeged, vol. 11, pp. 229- 233,1948.
	9	Hubert de Fraysseix , János Pach , Richard Pollack, Small sets supporting fary embeddings of planar graphs, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.426-433, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62254]
	10	L.J. Guibas and F.F. Yao, "On Translating a Set of Rectangles," in Advances in Computing Research, vol. 1, F.P. Preparata (Ed.), JAI Press Inc., pp. 61-77, 1983.
	11	John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
	12	M.Y. Hsueh and D.O. Pederson, "Computer-Aided Layout of LSI Circuit Building-Blocks," Proc. IEEE Int. Symp. on Circuits and Systems, pp. 474-477, 1979.
	13	T. Kameda, "On the Vector Representation of the Reachability in Planar Directed Graphs," Information Processing Letters, vol. 3, no. 3, pp. 75-77, 1975.
	14	D. Kelly and I. Rival, "Planar Lattices," Canadian J. Mathematics, vol. 27, no. 3, pp. 636-665, 1975.
	15	D. Kelly, Fundamentals of planar ordered sets, Discrete Mathematics, v.63 n.2-3, p.197-216, Feb. 1987 [doi>10.1016/0012-365X(87)90008-2]
	16	A. Lempel, S. Even, and I. Cederbaum, "An Algorithm for Planarity Testing of Graphs," Theory of Graphs, Int. Symposium, Rome, pp. 215-232,1966.
	17	R. J. Lipton , S. C. North , J. S. Sandberg, A method for drawing graphs, Proceedings of the first annual symposium on Computational geometry, p.153-160, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323254]
	18	J. Manning and M.J. Atallah, "Fast Detection and Display of Symmetry in Outerplanar Graphs," Technical Report CSD-TR-606, Dept. of Computer Sciences, Purdue Univ., West Lafayette, IN, 1986.
	19	J. Manning and MJ. Atallah, "Fast Detection and Display of Symmetry in Trees," Congressus Numerantium, 1989 (to appear).
	20	R. Read, "New Methods for Drawing a Planar Graph Given the Cyclic order of the Edges at Each Vertex," Research Report CORR 86-14, Faculty of Mathematics, Univ. of Waterloo, July 1986.
	21	E. Reingold and J. Tilford, "Tidier Drawing of Trees," IEEE Trans. on Software Engineering, vol. SE-7, no. 2, pp. 223-228,1981.
	22	I. Rival and J. Urrutia, "Representing Orders by Translating Convex Figures in the Plane," Order, vol. 4, pp. 319-339, 1988.
	23	P. Rosenstiehl and R.E. Tarjan, "Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations," Discrete & Computational Geometry, vol. 1, no. 4, pp. 342-351, 1986.
	24	W. Schnyder, "Embedding Planar Graphs on the Grid," Congressun Numerantium, 1989 (to appear).
	25	S.K. Stein, "Convex Maps," Proc. Amer. Math. Soc., vol. 2, pp. 464-466,1951.
	26	E. Steinitz and H. Rademacher, Vorlesung uber die Theorie der Polyeder, Springer, Berlin, 1934.
	27	J.A. Storer, "On Minimal Node-Cost Planar Embeddings," Networks, vol. 14, pp. 181-212,1984.
	28	K. Supowit and E. Reingold, "The Complexity of Drawing Trees Nicely,'* Acta Informatica, vol. 18, pp. 377-392, 1983.
	29	R. Tamassia and I.G. Tollis, "A Unified Approach to Visibility Representations of Planar Graphs," Discrete & Computational Geometry, vol. 1, no. 4, pp. 321-341, 1986.
	30	Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends, SIAM Journal on Computing, v.16 n.3, p.421-444, June 1987 [doi>10.1137/0216030]
	31	R. Tamassia and I.G. Tollis, "Efficient Embedding of Planar Graphs in Linear Time," Proc. IEEE Int. Symp. on Circuits and Systems, Philadelphia, pp. 495-498,1987.
	32	Roberto Tamassia , Giuseppe Di Battista , Carlo Batini, Automatic graph drawing and readability of diagrams, IEEE Transactions on Systems, Man and Cybernetics, v.18 n.1, p.61-79, January/February 1988 [doi>10.1109/21.87055]
	33	W.T. Tutte, "How to Draw a Graph," Proc. London Math Soc., vol. 3, no. 13, pp. 743-768, 1963.
	34	K. Wagner, "Bemerkungen zum Vierfarbenproblem," Jber. Deutsch. Math.-Verein, vol. 46, pp. 26- 32, 1936.
	35	Donald Roy Woods, Drawing planar graphs, 1981

CITED BY 9

	Paola Bertolazzi , Giuseppe Di Battista, On upward drawing testing of triconnected digraphs (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.272-280, June 10-12, 1991, North Conway, New Hampshire, United States
	Siu-Wing Cheng , Moon-Pun Ng, Isomorphism testing and display of symmetries in dynamic trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.202-211, January 28-30, 1996, Atlanta, Georgia, United States
	R. F. Cohen , G. Di Battista , R. Tamassia , I. G. Tollis , P. Bertolazzi, A framework for dynamic graph drawing, Proceedings of the eighth annual symposium on Computational geometry, p.261-270, June 10-12, 1992, Berlin, Germany
	Robert F. Cohen , Peter Eades , Tao Lin , Frank Ruskey, Volume upper bounds for 3D graph drawing, Proceedings of the 1994 conference of the Centre for Advanced Studies on Collaborative research, p.11, October 31-November 03, 1994, Toronto, Ontario, Canada
	Kelly A. Lyons, Cluster busting in anchored graph drawing, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Kelly A. Lyons, Cluster busting in anchored graph drawing, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
	Michael D. Hutton , Anna Lubiw, Upward planar drawing of single source acyclic digraphs, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.203-211, January 28-30, 1991, San Francisco, California, United States
	Patrick J. Finnigan , Kelly A. Lyons, Narratives of space and time: visualization for distributed applications, Proceedings of the 1991 conference of the Centre for Advanced Studies on Collaborative research, October 28-30, 1991, Toronto, Ontario, Canada
	R. Tamassia , J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.399-408, June 18-21, 1989, Santa Fe, New Mexico, United States