Optimal parallel algorithms for transitive closure and point location in planar structures

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	[1] F.N. Afrati, D.Q. Goldin & P.C. Kanellakis, "Efficient Parallelism for Structured Data: Directed Reachability in S-P Dags," Dept. Computer Science, Brown Univ., Tecnical Report CS-88-07, 1988.
	2	[2] M.J. Atallah, R. Cole & M.T. Goodrich, "Cascading Divide-and Conquer: A Technique for Designing Parallel Algorithms," Proc. 28th IEEE Symp. on Foundations of Computer Science (1987), 151-160.
	3	B. Chazelle , H. Edelsbrunner , L. Guibas, The complexity of cutting convex polytypes, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.66-76, January 1987, New York, New York, United States [doi>10.1145/28395.28403]
	4	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]
	5	[5] R. Cole, "Parallel Merge Sort," Proc. 27th IEEE Symp. on Foundations of Computer Science (1986), 511-516.
	6	[6] R. Cole & U. Vishkin, "Approximate and Exact Parallel Scheduling with Applications to List, Tree, and Graph Problems," Proc. 27th IEEE Symp. on Foundations of Computer Science (1986), 478-491.
	7	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	8	N. Dadoun , D. G. Kirkpatrick, Parallel processing for efficient subdivision search, Proceedings of the third annual symposium on Computational geometry, p.205-214, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41980]
	9	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]
	10	G. Di Battista , R. Tamassia , I. G. Tollis, Area requirement and symmetry display in drawing graphs, Proceedings of the fifth annual symposium on Computational geometry, p.51-60, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73839]
	11	[11] P. Duchet, Y. Hamidoune, M. Las Vergnas & H. Meyniel, "Representing a Planar Graph by Vertical Lines Joining Different Levels," Discrete Mathematics 46 (1983), 319-321.
	12	Peter Eades , Roberto Tamassia, Algorithms for Drawing Graphs: An Annotated Bibliography, Brown University, Providence, RI, 1988
	13	Ta. Asano, A new point-location algorithm and its practical efficiency: comparison with existing algorithms, ACM Transactions on Graphics (TOG), v.3 n.2, p.86-109, April 1984 [doi>10.1145/357337.357338]
	14	Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
	15	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]
	16	[16] L.J. Guibas & F.F. Yao, "On Translating a Set of Rectangles," in Advances in Computing Research, vol. 1, F.P. Preparata, ed., JAI Press Inc., Greenwich, CT, 1983, 61-77.
	17	[17] M.Y. Hsueh & D.O. Pederson, "Computer-Aided Layout of LSI Circuit Building-Blocks," Proc. IEEE Int. Symp. on Circuits and Systems (1979), 474-477.
	18	[18] J. Ja'Ja' & J. Simon, "Parallel Algorithms in Graph Theory: Planarity Testing," SIAM J. Comput. 11 (1982), 314-328.
	19	[19] T. Kameda, "On the Vector Representation of the Reachability in Planar Directed Graphs," Information Processing Letters 3 (1975), 75-77.
	20	[20] D. Kelly & I. Rival, "Planar Lattices," Canadian J. Mathematics 27 (1975), 636-665.
	21	[21] D.G. Kirkpatrick, "Optimal Search in Planar Subdivisions," SIAM J. Computing 12 (1983), 28-35.
	22	David G. Kirkpatrick, Establishing order in planar subdivisions, Discrete & Computational Geometry, v.3 n.3, p.267-280, Jan., 1988 [doi>10.1007/BF02187912]
	23	[23] P.N. Klein & J.H. Reif, "An Efficient Parallel Algorithm for Planarity," Proc. 27th IEEE Symp. on Foundations of Computer Science (1986), 456-477.
	24	[24] D.T. Lee & F.P. Preparata, "Location of a Point in a Planar Subdivision and its Applications," SIAM J. Computing 6 (1977), 594-606.
	25	[25] A. Lempel, S. Even & I. Cederbaum, "An Algorithm for Planarity Testing of Graphs," Theory of Graphs, Int. Symposium (1966), 215-232.
	26	Yael Maon , Baruch Schieber , Uzi Vishkin, Parallel ear decomposition search (EDS) and st-numbering in graphs, Theoretical Computer Science, v.47 n.3, p.277-298, Nov., 1986
	27	Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
	28	[28] R.H.J.M. Otten & J.G. van Wijk, "Graph Representations in Interactive Layout Design," Proc. IEEE Int. Symp. on Circuits and Systems (1978), 914-918.
	29	Takao Ozawa , H. Takahashi, A graph-planarization algorithm and its application to random graphs, Proceedings of the 17th Symposium of Research Institute of Electric Communication on Graph Theory and Algorithms, p.95-107, October 24-25, 1980
	30	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	31	[31] F.P. Preparata & R. Tamassia, "Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures," Proc. 29th IEEE Symp. on Foundations of Computer Science (1988), 558-567.
	32	Franco P. Preparata , Roberto Tamassia, Fully dynamic point location in a monotone subdivision, SIAM Journal on Computing, v.18 n.4, p.811-830, Aug. 1989 [doi>10.1137/0218056]
	33	[33] I. Rival & J. Urrutia, "Representing Orders by Translating Convex Figures in the Plane," Order 4 (1988), 319- 339.
	34	[34] P. Rosenstiehl & R.E. Tarjan, "Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations," Discrete & Computational Geometry 1 (1986), 342-351.
	35	John E. Savage , Markus G. Wloka, Parallel constraint graph generation, Proceedings of the decennial Caltech conference on VLSI on Advanced research in VLSI, p.241-259, June 1989, Cambridge, Massachusetts, United States
	36	B. Schieber , U. Vishkin, On finding lowest common ancestors: simplification and parallelization (extended summary), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	37	[37] M. Schlag, F. Luccio, P. Maestrini, D.T. Lee & C.K. Wong, "A Visibility Problem in VLSI Layout Compaction," in Advances in Computing Research, vol. 2, F.P. Preparata, ed., JAI Press Inc., Greenwich, CT, 1985, 259-282.
	38	[38] J.A. Storer, "On Minimal Node-Cost Planar Embeddings," Networks 14 (1984), 181-212.
	39	Roberto Tamassia, A Dynamic Data Structure for Planar Graph Embedding (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.576-590, July 11-15, 1988
	40	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]
	41	[41] R. Tamassia & F.P. Preparata, "Dynamic Maintenance of Planar Digraphs, with Applications," Algorithmica (1989, to appear).
	42	[42] R. Tamassia & I.G. Tollis, "A Unified Approach to Visibility Representations of Planar Graphs," Discrete & Computational Geometry 1 (1986), 321-341.
	43	[43] R. Tamassia & I.G. Tollis, "Efficient Embedding of Planar Graphs in Linear Time," Proc. IEEE Int. Symp. on Circuits and Systems (1987), 495-498.
	44	[44] S. Wimer, I. Koren & I. Cederbaum, "Floorplans, Planar Graphs, and Layouts," IEEE Trans. on Circuits and Systems 35 (1988), 267-278.
	45	Stephen K. Wismath, Characterizing bar line-of-sight graphs, Proceedings of the first annual symposium on Computational geometry, p.147-152, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323253]