{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:19Z","timestamp":1725551119443},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_3","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T17:12:04Z","timestamp":1269882724000},"page":"14-25","source":"Crossref","is-referenced-by-count":3,"title":["Improved Compact Visibility Representation of Planar Graph via Schnyder\u2019s Realizer"],"prefix":"10.1007","author":[{"given":"Lin","family":"Ching-Chi","sequence":"first","affiliation":[]},{"given":"Lu","family":"Hsueh","sequence":"additional","affiliation":[]},{"given":"Sun I.","family":"Fan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"N. Bonichon, C. Gavoille, and N. Hanusse. An information-theoretic upper bound of planar graphs using triangulation. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, 2003. To appear.","DOI":"10.1007\/3-540-36494-3_44"},{"key":"3_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1007\/3-540-45465-9_89","volume-title":"Wagner\u2019s theorem on realizers","author":"N. Bonichon","year":"2002","unstructured":"N. Bonichon, B. L. Sa\u00ebc, and M. Mosbah. Wagner\u2019s theorem on realizers. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, LNCS 2380, pages 1043\u20131053, M\u00e1laga, Spain, 2002."},{"key":"3_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-36151-0_31","volume-title":"Some applications of orderly spanning tree in graph drawing","author":"H.-L. Chen","year":"2002","unstructured":"H.-L. Chen, C.-C. Liao, H.-I. Lu, and H.-C. Yen. Some applications of orderly spanning tree in graph drawing. In Proceedings of the 10th International Symposium on Graph Drawing, LNCS 2528, pages 332\u2013343, Irvine, California, 2002."},{"key":"3_CR4","unstructured":"Y.-T. Chiang, C.-C. Lin, and H.-I. Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 506\u2013515, Washington, D. C., USA, 7\u20139 Jan. 2001."},{"issue":"3","key":"3_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1142\/S0218195997000144","volume":"7","author":"M. Chrobak","year":"1997","unstructured":"M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. International Journal of Computational Geometry & Applications, 7(3):211\u2013223, 1997.","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1017\/S0963548300001139","volume":"3","author":"H. Fraysseix de","year":"1994","unstructured":"H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl. On triangle contact graphs. Combinatorics, Probability and Computing, 3:233\u2013246, 1994.","journal-title":"Combinatorics, Probability and Computing"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41\u201351, 1990.","journal-title":"Combinatorica"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(92)90072-4","volume":"41","author":"G. Battista Di","year":"1992","unstructured":"G. Di Battista, R. Tamassia, and I. G. Tollis. Constrained visibility representations of graphs. Information Processing Letters, 41:1\u20137, 1992.","journal-title":"Information Processing Letters"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:436\u2013441, 1976.","journal-title":"Theoretical Computer Science"},{"key":"3_CR10","series-title":"Lect Notes Comput Sci","first-page":"155","volume-title":"2-visibility drawings of planar graphs","author":"U. F\u00f6\u00dfmeier","year":"1996","unstructured":"U. F\u00f6\u00dfmeier, G. Kant, and M. Kaufmann. 2-visibility drawings of planar graphs. In S. North, editor, Proceedings of the 4th International Symposium on Graph Drawing, LNCS 1190, pages 155\u2013168, California, USA, 1996."},{"issue":"6","key":"3_CR11","doi-asserted-by":"publisher","first-page":"2150","DOI":"10.1137\/S0097539796308874","volume":"28","author":"X. He","year":"1999","unstructured":"X. He. On floor-plan of plane graphs. SIAM Journal on Computing, 28(6):2150\u20132167, 1999.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"3_CR12","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1006\/jagm.2001.1161","volume":"40","author":"X. He","year":"2001","unstructured":"X. He. A simple linear time algorithm for proper box rectangular drawings of plane graphs. Journal of Algorithms, 40(1):82\u2013101, 2001.","journal-title":"Journal of Algorithms"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"A. Kanevsky, R. Tamassia, G. Di Battista, and J. Chen. On-line maintenance of the four-connected components of a graph. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 793\u2013801, San Juan, Puerto Rico, 1991. IEEE.","DOI":"10.1109\/SFCS.1991.185451"},{"key":"3_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/3-540-57899-4_70","volume-title":"A more compact visibility representation","author":"G. Kant","year":"1994","unstructured":"G. Kant. A more compact visibility representation. In Proceedings of the 19th Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 790, pages 411\u2013424, Utrecht, Netherlands, 1994."},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G. Kant","year":"1996","unstructured":"G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4\u201332, 1996.","journal-title":"Algorithmica"},{"issue":"3","key":"3_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1142\/S0218195997000132","volume":"7","author":"G. Kant","year":"1997","unstructured":"G. Kant. A more compact visibility representation. International Journal of Computational Geometry & Applications, 7(3):197\u2013210, 1997.","journal-title":"International Journal of Computational Geometry & Applications"},{"key":"3_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/3-540-57899-4_69","volume-title":"Two algorithms for finding rectangular duals of planar graphs","author":"G. Kant","year":"1994","unstructured":"G. Kant and X. He. Two algorithms for finding rectangular duals of planar graphs. In Proceedings of the 19th Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 790, pages 396\u2013410, Utrecht, Netherlands, 1994."},{"issue":"1\u20132","key":"3_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G. Kant","year":"1997","unstructured":"G. Kant and X. He. Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172(1\u20132):175\u2013193, 1997.","journal-title":"Theoretical Computer Science"},{"key":"3_CR19","series-title":"Lect Notes Comput Sci","first-page":"367","volume-title":"Floor-planning via orderly spanning trees","author":"C.-C. Liao","year":"2001","unstructured":"C.-C. Liao, H.-I. Lu, and H.-C. Yen. Floor-planning via orderly spanning trees. In Proceedings of the 9th International Symposium on Graph Drawing, LNCS 2265, pages 367\u2013377, Vienna, Austria, 2001."},{"key":"3_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/3-540-45655-4_8","volume-title":"Improved compact routing tables for planar networks via orderly spanning trees","author":"H.-I. Lu","year":"2002","unstructured":"H.-I. Lu. Improved compact routing tables for planar networks via orderly spanning trees. In O. H. Ibarra and L. Zhang, editors, Proceedings of the 8th International Conference on Computing and Combinatorics, LNCS 2387, pages 57\u201366, Singapore, August 15\u201317 2002."},{"issue":"3","key":"3_CR21","first-page":"384","volume":"E83-D","author":"C.-i. Nakano","year":"2000","unstructured":"C.-i. Nakano. Planar drawings of plane graphs. IEICE Transactions on Information and Systems, E83-D(3):384\u2013391, Mar. 2000.","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"2","key":"3_CR22","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0304-3975(92)90349-K","volume":"99","author":"J. Nummenmaa","year":"1992","unstructured":"J. Nummenmaa. Constructing compact rectilinear planar layouts using canonical representation of planar graphs. Theoretical Computer Science, 99(2):213\u2013230, 1992.","journal-title":"Theoretical Computer Science"},{"key":"3_CR23","unstructured":"R. Otten and J. van Wijk. Graph representations in interactive layout design. In Proceedings of the IEEE International Symposium on Circuits and Systems, pages 914\u2013918, 1978."},{"issue":"4","key":"3_CR24","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"P. Rosenstiehl and R. E. Tarjan. Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete & Computational Geometry, 1(4):343\u2013353, 1986.","journal-title":"Discrete & Computational Geometry"},{"key":"3_CR25","first-page":"259","volume-title":"Advances in Computing Research","author":"M. Schlag","year":"1985","unstructured":"M. Schlag, F. Luccio, P. Maestrini, D. T. Lee, and C. K. Wong. A visibility problem in VLSI layout compaction. In F. P. Preparata, editor, Advances in Computing Research, volume 2, pages 259\u2013282. JAI Press Inc. Greenwich, CT, 1985."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"W. Schnyder. Planar graphs and poset dimension. Order, 5:323\u2013343, 1989.","journal-title":"Order"},{"key":"3_CR27","unstructured":"W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 138\u2013148, 1990."},{"issue":"4","key":"3_CR28","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02187705","volume":"1","author":"R. Tamassia","year":"1986","unstructured":"R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete & Computational Geometry, 1(4):321\u2013341, 1986.","journal-title":"Discrete & Computational Geometry"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1109\/31.34669","volume":"36","author":"R. Tamassia","year":"1989","unstructured":"R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Transactions in Circuits and Systems, 36:1230\u20131234, 1989.","journal-title":"IEEE Transactions in Circuits and Systems"},{"key":"3_CR30","first-page":"26","volume":"46","author":"K. Wagner","year":"1936","unstructured":"K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresber Deutsche Math.-Verein, 46:26\u201332, 1936.","journal-title":"Jahresber Deutsche Math.-Verein"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T03:59:58Z","timestamp":1550980798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}