{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:16Z","timestamp":1725664096448},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:37:59Z","timestamp":1330270679000},"page":"83-94","source":"Crossref","is-referenced-by-count":3,"title":["On triangulating planar graphs under the four-connectivity constraint"],"prefix":"10.1007","author":[{"given":"Therese","family":"Biedl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Goos","family":"Kant","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kaufmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/net.3230170306","volume":"7","author":"J. Bhasker","year":"1987","unstructured":"Bhasker, J., and S. Sahni, A linear algorithm to check for the existence of a rectangular dual of a planar triangulated graph, Networks 7 (1987), pp. 307\u2013317.","journal-title":"Networks"},{"key":"8_CR2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1985), pp. 210\u2013223.","journal-title":"SIAM J. Comput."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(85)90004-2","volume":"30","author":"N. Chiba","year":"1985","unstructured":"Chiba, N., T. Nishizeki, S. Abe and T. Ozawa, A linear algorithm for embedding planar graphs using PQ-trees, J. of Computer and System Sciences 30 (1985), pp. 54\u201376.","journal-title":"J. of Computer and System Sciences"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Di Battista, G., and R. Tamassia, Incremental planarity testing, in: Proc. 30th Annual IEEE Symp. on Foundations of Comp. Science, 1989, pp. 436\u2013441.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Di Battista, G., Eades, P., and R. Tamassia, I.G. Tollis, Algorithms for Automatic Graph Drawing: An Annotated Bibliography, Brown Univ., Tech. Rep., 1993.","DOI":"10.1016\/0925-7721(94)00014-X"},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"K. P. Eswaran","year":"1976","unstructured":"Eswaran, K.P., and R.E. Tarjan, Augmentation problems, SIAM J. Comput. 5 (1976), pp. 653\u2013665.","journal-title":"SIAM J. Comput."},{"key":"8_CR7","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/TCT.1970.1083185","volume":"CT-17","author":"H. Frank","year":"1970","unstructured":"Frank, H. and W. Chou, Connectivity considerations in the design of survivable networks, IEEE Trans. on Circuit Theory, CT-17 (1970), pp. 486\u2013490.","journal-title":"IEEE Trans. on Circuit Theory"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"Garey, M.R., D.S. Johnson, The Rectilinear Steiner Tree Problem is NP-complete. SIAM J. Appl. Math. 32 (1977), pp. 826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"8_CR9","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"Garey, M.R., D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theoret. Comp. Science 1 (1976), pp. 237\u2013267.","journal-title":"Theoret. Comp. Science"},{"key":"8_CR10","unstructured":"Kant, G., The Planar Triconnectivity Augmentation Problem, submitted to Theoretical Computer Science, 1993."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Hsu, T.-S., On four-connecting a triconnected graph, in: Proc. 33st Annual IEEE Symp. on Found. of Comp. Science, 1992, pp. 70\u201379.","DOI":"10.1109\/SFCS.1992.267817"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Hsu, T.-S., and V. Ramachandran, A linear time algorithm for triconnectivity augmentation, Proc. 32th Annual IEEE Symp. on Found. of Comp. Sc., 1991, pp. 548\u2013559.","DOI":"10.1109\/SFCS.1991.185418"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Hsu, T.-S., and V. Ramachandran, On finding a smallest augmentation to biconnect a graph, in: W.L. Hsu and R.C.T. Lee (Eds.), Proc. of the Second Annual Int. Symp. on Algorithms, Lecture Notes in Comp. Science 557, Springer-Verlag, 1992, pp. 326\u2013335.","DOI":"10.1007\/3-540-54945-5_77"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Kanevsky, A., R. Tamassia, G. Di Battista and J. Chen, On-line maintenance of the four-connected components of a graph, In: Proc. 32th Annual IEEE Symp. on Foundations of Comp. Science, 1991, pp. 793\u2013801.","DOI":"10.1109\/SFCS.1991.185451"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Kant, G., A More Compact Visibility Representation, in: J. van Leeuwen (Ed.), Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Sc. (WG'93), LNCS, Springer 1994, to appear.","DOI":"10.1007\/3-540-57899-4_70"},{"key":"8_CR16","unstructured":"Kant, G., Algorithms for Drawing Planar Graphs, PhD thesis, Utrecht University, 1993."},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Kant, G., and X. He, Two Algorithms for Finding Rectangular Duals of Planar Graphs, in: J. van Leeuwen (Ed.), Proc. 19th Intern. Workshop on Graph-Theoretic Concepts in Comp. Sc. (WG'93), LNCS, Springer 1994, to appear.","DOI":"10.1007\/3-540-57899-4_69"},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/net.3230150202","volume":"5","author":"K. Ko\u017ami\u0144ski","year":"1985","unstructured":"Ko\u017ami\u0144ski, K., and E. Kinnen, Rectangular dual of planar graphs, Networks 5 (1985), pp. 145\u2013157.","journal-title":"Networks"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Lengauer, Th., Combinatorial Algorithms for Integrated Circuit Layout, Wiley, 1990.","DOI":"10.1007\/978-3-322-92106-2_3"},{"key":"8_CR20","unstructured":"Otten, R.H.J.M., and J.G. van Wijk, Graph representation in interactive layout design, in: Proc. IEEE Int. Symp. on Circuits and Systems, 1978, pp. 914\u2013918."},{"key":"8_CR21","first-page":"31","volume":"56","author":"R. C. Read","year":"1987","unstructured":"Read, R.C., A new method for drawing a graph given the cyclic order of the edges at each vertex, Congr. Numer. 56 (1987), pp. 31\u201344.","journal-title":"Congr. Numer."},{"key":"8_CR22","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1137\/0206003","volume":"6","author":"A. Rosenthal","year":"1977","unstructured":"Rosenthal, A., and A. Goldner, Smallest augmentation to biconnect a graph, SIAM J. Comput 6 (1977), pp. 55\u201366.","journal-title":"SIAM J. Comput"},{"key":"8_CR23","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., and R.E. Tarjan, Rectilinear planar layouts and bipolar orientations of planar graphs, Discr. and Comp. Geometry 1 (1986), pp. 343\u2013353.","journal-title":"Discr. and Comp. Geometry"},{"key":"8_CR24","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/TCT.1969.1083004","volume":"CT-16","author":"K. Steiglitz","year":"1969","unstructured":"Steiglitz, K., P. Weiner and D.J. Kleitman, The design of minimum-cost survivable networks, IEEE Trans. on Circuit Theory, CT-16 (1969), pp. 455\u2013560.","journal-title":"IEEE Trans. on Circuit Theory"},{"key":"8_CR25","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"Tamassia, R., and I.G. Tollis, A unified approach to visibility representations of planar graphs, Discr. and Comp. Geometry 1 (1986), pp. 321\u2013341.","journal-title":"Discr. and Comp. Geometry"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T06:34:39Z","timestamp":1640932479000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}