{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T20:08:13Z","timestamp":1709669293802},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,2]]},"abstract":"<jats:p>A canonical decomposition, a realizer, a Schnyder labeling and an orderly spanning tree of a plane graph play an important role in straight-line grid drawings, convex grid drawings, floor-plannings, graph encoding, etc. It is known that the triconnectivity is a sufficient condition for their existence, but no necessary and sufficient condition has been known. In this paper, we present a necessary and sufficient condition for their existence, and show that a canonical decomposition, a realizer, a Schnyder labeling, an orderly spanning tree, and an outer triangular convex grid drawing are notions equivalent with each other. We also show that they can be found in linear time whenever a plane graph satisfies the condition.<\/jats:p>","DOI":"10.1142\/s0129054105002905","type":"journal-article","created":{"date-parts":[[2005,3,14]],"date-time":"2005-03-14T08:00:11Z","timestamp":1110787211000},"page":"117-141","source":"Crossref","is-referenced-by-count":21,"title":["CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS"],"prefix":"10.1142","volume":"16","author":[{"given":"KAZUYUKI","family":"MIURA","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai 980-8579, Japan"}]},{"given":"MACHIKO","family":"AZUMA","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai 980-8579, Japan"}]},{"given":"TAKAO","family":"NISHIZEKI","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aoba-yama 05, Sendai 980-8579, Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"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","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000144"},{"key":"rf6","first-page":"29","volume":"10","author":"Chrobak M.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00020-D"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"rf9","volume-title":"Graph Drawing","author":"Di Battista G.","year":"1999"},{"key":"rf10","first-page":"302","volume":"4","author":"Di Battista G.","journal-title":"Algorithmica"},{"key":"rf11","first-page":"229","volume":"11","author":"F\u00e1ry I.","journal-title":"Acta Sci. Math. Szeged"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010604726900"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009290"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02086606"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(95)00257-X"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00057-9"},{"key":"rf21","volume-title":"Planar Graphs: Theory and Algorithms","author":"Nishizeki T.","year":"1988"},{"key":"rf23","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":"rf24","first-page":"743","volume":"13","author":"Tutte W. T.","journal-title":"Proc. London Math. Soc."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105002905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T16:51:27Z","timestamp":1683046287000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105002905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,2]]},"references-count":18,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,2]]}},"alternative-id":["10.1142\/S0129054105002905"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105002905","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,2]]}}}