网站地图 | 联系我们  
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
学术报告
现在位置:首页 > 学术报告

Non-Planar Square-Orthogonal Drawing with Few-Bend Edges
【2014.7.8 10:00am, N602】

【打印】【关闭】

 2014-7-4 

  Colloquia & Seminars 

  Speaker

Dr.Sheung-Hung POON,National Tsing Hua University

  Title

Non-Planar Square-Orthogonal Drawing with Few-Bend Edges

  Time

2014.7.8 10:00am                                         

  Venue

N602

  Abstract

We investigate square-orthogonal drawings of non-planar graphs with vertices represented as unit grid squares. We present quadratic-time algorithms to construct the square-orthogonal drawings of 5-graphs, 6-graphs, and 8-graphs such that each edge in the drawing contains at most two, two, and three bends, respectively. In particular, the novel analysis method we use to split a vertex so as to build some specific propagation channels in our algorithms is an interesting technique and may be of independent interest. Moreover, we show that the decision problem of determining whether an 8-graph has a square-orthogonal drawing without edge-bends is NP-complete.

  Affiliation

 

Sheung-Hung Poon received his Ph.D. degrees in Department of Computer Science from Hong Kong University of Science & Technology, Hong Kong, in 2004.He had been a postdoc researcher in Algorithm Group at Technical University of Eindhoven, The Netherlands, for two and a half years. Since 2007, he has been an assistant professor in Department of Computer Science at National Tsing Hua University, Taiwan. His research interests include computational geometry, graph drawing, geographic visualization, and graph algorithms.

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn