https://scholars.lib.ntu.edu.tw/handle/123456789/296679
標題: | Some applications of orderly spanning trees in graph drawing | 作者: | CHEN HO-LIN Liao, C.-C. HSUEH-I LU HSU-CHUN YEN |
公開日期: | 2002 | 卷: | 2528 LNCS | 起(迄)頁: | 332-343 | 來源出版物: | Lecture Notes in Computer Science | 摘要: | Orderly spanning trees seem to have the potential of becoming a new and promising technique capable of unifying known results as well as deriving new results in graph drawing. Our exploration in this paper provides new evidence to demonstrate such a potential. Two applications of the orderly spanning trees of plane graphs are investigated. Our first application deals with Podevs drawing, i.e., planar orthogonal drawing with equal vertex size, introduced by Fößmeier and Kaufmann. Based upon orderly spanning trees, we give an algorithm that produces a Podevs drawing with half-perimeter no more than ⌈3n/2⌉ + 1 and at most one bend per edge for any n-node plane graph with maximal degree Δ, a notable improvement over the existing results in the literature in terms of the size of the drawing area. The second application is an alternative proof for the sufficient and necessary condition for a graph to admit a rectangular dual, i.e., a floor-plan using only rectangles. © Springer-Verlag Berlin Heidelberg 2002. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-84867451049&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/296679 https://www.scopus.com/inward/record.uri?eid=2-s2.0-84867451049&doi=10.1007%2f3-540-36151-0_31&partnerID=40&md5=bd0c999554c0053b32649447a30a8736 |
ISSN: | 03029743 | SDG/關鍵字: | Drawing (graphics); Floorplans; Graph drawing; Maximal degree; New results; Orthogonal drawings; Plane graphs; Spanning tree; Sufficient and necessary condition; Trees (mathematics) |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。