{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T15:56:26Z","timestamp":1714751786735},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2011,4,29]],"date-time":"2011-04-29T00:00:00Z","timestamp":1304035200000},"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":[[2012,4]]},"DOI":"10.1007\/s00453-011-9513-6","type":"journal-article","created":{"date-parts":[[2011,4,28]],"date-time":"2011-04-28T15:27:39Z","timestamp":1304004459000},"page":"1122-1158","source":"Crossref","is-referenced-by-count":4,"title":["A Linear-Time Algorithm for Star-Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners"],"prefix":"10.1007","volume":"62","author":[{"given":"Seok-Hee","family":"Hong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,4,29]]},"reference":[{"key":"9513_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/978-3-540-31843-9_8","volume-title":"Proceedings of the 12th International Symposium on Graph Drawing (GD 2004)","author":"N. Bonichon","year":"2005","unstructured":"Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. In: Proceedings of the 12th International Symposium on Graph Drawing (GD 2004). Lecture Notes in Computer Science, vol. 3383, pp. 60\u201370. Springer, Berlin (2005)"},{"key":"9513_CR2","first-page":"153","volume-title":"Progress in Graph Theory","author":"N. Chiba","year":"1984","unstructured":"Chiba, N., Yamanouchi, T., Nishizeki, T.: Linear algorithms for convex drawings of planar graphs. In: Progress in Graph Theory, pp. 153\u2013173. Academic Press, San Diego (1984)"},{"key":"9513_CR3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/237218.237401","volume-title":"Proceedings of the 12th Annual Symposium on Computational Geometry (SoCG 1996)","author":"M. Chrobak","year":"1996","unstructured":"Chrobak, M., Goodrich, M.T., Tamassia, R.: Convex drawings of graphs in two and three dimensions. In: Proceedings of the 12th Annual Symposium on Computational Geometry (SoCG 1996), pp. 319\u2013328. ACM Press, New York (1996)"},{"key":"9513_CR4","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1142\/S0218195997000144","volume":"7","author":"M. Chrobak","year":"1997","unstructured":"Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. Int. J. Comput. Geom. Appl. 7, 211\u2013223 (1997)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9513_CR5","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G. Battista Di","year":"1999","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, New York (1999)"},{"issue":"5","key":"9513_CR6","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G. Battista Di","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25(5), 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"9513_CR7","first-page":"229","volume":"11","author":"I. F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representations of planar graphs. Acta Sci. Math. Szeged 11, 229\u2013233 (1948)","journal-title":"Acta Sci. Math. Szeged"},{"key":"9513_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-44541-2_8","volume-title":"Proceedings of the 8th International Symposium on Graph Drawing (GD 2000)","author":"C. Gutwenger","year":"2001","unstructured":"Gutwenger, C., Mutzel, P.: A linear time implementation of SPQR-trees. In: Proceedings of the 8th International Symposium on Graph Drawing (GD 2000). Lecture Notes in Computer Science, vol.\u00a01984, pp.\u00a077\u201390. Springer, Berlin (2001)"},{"key":"9513_CR9","doi-asserted-by":"crossref","first-page":"2368","DOI":"10.1016\/j.dam.2007.10.012","volume":"156","author":"S.-H. Hong","year":"2008","unstructured":"Hong, S.-H., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Appl. Math. 156, 2368\u20132380 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9513_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/978-3-540-69733-6_40","volume-title":"Proceedings of the 15th International Conference on Computing and Combinatorics (COCOON 2008)","author":"S.-H. Hong","year":"2008","unstructured":"Hong, S.-H., Nagamochi, H.: Star-shaped drawings of graphs with fixed embedding and concave corner constraints. In: Proceedings of the 15th International Conference on Computing and Combinatorics (COCOON 2008). Lecture Notes in Computer Science, vol. 5092, pp. 405\u2013414 (2008)"},{"issue":"3","key":"9513_CR11","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/j.jda.2009.05.003","volume":"8","author":"S.-H. Hong","year":"2010","unstructured":"Hong, S.-H., Nagamochi, H.: Convex drawings of hierarchical planar graphs and clustered planar graphs. J. Discrete Algorithms 8(3), 282\u2013295 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"9513_CR12","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.comgeo.2009.06.008","volume":"43","author":"S.-H. Hong","year":"2010","unstructured":"Hong, S.-H., Nagamochi, H.: An algorithm for constructing star-shaped drawings of plane graphs. Comput. Geom. Theory Appl. 43(2), 191\u2013206 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9513_CR13","unstructured":"Hong, S.-H., Nagamochi, H.: Star-shaped drawings of plane graphs with a cost function on concave corners (submitted)"},{"key":"9513_CR14","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Dividing a graph into triconnected components. SIAM J. Comput. 2, 135\u2013158 (1973)","journal-title":"SIAM J. Comput."},{"key":"9513_CR15","unstructured":"Kant, G.: Algorithms for drawing planar graphs. Ph.D. dissertation, Department of Computer Science, University of Utrecht, Holland (1993)"},{"key":"9513_CR16","series-title":"Lecture Notes in Computer Science Tutorial","volume-title":"Drawing Graphs: Methods and Models","year":"2001","unstructured":"Kaufmann, M., Wagner, D. (eds.): Drawing Graphs: Methods and Models. Lecture Notes in Computer Science Tutorial, vol.\u00a02025. Springer, Berlin (2001)"},{"issue":"5","key":"9513_CR17","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1142\/S012905410600425X","volume":"17","author":"K. Miura","year":"2006","unstructured":"Miura, K., Nakano, S., Nishizeki, T.: Convex grid drawings of four-connected plane graphs. Int. J. Found. Comput. Sci. 17(5), 1031\u20131060 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9513_CR18","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1142\/S0129054106004297","volume":"17","author":"K. Miura","year":"2006","unstructured":"Miura, K., Azuma, M., Nishizeki, T.: Convex drawings of plane graphs of minimum outer apices. Int. J. Found. Comput. Sci. 17, 1115\u20131128 (2006)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9513_CR19","doi-asserted-by":"crossref","DOI":"10.1142\/5648","volume-title":"Planar Graph Drawing","author":"T. Nishizeki","year":"2004","unstructured":"Nishizeki, T., Rahman, M.S.: Planar Graph Drawing. World Scientific, Singapore (2004)"},{"key":"9513_CR20","volume-title":"Graph Drawing and Applications","author":"K. Sugiyama","year":"2002","unstructured":"Sugiyama, K.: Graph Drawing and Applications. World Scientific, Singapore (2002)"},{"key":"9513_CR21","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1090\/S0002-9939-1951-0041425-5","volume":"2","author":"K.S. Stein","year":"1951","unstructured":"Stein, K.S.: Convex maps. Proc. Am. Math. Soc. 2, 464\u2013466 (1951)","journal-title":"Proc. Am. Math. Soc."},{"key":"9513_CR22","first-page":"43","volume-title":"Progress in Graph Theory","author":"C. Thomassen","year":"1984","unstructured":"Thomassen, C.: Plane representations of graphs. In: Progress in Graph Theory, pp. 43\u201369. Academic Press, San Diego (1984)"},{"issue":"3","key":"9513_CR23","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. Lond. Math. Soc., 10(3), 304\u2013320 (1960)","journal-title":"Proc. Lond. Math. Soc."},{"key":"9513_CR24","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"Wagner, K.: Bemerkungen zum Vierfarbenproblem. Jahresber. Dtsch. Math.-Ver., 46, 26\u201332 (1936)","journal-title":"Jahresber. Dtsch. Math.-Ver."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9513-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9513-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9513-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9513-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,29]]},"references-count":24,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9513"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9513-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,29]]}}}