{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T03:28:00Z","timestamp":1648610880582},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1007\/bf01189069","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T22:39:28Z","timestamp":1108679968000},"page":"553-572","source":"Crossref","is-referenced-by-count":7,"title":["An efficient parallel algorithm for finding rectangular duals of plane triangular graphs"],"prefix":"10.1007","volume":"13","author":[{"given":"Xin","family":"He","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka, A Simple Tree Contraction Algorithm,J. Algorithms,10 (1989), 287?302.","journal-title":"J. Algorithms"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/net.3230170306","volume":"17","author":"J. Bhasker","year":"1987","unstructured":"J. Bhasker and S. Sahni, A Linear Time Algorithm To Check for the Existence of a Rectangular Dual of a Planar Triangulated Graph,Networks,17 (1987), 307?317.","journal-title":"Networks"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/BF01762117","volume":"3","author":"J. Bhasker","year":"1988","unstructured":"J. Bhasker and S. Sahni, A Linear Algorithm To Find a Rectangular Dual of a Planar Triangulated Graph,Algorithmica,3 (1988), 247?278.","journal-title":"Algorithmica"},{"key":"CR4","unstructured":"G. Brebner and D. Buchanan, On Compiling Structural Descriptions to Floorplans,Proc. IEEE Internat. Conf. on Computer-Aided Design, 1983, pp. 6?7."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N. Chiba","year":"1981","unstructured":"N. Chiba, T. Nishizeki, and N. Saito, A Linear 5-Coloring Algorithm of Planar Graphs,J. Algorithms,2 (1981), 317?327.","journal-title":"J. Algorithms"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, Matrix Multiplication via Arithmetic Progressions,Proc. 19th ACM Symp. on Theory of Computing, 1987, pp. 1?6.","DOI":"10.1145\/28395.28396"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"N. Dadoun and D. G. Kirkpatrick, Parallel Processing for Efficient Subdivision Search,Proc. ACM Symp. on Computational Geometry, 1987, pp. 205?214.","DOI":"10.1145\/41958.41980"},{"key":"CR8","unstructured":"P. Eades and R. Tamassia, Algorithms for Automatic Graph Drawing: An Annotated Bibliography, Technical Report CS-89-09, Department of Computer Science, Brown University, 1989."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"M. F\u00fcrer, X. He, M.-Y, Kao, and B. Raghavachari, O(n, log logn)-Work Parallel Algorithms for Straight-Line Grid Embedding of Planar Graphs,Proc. 4th ACM Symp. on Parallel Algorithms and Architectures, 1992, pp. 410?419.","DOI":"10.1145\/140901.141933"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(88)90164-0","volume":"28","author":"H. Gazit","year":"1988","unstructured":"H. Gazit and G. L. Miller, An Improved Parallel Algorithm that Computes the BFS Numbering of a Directed Graph,Inform. Process. Lett.,28 (1988), 61?65.","journal-title":"Inform. Process. Lett."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, S. A. Plotkin, and G. E. Shanon, Parallel Symmetry Breaking in Sparse Graphs,Proc. 19th ACM Symp. on Theory of Computing, 1987, pp. 315?324.","DOI":"10.1145\/28395.28429"},{"issue":"2","key":"CR12","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1137\/0218020","volume":"18","author":"T. Hagerup","year":"1989","unstructured":"T. Hagerup, M. Chrobak, and K. Diks, Optimal Parallel 5-Coloring of Planar Graphs,SIAM J. Comput.,18(2), (1989), 288?300.","journal-title":"SIAM J. Comput"},{"issue":"6","key":"CR13","doi-asserted-by":"crossref","first-page":"1218","DOI":"10.1137\/0222072","volume":"22","author":"X. He","year":"1993","unstructured":"X. He, On Finding the Rectangular Duals of Planar Triangulated Graphs,SIAM J. Comput.,22(6) (1993), 1218?1226.","journal-title":"SIAM J. Comput."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/BF01840403","volume":"5","author":"X. He","year":"1990","unstructured":"X. He, Efficient Parallel and Sequential Algorithms for 4-Coloring Perfect Planar Graphs,Algorithmica,5 (1990), 545?559.","journal-title":"Algorithmica"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"W. R. Heller, G. Sorkin, and K. Maling, The Planar Package Planner for System Designers,Proc. 19th Design Automation Conference, 1982, pp. 253?260.","DOI":"10.1109\/DAC.1982.1585509"},{"key":"CR16","first-page":"26","volume-title":"Ph.D. Thesis","author":"M. Y. Hsueh","year":"1979","unstructured":"M. Y. Hsueh, Symbolic Layout and Compaction of Integrated Circuits, Ph.D. Thesis, University of California, Berkeley, 1979, pp. 26?28 and 46?52."},{"key":"CR17","unstructured":"M. Y. Hsueh and D. O. Pederson, Computer-Aided Layout of LSI Circuit Building-Blocks,Proc. IEEE Internat. Symp. on Circuits and Systems, 1979, pp. 474?477."},{"issue":"2","key":"CR18","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1137\/0211024","volume":"11","author":"J. Ja'Ja'","year":"1982","unstructured":"J. Ja'Ja' and J. Simon, Parallel Algorithms in Graph Theory: Planarity TestingSIAM J. Comput.,11(2) (1982), 314?328.","journal-title":"SIAM J. Comput."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0012-365X(76)90065-0","volume":"14","author":"G. R. Kampen","year":"1976","unstructured":"G. R. Kampen, Orienting Planar Graphs,Discrete Math.,14 (1976), 337?341.","journal-title":"Discrete Math."},{"issue":"1","key":"CR20","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D. G. Kirkpatrick, Optimal Search in Planar Subdivisions,SIAM J. Comput.,12(1) (1983), 28?35.","journal-title":"SIAM J. Comput."},{"key":"CR21","first-page":"145","volume":"5","author":"K. Ko?mi?ski","year":"1985","unstructured":"K. Ko?mi?ski and E. Kinnen, Rectangular Dual of Planar Graphs,Network,5 (1985), 145?157.","journal-title":"Network"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"K. Maling, S. H. Mueller, and W. R. Heller, On Finding Most Optimal Rectangular Package Plans,Proc. 19th Design Automation Conference, 1982, pp. 663?670.","DOI":"10.1109\/DAC.1982.1585567"},{"key":"CR23","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and J. Reif, An Optimal Parallel Algorithm for Graph Planarity,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 282?287.","DOI":"10.1109\/SFCS.1989.63491"},{"issue":"4","key":"CR24","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosentiehl","year":"1986","unstructured":"P. Rosentiehl and R. E. Tarjan, Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations,Discrete Comput. Geom.,1(4) (1986), 343?353.","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"CR25","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"R. Tamassia, On Embedding a Graph in the Grid with the Minimum Number of Bends,SIAM J. Comput.,16(3) (1987), 421?444.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"CR26","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"R. Tamassia and I. G. Tollis, A Unified Approach to Visibility Representation of Planar Graphs,Discrete Comput. Geom.,1(4) (1986), 321?341.","journal-title":"Discrete Comput. Geom."},{"issue":"9","key":"CR27","doi-asserted-by":"crossref","first-page":"1230","DOI":"10.1109\/31.34669","volume":"36","author":"R. Tamassia","year":"1989","unstructured":"R. Tamassia and I. G. Tollis, Planar Grid Embedding in Linear Time,IEEE Trans. Circuits and Systems,36(9) (1989), 1230?1234.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"CR28","unstructured":"R. Tamassia and I. G. Tollis, Tessellation Representations of Planar Graphs,Proc. 27th Annual Allerton Conf., (1989), pp. 48?57."},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"R. Tamassia, I. G. Tollis, and J. S. Vitter, Lower Bounds and Parallel Algorithms for Planar Orthogonal Grid Drawings,Proc. IEEE Symp. on Parallel and Distributed Processing, 1991, pp. 386?393.","DOI":"10.1109\/SPDP.1991.218215"},{"issue":"4","key":"CR30","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0220045","volume":"20","author":"R. Tamassia","year":"1991","unstructured":"R. Tamassia and J. S. Vitter, Parallel Transitive Closure and Point Location in Planar Structures,SIAM J. Comput.,20(4) (1991), 708?725.","journal-title":"SIAM J. Comput."},{"key":"CR31","unstructured":"K. Zilbert and R. Saal, On Computer-Aided Hybrid Circuit Layout,Proc. IEEE Internat. Symp. on Circuits and Systems, 1974, pp. 314?318."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01189069.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01189069\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01189069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:40:27Z","timestamp":1586119227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01189069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["BF01189069"],"URL":"https:\/\/doi.org\/10.1007\/bf01189069","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}