{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T10:10:15Z","timestamp":1711879815169},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>In a convex grid drawing of a plane graph, every edge is drawn as a straight-line segment without any edge-intersection, every vertex is located at a grid point, and every facial cycle is drawn as a convex polygon. A plane graph G has a convex drawing if and only if G is internally triconnected. It has been known that an internally triconnected plane graph G of n vertices has a convex grid drawing on a grid of O(n<jats:sup>3<\/jats:sup>) area if the triconnected component decomposition tree of G has at most four leaves. In this paper, we improve the area bound O(n<jats:sup>3<\/jats:sup>) to O(n<jats:sup>2<\/jats:sup>), which is optimal up to a constant factor. More precisely, we show that G has a convex grid drawing on a 2n \u00d7 4n grid. We also present an algorithm to find such a drawing in linear time.<\/jats:p>","DOI":"10.1142\/s179383091000070x","type":"journal-article","created":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T08:44:00Z","timestamp":1286873040000},"page":"347-362","source":"Crossref","is-referenced-by-count":6,"title":["CONVEX DRAWINGS OF INTERNALLY TRICONNECTED PLANE GRAPHS ON O(n<sup>2<\/sup>) GRIDS"],"prefix":"10.1142","volume":"02","author":[{"given":"XIAO","family":"ZHOU","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, Aobaku, Sendai 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TAKAO","family":"NISHIZEKI","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, Aobaku, Sendai 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-0177-6"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000144"},{"key":"rf3","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF00264230","volume":"22","author":"Chiba N.","journal-title":"Acta Inform."},{"key":"rf4","unstructured":"N.\u00a0Chiba, T.\u00a0Yamanouchi and T.\u00a0Nishizeki, Progress in Graph Theory, eds. J. A.\u00a0Bondy and U. S. R.\u00a0Murty (Academic Press, 1984)\u00a0pp. 153\u2013173."},{"key":"rf5","unstructured":"D.\u00a0Dolev, F. T.\u00a0Leighton and H.\u00a0Trickey, Advances in Computer Research, VLSI Theory\u00a02 (1984)\u00a0pp. 147\u2013161."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010604726900"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105002905"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004297"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00164"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/5648"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091000070X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,31]],"date-time":"2024-03-31T09:39:18Z","timestamp":1711877958000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091000070X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":12,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1142\/S179383091000070X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091000070x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}