{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,29]],"date-time":"2024-06-29T06:34:00Z","timestamp":1719642840691},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,2,5]],"date-time":"2009-02-05T00:00:00Z","timestamp":1233792000000},"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":[[2010,10]]},"DOI":"10.1007\/s00453-008-9275-y","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T18:46:02Z","timestamp":1233773162000},"page":"433-460","source":"Crossref","is-referenced-by-count":5,"title":["A Linear-Time Algorithm for Symmetric Convex Drawings of Internally Triconnected Plane Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Seok-Hee","family":"Hong","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,2,5]]},"reference":[{"key":"9275_CR1","series-title":"Lecture Notes in Computer Science","first-page":"86","volume-title":"Graph Drawing (Proc. of GD 2002)","author":"D. Abelson","year":"2003","unstructured":"Abelson, D., Hong, S., Taylor, D.E.: A Group-theoretic method for drawing graphs symmetrically. In: Graph Drawing (Proc. of GD 2002). Lecture Notes in Computer Science, vol. 2265, pp. 86\u201397. Springer, Berlin (2003)"},{"key":"9275_CR2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"9275_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J.A. Bondy","year":"1976","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. North Holland, Amsterdam (1976)"},{"key":"9275_CR4","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":"Graph Drawing (Proc. of GD 2004)","author":"N. Bonichon","year":"2005","unstructured":"Bonichon, N., Felsner, S., Mosbah, M.: Convex drawings of 3-connected plane graphs. In: Graph Drawing (Proc. of GD 2004). Lecture Notes in Computer Science, vol. 3383, pp. 60\u201370. Springer, Berlin (2005)"},{"key":"9275_CR5","series-title":"Lecture Notes in Computer Science","first-page":"178","volume-title":"Graph Drawing (Proc. of GD 2001)","author":"C. Buchheim","year":"2001","unstructured":"Buchheim, C., Junger, M.: Detecting symmetries by branch and cut. In: Graph Drawing (Proc. of GD 2001). Lecture Notes in Computer Science, pp.\u00a0178\u2013188. Springer, Berlin (2001)"},{"key":"9275_CR6","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":"9275_CR7","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":"9275_CR8","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1145\/237218.237401","volume-title":"Proc. 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: Proc. of the 12th Annual Symposium on Computational Geometry (SoCG 1996), pp. 319\u2013328. ACM, New York (1996)"},{"key":"9275_CR9","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1016\/S0022-0000(73)80029-7","volume":"7","author":"S.A. Cook","year":"1976","unstructured":"Cook, S.A., Reckhow, R.A.: Time bounded random access machines. J. Comput. Syst. Sci. 7, 354\u2013375 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"9275_CR10","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G. Di Battista","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)"},{"key":"9275_CR11","series-title":"Lecture Notes in Computer Science","first-page":"276","volume-title":"Graph Drawing (Proc. of GD 1999)","author":"H. Fraysseix de","year":"2000","unstructured":"de Fraysseix, H.: An heuristic for graph symmetry detection. In: Graph Drawing (Proc. of GD 1999). Lecture Notes in Computer Science, vol. 1731, pp. 276\u2013285. Springer, Berlin (2000)"},{"issue":"2","key":"9275_CR12","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/S0304-3975(99)00239-X","volume":"240","author":"P. Eades","year":"2000","unstructured":"Eades, P., Lin, X.: Spring algorithms and symmetry. Theor. Comput. Sci. 240(2), 379\u2013405 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9275_CR13","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":"9275_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/978-3-540-24587-2_42","volume-title":"Algorithms and Computation (Proc. of ISAAC 2003)","author":"S. Hong","year":"2003","unstructured":"Hong, S., Eades, P.: Symmetric layout of disconnected graphs. In: Algorithms and Computation (Proc. of ISAAC 2003). Lecture Notes in Computer Science, vol. 2906, pp. 405\u2013414. Springer, Berlin (2003)"},{"issue":"2","key":"9275_CR15","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00453-004-1132-z","volume":"42","author":"S. Hong","year":"2005","unstructured":"Hong, S., Eades, P.: Drawing planar graphs symmetrically II: biconnected planar graphs. Algorithmica 42(2), 159\u2013197 (2005)","journal-title":"Algorithmica"},{"issue":"1","key":"9275_CR16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s00453-005-1149-y","volume":"44","author":"S. Hong","year":"2006","unstructured":"Hong, S., Eades, P.: Drawing planar graphs symmetrically III: oneconnected planar graphs. Algorithmica 44(1), 67\u2013100 (2006)","journal-title":"Algorithmica"},{"key":"9275_CR17","unstructured":"Hong, S., Nagamochi, H.: Convex drawings of hierarchical plane graphs. In: Proc. of the 17th Australasian Workshop on Combinatorial Algorithms (AWOCA 2006), Uluru, NT, 13\u201316 July 2006"},{"key":"9275_CR18","doi-asserted-by":"crossref","first-page":"2368","DOI":"10.1016\/j.dam.2007.10.012","volume":"156","author":"S. Hong","year":"2008","unstructured":"Hong, S., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Appl. Math. 156, 2368\u20132380 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"3\u20134","key":"9275_CR19","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0925-7721(00)00020-1","volume":"17","author":"S. Hong","year":"2000","unstructured":"Hong, S., Eades, P., Lee, S.: Drawing series parallel digraphs symmetrically. Comput. Geom. Theory Appl. 17(3\u20134), 165\u2013188 (2000)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9275_CR20","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s00454-006-1231-5","volume":"36","author":"S. Hong","year":"2006","unstructured":"Hong, S., McKay, B., Eades, P.: A linear time algorithm for constructing maximally symmetric straight line drawings of triconnected planar graphs. Discrete Comput. Geom. 36, 283\u2013311 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"9275_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/11940128_15","volume-title":"Proc. of ISAAC 2006","author":"A. Kamada","year":"2006","unstructured":"Kamada, A., Miura, K., Nishizeki, T.: Convex grid drawings of plane graphs with rectangular contours. In: Proc. of ISAAC 2006. Lecture Notes in Computer Science, pp.\u00a0131\u2013140. Springer, Berlin (2006)"},{"key":"9275_CR22","unstructured":"Lin, X.: Analysis of algorithms for drawing graphs. Ph.D. Thesis, University of Queensland (1992)"},{"key":"9275_CR23","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"9275_CR24","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/323233.323254","volume-title":"Proc. of Annual Symposium on Computational Geometry (SoCG)","author":"R.J. Lipton","year":"1985","unstructured":"Lipton, R.J., North, S.C., Sandberg, J.S.: A method for drawing graphs. In: Proc. of Annual Symposium on Computational Geometry (SoCG), pp.\u00a0153\u2013160. ACM, New York (1985)"},{"key":"9275_CR25","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0012-365X(94)00347-L","volume":"156","author":"V.A. Liskovets","year":"1996","unstructured":"Liskovets, V.A.: A reductive technique for enumerating non-isomorphic planar maps. Discrete Math. 156, 197\u2013217 (1996)","journal-title":"Discrete Math."},{"issue":"1","key":"9275_CR26","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1137\/0210002","volume":"10","author":"A. Lubiw","year":"1981","unstructured":"Lubiw, A.: Some NP-complete problems similar to graph isomorphism. SIAM J. Comput. 10(1), 11\u201321 (1981)","journal-title":"SIAM J. Comput."},{"key":"9275_CR27","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02075357","volume":"192","author":"P. Mani","year":"1971","unstructured":"Mani, P.: Automorphismen von Polyedrischen Graphen. Math. Ann. 192, 279\u2013303 (1971)","journal-title":"Math. Ann."},{"key":"9275_CR28","unstructured":"Manning, J.: Geometric symmetry in graphs. Ph.D. Thesis, Purdue Univ. (1990)"},{"key":"9275_CR29","first-page":"159","volume":"64","author":"J. Manning","year":"1988","unstructured":"Manning, J., Atallah, M.J.: Fast detection and display of symmetry in trees. Congressus Numerantium 64, 159\u2013169 (1988)","journal-title":"Congressus Numerantium"},{"key":"9275_CR30","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0166-218X(92)90112-N","volume":"39","author":"J. Manning","year":"1992","unstructured":"Manning, J., Atallah, M.J.: Fast detection and display of symmetry in quterplanar graphs. Discrete Appl. Math. 39, 13\u201335 (1992)","journal-title":"Discrete Appl. Math."},{"key":"9275_CR31","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."},{"issue":"5","key":"9275_CR32","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":"9275_CR33","series-title":"Lecture Notes in Computer Science","first-page":"248","volume-title":"Graph Drawing (Proc. of GD 1997)","author":"H. Purchase","year":"1998","unstructured":"Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: Graph Drawing (Proc. of GD 1997). Lecture Notes in Computer Science, vol.\u00a01353, pp.\u00a0248\u2013259. Springer, Berlin (1998)"},{"key":"9275_CR34","first-page":"728","volume-title":"Proc. of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)","author":"G. Rote","year":"2005","unstructured":"Rote, G.: Strictly convex drawings of planar graphs. In: Proc. of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp.\u00a0728\u2013734. SIAM, Philadelphia (2005)"},{"key":"9275_CR35","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1983","unstructured":"Tarjan, R.E.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)"},{"key":"9275_CR36","first-page":"43","volume-title":"Progress in Graph Theory","author":"C. Thomassen","year":"1984","unstructured":"Thomassen, C.: Plane representations of graphs. In: Bondy, J.A., Murty, U.S.R. (eds.) Progress in Graph Theory, pp.\u00a043\u201369. Academic Press, San Diego (1984)"},{"issue":"3","key":"9275_CR37","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":"9275_CR38","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"13","author":"W.T. Tutte","year":"1963","unstructured":"Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. 13, 743\u2013768 (1963)","journal-title":"Proc. Lond. Math. Soc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9275-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9275-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9275-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T21:38:54Z","timestamp":1684877934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9275-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9275"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9275-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,5]]}}}