{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:14:45Z","timestamp":1760440485443},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p>A drawing of a plane graph is called an inner rectangular drawing if every edge is drawn as a horizontal or vertical line segment so that every inner face is a rectangle. In this paper we show that a plane graph G has an inner rectangular drawing D if and only if a new bipartite graph constructed from G has a perfect matching. We also show that D can be found in time O(n<jats:sup>1.5<\/jats:sup>\/ log n) if G has n vertices and a sketch of the outer face is prescribed, that is, all the convex outer vertices and concave ones are prescribed.<\/jats:p>","DOI":"10.1142\/s0218195906002026","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T12:53:13Z","timestamp":1146142393000},"page":"249-270","source":"Crossref","is-referenced-by-count":17,"title":["INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS"],"prefix":"10.1142","volume":"16","author":[{"given":"KAZUYUKI","family":"MIURA","sequence":"first","affiliation":[{"name":"Faculty of Symbiotic Systems Science, Fukushima University, Fukushima 960-1296, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HIROKI","family":"HAGA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"TAKAO","family":"NISHIZEKI","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Sendai 980-8579, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762117"},{"key":"rf3","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"Di Battista G.","year":"1999"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"rf6","volume-title":"Facility Layout and Location","author":"Francis R. L.","year":"1974"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1137\/0222072"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(95)00257-X"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840399"},{"key":"rf15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer T.","year":"1990"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"rf19","volume-title":"Combinatorial Optinization","author":"Papadimitriou C. H.","year":"1982"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00061-X"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00003-0"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1142\/4109"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891831"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1137\/0216030"},{"key":"rf25","unstructured":"C.\u00a0Thomassen, Progress in Graph Theory, eds. J. A.\u00a0Bondy and U. S. R.\u00a0Murty (Academic Press Canada, Don Mills, Ontario, Canada, 1984)\u00a0pp. 43\u201369."},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-033-3"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1137\/0222035"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906002026","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T06:07:46Z","timestamp":1586844466000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906002026"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":20,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0218195906002026"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906002026","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}