2009年
Upward Star-Shaped Polyhedral Graphs
ALGORITHMS AND COMPUTATION, PROCEEDINGS
- ,
- 巻
- 5878
- 号
- 開始ページ
- 913
- 終了ページ
- +
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
We introduce a new wider class of polyhedra, called upward (star-shaped) polyhedra, and present a graph-theoretic characterization. Our proof includes a drawing algorithm which constructs an upward polyhedron with n vertices in O(n(1.5)) time. Moreover, we can test whether a given plane graph is an upward polyhedral graph hi linear time. Our result is the first graph-theoretic characterization of non-convex polyhedra, which solves an open problem posed by Grunbaum [6], and a generalization of the Steinitz' theorem [9].
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- Web of Science ID : WOS:000280382600090