https://scholars.lib.ntu.edu.tw/handle/123456789/119268
標題: | Improved Compact Visibility Representation of Planar Graph via Schnyder’s Realizer | 作者: | Lin, C.-C. Lu, Hsueh-I Sun, I-F. |
關鍵字: | Canonical ordering; Graph drawing; Planar graph algorithm; Realizer; Visibility representation | 公開日期: | 三月-2004 | 卷: | 18 | 期: | 1 | 起(迄)頁: | 19-29 | 來源出版物: | SIAM Journal on Discrete Mathematics | 摘要: | Let G be an n-node planar graph. In a visibility representation of G, each node of G is represented by a horizontal line segment such that the line segments representing any two adjacent nodes of G are vertically visible to each other. In the present paper we give the best known compact visibility representation of G. Given a canonical ordering of the triangulated G, our algorithm draws the graph incrementally in a greedy manner. We show that one of three canonical orderings obtained from Schnyder's realizer for the triangulated G yields a visibility representation of G no wider than [22n-40/15]. Our easy-to-implement O(n)-time algorithm bypasses the complicated subroutines for four-connected components and four-block trees required by the best previously known algorithm of Kant. Our result provides a negative answer to Kant's open question about whether [3n-6/2] is a worst-case lower bound on the required width. Also, if G has no degree-three (respectively, degree-five) internal node, then our visibility representation for G is no wider than [4n-9/3] (respectively, [4n-7/3]). Moreover, if G is four-connected, then our visibility representation for G is no wider than n - 1, matching the best known result of Kant and He. As a by-product, we give a much simpler proof for a corollary of Wagner's theorem on realizers due to Bonichon, Le Saëc, and Mosbah. © 2004 Society for Industrial and Applied Mathematics. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-14644426536&doi=10.1137%2fS0895480103420744&partnerID=40&md5=f7b669b725f89d2bd6693f8cfab848e6 | DOI: | 10.1137/S0895480103420744 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。