2008年
Star-shaped drawings of graphs with fixed embedding and concave corner constraints
COMPUTING AND COMBINATORICS, PROCEEDINGS
- ,
- 巻
- 5092
- 号
- 開始ページ
- 405
- 終了ページ
- +
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-540-69733-6_40
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, given a biconnected planar graph G with fixed plane embedding and a subset A of corners of G, we consider the problem of finding a star-shaped drawing D of G such that only corners in A are allowed to become concave corners in D. We first characterize a necessary and sufficient condition for a subset A of corners to admit such a star-shaped drawing D. Then we present a linear time algorithm for finding such a star-shaped drawing D. Our characterization includes Thomassen's classical characterization of biconnected plane graphs with a prescribed boundary that have convex drawings.
- リンク情報
- ID情報
-
- DOI : 10.1007/978-3-540-69733-6_40
- ISSN : 0302-9743
- J-Global ID : 200902261008141460
- Web of Science ID : WOS:000257186200040