{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T00:10:53Z","timestamp":1685146253147},"reference-count":7,"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":[[2009,9]]},"abstract":"<jats:p>Irreducible triangulations are plane graphs with a quadrangular exterior face, triangular interior faces and no separating triangles. Fusy proposed a straight-line grid drawing algorithm for irreducible triangulations, whose grid size is asymptotically with high probability 11n\/27 \u00d7 11n\/27 up to an additive error of [Formula: see text]. Later on, Fusy generalized the idea to quadrangulations and obtained a straight-line grid drawing, whose grid size is asymptotically with high probability 13n\/27 \u00d7 13n\/27 up to an additive error of [Formula: see text]. In this paper, we first prove that the above two straight-line grid drawing algorithms for irreducible triangulations and quadrangulations actually produce open rectangle-of-influence drawings for them respectively. Therefore, the above mentioned straight-line grid drawing size bounds also hold for the open rectangle-of-influence drawings. These results improve previous known drawing sizes.<\/jats:p><jats:p>In the second part of the paper, we present another application of the results obtained by Fusy. We present a linear time algorithm for constructing a rectangular dual for a randomly generated irreducible triangulation with n vertices, one of its dimensions equals [Formula: see text] asymptotically with high probability, up to an additive error of [Formula: see text]. In addition, we prove that the one dimension tight bound for a rectangular dual of any irreducible triangulations with n vertices is (n + 1)\/2.<\/jats:p>","DOI":"10.1142\/s1793830909000257","type":"journal-article","created":{"date-parts":[[2009,9,30]],"date-time":"2009-09-30T07:00:24Z","timestamp":1254294024000},"page":"319-333","source":"Crossref","is-referenced-by-count":6,"title":["ON OPEN RECTANGLE-OF-INFLUENCE AND RECTANGULAR DUAL DRAWINGS OF PLANE GRAPHS"],"prefix":"10.1142","volume":"01","author":[{"given":"HUAMING","family":"ZHANG","sequence":"first","affiliation":[{"name":"Computer Science Department, University of Alabama in Huntsville, 301 Sparkman Drive, Huntsville, Alabama, 35899, USA"}]},{"given":"MILIND","family":"VAIDYA","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Alabama in Huntsville, 301 Sparkman Drive, Huntsville, Alabama, 35899, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF00264230","volume":"22","author":"Chiba N.","journal-title":"Acta Inform."},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0222072"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(95)00257-X"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150202"},{"key":"rf9","first-page":"743","volume":"13","author":"Tutte W. T.","journal-title":"Proc. Lond. Math. Soc."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1154-y"},{"key":"rf11","author":"Zhang H.","journal-title":"Algorithmica"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T23:41:21Z","timestamp":1685144481000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":7,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1142\/S1793830909000257"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000257","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]}}}