Star-Shaped Drawings of Graphs with Fized Embedding and Concave Corner Constraints
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 Thomassens classical characterization of biconnected plane graphs with a prescribed boundary that have convex drawings.
Seok-Hee Hong Hiroshi Nagamochi
School of Information Technologies, University of Sydney Department of Applied Mathematics and Physics, Kyoto University
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
405-414
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）