Width-optimal visibility representations of plane graphs

Jia Hao Fan*, Chun-Cheng Lin, Hsueh I. Lu, Hsu Chun Yen

*此作品的通信作者

研究成果: Conference contribution同行評審

13 引文 斯高帕斯(Scopus)

摘要

Given an n-node plane graph G, the visibility representation of G is concerned with drawing each node of G using a horizontal line segment such that the line segments associated with any two adjacent nodes of G are vertically visible to each other. Finding most compact visibility representations of plane graphs is not only of theoretical importance but also of practical interest, and has received much attention in the community of algorithmic graph theory. In this paper, we give a linear-time algorithm to find a visibility representation of G no wider than [4n/3] - 2. Our result improves upon the previously known upper bound 4n/3 + 2[√n], providing a positive answer to a conjecture suggested in the literature about whether an upper bound 4n/3 + O(1) on the required width can be achieved for an arbitrary plane graph. In fact, our visibility representation achieves optimality in the upper bound of width because the bound differs from the previously known lower bound [4n/3] - 3 only by one unit.

原文English
主出版物標題Algorithms and Computation - 18th International Symposium, ISAAC 2007, Proceedings
頁面160-171
頁數12
DOIs
出版狀態Published - 12月 2007
事件18th International Symposium on Algorithms and Computation, ISAAC 2007 - Sendai, Japan
持續時間: 17 12月 200719 12月 2007

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
4835 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference18th International Symposium on Algorithms and Computation, ISAAC 2007
國家/地區Japan
城市Sendai
期間17/12/0719/12/07

指紋

深入研究「Width-optimal visibility representations of plane graphs」主題。共同形成了獨特的指紋。

引用此