Convex drawings of graphs in two and three dimensions (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Convex drawings of graphs in two and three dimensions (preliminary version)

Full text

Pdf (1.08 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 319 - 328

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Marek Chrobak	Dept. of Computer Science, Univ. of California, Riverside, CA
Michael T. Goodrich	Dept. of Computer Science, Johns Hopkins Univ , Baltimore, MD
Roberto Tamassia	Dept of Computer Science, Brown Univ., Providence, RI

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): 4, Downloads (12 Months): 33, 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/237218.237401 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	G. E. Andrews. A lower bound for the volume of strictly convex bodies with many boundary lattice points. Trans. Amer. Math. Soc., 106:270-279, 1963.
	2	B. Becker , G. Hotz, On the optimal layout of planar graphs with fixed boundary, SIAM Journal on Computing, v.16 n.5, p.946-972, Oct. 1987 [doi>10.1137/0216061]
	3	B. Becker , H. G. Osthof, Layouts with wires of balanced length, Information and Computation, v.73 n.1, p.45-58, April 1987 [doi>10.1016/0890-5401(87)90039-3]
	4	N. Chiba, K. Onoguchi, and T. Nishizeki. Drawing planar graphs nicely. Acts Inform., 22:187-201, 1985.
	5	N. Chiba, T. Yamanouchi, and T. Nishizeki. Linear algorithms for convex drawings of planar graphs. In j. A. Bondy and U. S. R. Murty, editors, Progress in Graph Theory, pages 153- 173. Academic Press, New York, NY, 1984.
	6	M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. Technical Report RUU-93-45, Dept. of Computer Sci., Utrecht Univ., 1993.
	7	Marek Chrobak , Shin-Ichi Nakano, Minimum-Width Grid Drawings of Plane Graphs, Proceedings of the DIMACS International Workshop on Graph Drawing, p.104-110, October 10-12, 1994
	8	M. Chrobak , T. H. Payne, A linear-time algorithm for drawing a planar graph on a grid, Information Processing Letters, v.54 n.4, p.241-246, May 26, 1995 [doi>10.1016/0020-0190(95)00020-D]
	9	Robert F. Cohen , Peter Eades , Tao Lin , Frank Ruskey, Three-Dimensional Graph Drawing, Proceedings of the DIMACS International Workshop on Graph Drawing, p.1-11, October 10-12, 1994
	10	R. Connelly. Rigidity and energy, invent. Math., 66:11-33, 1982.
	11	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	12	H. Crapo and W. Whitely. Statics of frameworks and motions of panel structures, a projective geometric introduction. Structural Topology, 6:42-82, 1982.
	13	Gautam Das , Michael T. Goodrich, On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra (Preliminary Version), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.74-85, August 16-18, 1995
	14	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]
	15	H. de Fraysseix, j. Pach, and R. Pollack. How to draw a planar graph on a grid. Cornbinatorzca, 10:41-51, 1990.
	16	Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, v.4 n.5, p.235-282, Oct. 1994 [doi>10.1016/0925-7721(94)00014-X]
	17	Giuseppe Di Battista , Roberto Tamassia , Ioannis G. Tollis, Area requirement and symmetry display of planar upward drawings, Discrete & Computational Geometry, v.7 n.4, p.381-401, 1992 [doi>10.1007/BF02187850]
	18	Giuseppe Di Battista , Roberto Tamassia , Luca Vismara, On-Line Convex Plabarity Testing, Proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science, p.242-255, June 16-18, 1994
	19	Michael B. Dillencourt , Warren D. Smith, A linear-time algorithm for testing the inscribability of trivalent polyhedra, Proceedings of the eighth annual symposium on Computational geometry, p.177-185, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142715]
	20	Peter Eades , Patrick Garvan, Drawing Stressed Planar Graphs in Three Dimensions, Proceedings of the Symposium on Graph Drawing, p.212-223, September 20-22, 1995
	21	P. Eades, C. Stirk, and S. Whitesides. The techniques of Komolgorov and Bardzin for three dimensional orthogonal graph drawings. Manuscript, Dept. of Computer Sci., Univ. of Newcastle, 1995.
	22	I. Fary. On straight lines representation of planar graphs. Acta Sci. Math. $zeged., 11:229- 233, 1948.
	23	M. Formann , T. Hagerup , J. Haralambides , M. Kaufmann , F. T. Leighton , A. Symvonis , E. Welzl , G. Woeginger, Drawing graphs in the plane with high resolution, SIAM Journal on Computing, v.22 n.5, p.1035-1052, Oct. 1993 [doi>10.1137/0222063]
	24	Ashim Garg , Roberto Tamassia, Planar Drawings and Angular Resolution: Algorithms and Bounds (Extended Abstract), Proceedings of the Second Annual European Symposium on Algorithms, p.12-23, September 26-28, 1994
	25	J. R. Gilbert , R. E. Tarjan, The analysis of a nested dissection algorithm, Numerische Mathematik, v.50 n.4, p.377-404, FEB. 1987 [doi>10.1007/BF01396660]
	26	B. Griinbaum. Convex Polytopes. Wiley, New York, NY, 1967.
	27	S. Mehdi Hashemi , Ivan Rival, Upward Drawings to Fit Surfaces, Proceedings of the International Workshop on Orders, Algorithms, and Applications, p.53-58, July 04-08, 1994
	28	C. D. Hodgson, I. Rivin, and W. D. Smith. A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere. Bull. (New Series) of the AMS, 27(2):246-251, 1992.
	29	J. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Cornput., 2:135-158, 1973.
	30	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]
	31	J. E. Hopcroft and P. J. Kahn. A paradigm for robust geometric algorithms. Algoriihmica, 7:339-380, 1992.
	32	Thierry Jéron , Claude Jard, 3D Layout of Reachability Graphs of Communicating Processes, Proceedings of the DIMACS International Workshop on Graph Drawing, p.25-32, October 10-12, 1994
	33	G. Kant. Drawing planar graphs using the canonical ordering. Algorzthmica (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia). (to appear).
	34	G. Kant. Drawing planar graphs using the lmcordering. In Proc. 33th Annu. IEEE Sympos. Found. Comput. Sc~., pages 101-110, 1992.
	35	Y. Lin and S. Skiena. Complexity aspects of visibility graphs. Technical Report 92//08, SUNY Stony Brook, 1992.
	36	Giuseppe Liotta , Giuseppe Di Battista, Computing Proximity Drawings of Trees in the 3-Dimemsional Space, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.239-250, August 16-18, 1995
	37	R. J. Lipton, D. J. Rose, and R. E. Tarjan. (~eneralized nested dissection. SIA}VI J. Aruraer. Anal., 16(2):346-358, 1979.
	38	R. J. Lipton and R. E. Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9:615-627, 1980.
	39	Seth Malitz , Achilleas Papakostas, [doi>10.1137/S0895480193242931]
	40	J. C. Maxwell. On reciprocal figures and diagrams of forces. Phil. Mag. Set., 27:250-261, 1864.
	41	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	42	Steven P. Reiss, 3-D Visualization of Program Information, Proceedings of the DIMACS International Workshop on Graph Drawing, p.12-24, October 10-12, 1994
	43	S. P. Reiss. An engine for the 3D visualization of program information. J. Visual Languages and Computing (special issue on Graph Visualization, edited by i. F. Cruz and P. Eades), 6(3), 1995.
	44	Walter Schnyder, Embedding planar graphs on the grid, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.138-148, January 22-24, 1990, San Francisco, California, United States
	45	W. Schnyder and W. Trotter. Convex drawings of planar graphs. Abstracts of the AMS, 92T- 05-135, 1992.
	46	S. K. Stein. Convex maps. Proc. Amer. Math. Soc., 2:464-466, 1951.
	47	E. Steinitz and H. Rademacher. Vorlesungen iiber die Theorie dec PoIyeder. Julius Springer, Berlin, Germany, 1934.
	48	C. Thomassen. Planarity and duality of finite and infinite planar graphs. J. Combin. Theory Set. B, 29:244-271, 1980.
	49	C. Thomassen. Plane representations of graphs. In J. A. Bondy and U. S. R. Murty, editors, Progress in Graph Theory, pages 43- 69. Academic Press, New York, NY, 1984.
	50	W. T. Tutte. Convex representations of graphs. Proceedings London Mathematical Society, 10:304-320, 1960.
	51	W. T. Tutte. How to draw a graph. Proceedings London Mathematical Society, 3(13):743- 768, 1963.
	52	W. Whitney. Motions and stresses of projected polyhedra. Structural Topology, 7:13-38, 1982.

CITED BY 9

	Ruth Haas , David Orden , Günter Rote , Francisco Santos , Brigitte Servatius , Hermann Servatius , Diane Souvaine , Ileana Streinu , Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Éric Colin de Verdière , Michel Pocchiola , Gert Vegter, Tutte's barycenter method applied to isotopies, Computational Geometry: Theory and Applications, v.26 n.1, p.81-97, August 2003
	Ruth Haas , David Orden , Günter Rote , Francisco Santos , Brigitte Servatius , Herman Servatius , Diane Souvaine , Ileana Streinu , Walter Whiteley, Planar minimally rigid graphs and pseudo-triangulations, Computational Geometry: Theory and Applications, v.31 n.1-2, p.31-61, May 2005
	Günter Rote, Strictly convex drawings of planar graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Emilio Di Giacomo , Giuseppe Liotta , Henk Meijer, Computing straight-line 3D grid drawings of graphs in linear volume, Computational Geometry: Theory and Applications, v.32 n.1, p.26-58, September 2005
	Paolo Penna , Paola Vocca, Proximity drawings in polynomial area and volume, Computational Geometry: Theory and Applications, v.29 n.2, p.91-116, October 2004
	David R. Wood, Optimal three-dimensional orthogonal graph drawing in the general position model, Theoretical Computer Science, v.299 n.1-3, p.151-178, 18 April 2003
	Peter Brass , Eowyn Cenek , Cristian A. Duncan , Alon Efrat , Cesim Erten , Dan P. Ismailescu , Stephen G. Kobourov , Anna Lubiw , Joseph S. B. Mitchell, On simultaneous planar graph embeddings, Computational Geometry: Theory and Applications, v.36 n.2, p.117-130, February, 2007
	Seok-Hee Hong , Hiroshi Nagamochi, Convex drawings of graphs with non-convex boundary constraints, Discrete Applied Mathematics, v.156 n.12, p.2368-2380, June, 2008