{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:01Z","timestamp":1759063801971},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540557067"},{"type":"electronic","value":"9783540472759"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55706-7_22","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:32:32Z","timestamp":1330252352000},"page":"258-271","source":"Crossref","is-referenced-by-count":6,"title":["Triangulating planar graphs while minimizing the maximum degree"],"prefix":"10.1007","author":[{"given":"Goos","family":"Kant","sequence":"first","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., and G.S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity testing using PQ-tree algorithms, J. of Computer and System Sciences 13 (1976), pp. 335\u2013379.","journal-title":"J. of Computer and System Sciences"},{"key":"22_CR2","first-page":"153","volume-title":"Progress in Graph Theory","author":"N. Chiba","year":"1984","unstructured":"Chiba, N., T. Yamanouchi and Nishizeki, Linear algorithms for convex drawings of planar graphs, In: J.A. Bondy and U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, Toronto, 1984, pp. 153\u2013173."},{"key":"22_CR3","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":"22_CR4","doi-asserted-by":"crossref","unstructured":"Frank, A., Augmenting graphs to meet edge-connectivity requirements, Proc. 31th Annual IEEE Symp. on Found. on Comp. Science, St. Louis, 1990, pp. 708\u2013718.","DOI":"10.1109\/FSCS.1990.89593"},{"key":"22_CR5","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"Fraysseix, H. de, J. Pach and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), pp. 41\u201351.","journal-title":"Combinatorica"},{"key":"22_CR6","first-page":"75","volume":"13","author":"H. Fraysseix de","year":"1982","unstructured":"Fraysseix, H. de, and P. Rosenstiehl, A depth first characterization of planarity, Annals of Discrete Math. 13 (1982), pp. 75\u201380.","journal-title":"Annals of Discrete Math."},{"key":"22_CR7","unstructured":"Haandel, F. van, Straight Line Embeddings on the Grid, Dept. of Comp. Science, Report no. INF\/SCR-91-19, Utrecht University, 1991."},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., and R.E. Tarjan, Efficient planarity testing, J. ACM 21 (1974), pp. 549\u2013568.","journal-title":"J. ACM"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Hsu, T., and V. Ramachandran, A linear time algorithm for triconnectivity augmentation, in: Proc. 32th Annnual IEEE Symp. on Found. on Comp. Science, Porto Rico, 1991.","DOI":"10.1109\/SFCS.1991.185418"},{"key":"22_CR10","volume-title":"Tech. Rep. TR-91-12","author":"T. Hsu","year":"1991","unstructured":"Hsu, T., and V. Ramachandran, On Finding a Smallest Augmentation to Biconnect a Graph, Computer Science Dept., University of Texas at Austin, Texas, Tech. Rep. TR-91-12, 1991."},{"key":"22_CR11","unstructured":"Kant, G., Optimal Linear Planar Augmentation Algorithms for Outerplanar Graphs, Techn. Rep. RUU-CS-91-47, Dept. of Computer Science, Utrecht University, 1991."},{"key":"22_CR12","unstructured":"Kant, G., A Linear Implementation of De Fraysseix' Grid Drawing Algorithm, Manuscript, Dept. of Comp. Science, Utrecht University, 1988."},{"key":"22_CR13","first-page":"286","volume-title":"Lecture Notes in Comp. Science 519","author":"G. Kant","year":"1991","unstructured":"Kant, G., and H.L. Bodlaender, Planar graph augmentation problems, Extended Abstract in: F. Dehne, J.-R. Sack and N. Santoro (Eds.), Proc. 2nd Workshop on Data Structures and Algorithms, Lecture Notes in Comp. Science 519, Springer-Verlag, Berlin\/Heidelberg, 1991, pp. 286\u2013298."},{"key":"22_CR14","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":"22_CR15","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 augmentations to biconnect a graph, SIAM J. Comput. 6 (1977), pp. 55\u201366.","journal-title":"SIAM J. Comput."},{"key":"22_CR16","unstructured":"Schnyder, W., Embedding planar graphs on the grid, in: Proc. 1st Annual ACM-SIAM Symp. on Discr. Alg., San Francisco, 1990, pp. 138\u2013147."},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1112\/plms\/s3-10.1.304","volume":"10","author":"W.T. Tutte","year":"1960","unstructured":"Tutte, W.T., Convex representations of graphs, Proc. London Math. Soc., vol. 10 (1960), pp. 304\u2013320.","journal-title":"Proc. London Math. Soc."},{"key":"22_CR18","series-title":"Tech. Rep. STAN-CS-82-943","volume-title":"Ph.D. Dissertation","author":"D. Woods","year":"1982","unstructured":"Woods, D., Drawing Planar Graphs, Ph.D. Dissertation, Computer Science Dept., Stanford University, CA, Tech. Rep. STAN-CS-82-943, 1982."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '92"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55706-7_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:34:40Z","timestamp":1619573680000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55706-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557067","9783540472759"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-55706-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}