{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:22:22Z","timestamp":1787505742737,"version":"build-2736575974"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"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":[[1990,6]]},"DOI":"10.1007\/bf01840401","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T18:41:35Z","timestamp":1119984095000},"page":"509-527","source":"Crossref","is-referenced-by-count":28,"title":["Dynamic maintenance of planar digraphs, with applications"],"prefix":"10.1007","volume":"5","author":[{"given":"Roberto","family":"Tamassia","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Franco P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"no. 2","key":"BF01840401_CR1","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, vol. 3, no. 2, pp. 247\u2013278, 1988.","journal-title":"Algorithmica"},{"key":"BF01840401_CR2","volume-title":"American Mathematical Society Colloquium Publications, vol. 25","author":"G. Birkhoff","year":"1979","unstructured":"G. Birkhoff,Lattice Theory, American Mathematical Society Colloquium Publications, vol. 25, AMS, Providence, RI, 1979."},{"key":"BF01840401_CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, and L. J. Guibas, The Complexity of Cutting Convex Polytopes,Proceedings of the 19th ACM Symposium on Theory of Computing, pp. 66\u201376, 1987.","DOI":"10.1145\/28395.28403"},{"issue":"no. 1","key":"BF01840401_CR4","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa, A Linear Algorithm for Embedding Planar Graphs Using PQ-Trees,Journal of Computer and System Sciences, vol. 30, no. 1, pp. 54\u201376, 1985.","journal-title":"Journal of Computer and System Sciences"},{"issue":"no. 3","key":"BF01840401_CR5","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G. Battista Di","year":"1988","unstructured":"G. Di Battista and R. Tamassia, Algorithms for Plane Representations of Acyclic Digraphs,Theoretical Computer Science, vol. 61, no. 3, pp. 175\u2013198, 1988.","journal-title":"Theoretical Computer Science"},{"issue":"no. 2","key":"BF01840401_CR6","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal Point Location in a Monotone Subdivision,SIAM Journal on Computing, vol. 15, no. 2, pp. 317\u2013340, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"BF01840401_CR7","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S. Even,Graph Algorithms, Computer Science Press, Potomac, MD, 1979."},{"issue":"no. 4","key":"BF01840401_CR8","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"G. N. Frederickson","year":"1985","unstructured":"G. N. Frederickson, Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications,SIAM Journal on Computing, vol. 14, no. 4, pp. 781\u2013798, 1985.","journal-title":"SIAM Journal on Computing"},{"key":"BF01840401_CR9","first-page":"61","volume-title":"Advances in Computing Research, vol. 1","author":"L. J. Guibas","year":"1983","unstructured":"L. J. Guibas and F. F. Yao, On Translating a Set of Rectangles, inAdvances in Computing Research, vol. 1, F. P. Preparata (ed.), JAI Press, Greenwich, CT, pp. 61\u201377, 1983."},{"key":"BF01840401_CR10","unstructured":"M. Y. Hsueh and D. O. Pederson, Computer-Aided Layout of LSI Circuit Building-Blocks,Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 474\u2013477, 1979."},{"key":"BF01840401_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(86)90098-8","volume":"48","author":"G. F. Italiano","year":"1986","unstructured":"G. F. Italiano, Amortized Efficiency of a Path Retrieval Data Structure,Theoretical Computer Science, vol. 48, pp. 273\u2013281, 1986.","journal-title":"Theoretical Computer Science"},{"issue":"no. 1","key":"BF01840401_CR12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(88)90136-6","volume":"28","author":"G. F. Italiano","year":"1988","unstructured":"G. F. Italiano, Finding Paths and Deleting Edges in Directed Acyclic Graphs,Information Processing Letters, vol. 28, no. 1, pp. 5\u201311, 1988.","journal-title":"Information Processing Letters"},{"issue":"no. 3","key":"BF01840401_CR13","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/31.1746","volume":"35","author":"R. Jayakumar","year":"1988","unstructured":"R. Jayakumar, K. Thulasiraman, and M. N. S. Swamy, Planar Embedding: Linear-Time Algorithms for Vertex Placement and Edge Ordering,IEEE Transactions on Circuits and Systems, vol. 35, no. 3, pp. 334\u2013344, 1988.","journal-title":"IEEE Transactions on Circuits and Systems"},{"issue":"no. 3","key":"BF01840401_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0020-0190(75)90019-8","volume":"3","author":"T. Kameda","year":"1975","unstructured":"T. Kameda, On the Vector Representation of the Reachability in Planar Directed Graphs,Information Processing Letters, vol. 3, no. 3, pp. 75\u201377, 1975.","journal-title":"Information Processing Letters"},{"key":"BF01840401_CR15","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0012-365X(87)90008-2","volume":"63","author":"D. Kelly","year":"1987","unstructured":"D. Kelly, Fundamentals of Planar Ordered Sets,Discrete Mathematics, vol. 63, pp. 197\u2013216, 1987.","journal-title":"Discrete Mathematics"},{"issue":"no. 3","key":"BF01840401_CR16","doi-asserted-by":"crossref","first-page":"636","DOI":"10.4153\/CJM-1975-074-0","volume":"27","author":"D. Kelly","year":"1975","unstructured":"D. Kelly and I. Rival, Planar Lattices,Canadian Journal of Mathematics, vol. 27, no. 3, pp. 636\u2013665, 1975.","journal-title":"Canadian Journal of Mathematics"},{"issue":"no. 3","key":"BF01840401_CR17","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0206043","volume":"6","author":"D. T. Lee","year":"1977","unstructured":"D. T. Lee and F. P. Preparata, Location of a Point in a Planar Subdivision and Its Applications,SIAM Journal on Computing, vol. 6, no. 3, pp. 594\u2013606, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"BF01840401_CR18","unstructured":"A. Lempel, S. Even, and I. Cederbaum, An Algorithm for Planarity Testing of Graphs,Proceedings of the International Symposium on the Theory of Graphs, Rome, pp. 215\u2013232, 1966."},{"key":"BF01840401_CR19","unstructured":"R. M. Otten and J. G. van Wijk, Graph Representations in Interactive Layout Design,Proceedings of the IEEE International Symposium on Circuits and Systems, New York, pp. 914\u2013918, 1978."},{"key":"BF01840401_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/3-540-10704-5_9","volume-title":"Graph Theory and Algorithms","author":"T. Ozawa","year":"1981","unstructured":"T. Ozawa and H. Takahashi, A Graph-Planarization Algorithm and Its Applications to Random Graphs, inGraph Theory and Algorithms, Lecture Notes in Computer Science, vol. 108, Springer-Verlag, Berlin, pp. 95\u2013107, 1981."},{"key":"BF01840401_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-19422-3_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. A. Poutre La","year":"1988","unstructured":"J. A. La Poutre and J. van Leeuwen, Maintenance of Transitive Closures and Transitive Reductions of Graphs, inGraph-Theoretic Concepts in Computer Science (Proc. Internat. Workshop WG '87, Kloster Banz, June 1987), H. Gottler and H. J. Schneider (eds.), Lecture Notes in Computer Science, vol. 314, Springer-Verlag, Berlin, pp. 106\u2013120, 1988."},{"key":"BF01840401_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry, Springer-Verlag, New York, 1985."},{"key":"BF01840401_CR23","unstructured":"F. P. Preparata and R. Tamassia, A Fully Dynamic Planar Point Location Technique, Technical Report ACT-84, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1987."},{"key":"BF01840401_CR24","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and R. Tamassia, Fully Dynamic Point Location in a Monotone Subdivision,SIAM Journal on Computing, 1989 (to appear).","DOI":"10.1137\/0218056"},{"key":"BF01840401_CR25","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF00714475","volume":"4","author":"I. Rival","year":"1988","unstructured":"I. Rival and J. Urrutia, Representing Orders by Translating Convex Figures in the Plane,Order, vol. 4, pp. 319\u2013339, 1988.","journal-title":"Order"},{"issue":"no. 4","key":"BF01840401_CR26","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"P. Rosenstiehl and R. E. Tarjan, Rectilinear Planar Layouts of Planar Graphs and Bipolar Orientations,Discrete & Computational Geometry, vol. 1, no. 4, pp. 342\u2013351, 1986.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01840401_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1007\/3-540-19488-6_143","volume-title":"Automata, Languages and Programming","author":"R. Tamassia","year":"1988","unstructured":"R. Tamassia, A Dynamic Data Structure for Planar Graph Embedding, inAutomata, Languages and Programming (Proc. 15th ICALP, Tampere, Finland, 1988), T. Lepisto and A. Salomaa (eds.), Lecture Notes in Computer Science, vol. 317, Springer-Verlag, Berlin, pp. 576\u2013590, 1988."},{"issue":"no. 4","key":"BF01840401_CR28","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 Representations of Planar Graphs,Discrete & Computational Geometry, vol. 1, no. 4, pp. 321\u2013341, 1986.","journal-title":"Discrete & Computational Geometry"},{"key":"BF01840401_CR29","unstructured":"R. Tamassia and I. G. Tollis, Efficient Embedding of Planar Graphs in Linear Time,Proceedings of the IEEE International Symposium on Circuits and Systems, Philadelphia, pp. 495\u2013498, 1987."},{"key":"BF01840401_CR30","volume-title":"CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial Applied Mathematics, Philadelphia, PA, 1983."},{"issue":"no. 3","key":"BF01840401_CR31","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1109\/31.1739","volume":"35","author":"S. Wimer","year":"1988","unstructured":"S. Wimer, I. Koren, and I. Cederbaum, Floorplans, Planar Graphs, and Layouts,IEEE Transactions on Circuits and Systems, vol. 35, no. 3, pp. 267\u2013278, 1988.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"BF01840401_CR32","doi-asserted-by":"crossref","unstructured":"S. Wismath, Characterizing Bar Line-of-Sight Graphs,Proceedings of the ACM Symposium on Computational Geometry, Baltimore, MD, pp. 147\u2013152, 1985.","DOI":"10.1145\/323233.323253"},{"key":"BF01840401_CR33","unstructured":"D. Woods, Drawing Planar Graphs, Ph.D. dissertation (Technical Report STAN-CS-82-943), Computer Science Department, Stanford University, 1982."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840401.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840401\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840401","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T21:38:47Z","timestamp":1586295527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":33,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["BF01840401"],"URL":"https:\/\/doi.org\/10.1007\/bf01840401","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}