論文

査読有り
2008年

Star-shaped drawings of graphs with fixed embedding and concave corner constraints

COMPUTING AND COMBINATORICS, PROCEEDINGS
  • Seok-Hee Hong
  • ,
  • Hiroshi Nagamochi

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.

リンク情報
DOI
https://doi.org/10.1007/978-3-540-69733-6_40
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902261008141460
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000257186200040&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/978-3-540-69733-6_40
  • ISSN : 0302-9743
  • J-Global ID : 200902261008141460
  • Web of Science ID : WOS:000257186200040

エクスポート
BibTeX RIS