Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420598 | Discrete Applied Mathematics | 2008 | 13 Pages |
Abstract
In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints, and call a drawing in which every inner-facial cycle is drawn as a convex polygon an inner-convex drawing. It is proved that every triconnected plane graph with the boundary fixed with a star-shaped polygon whose kernel has a positive area admits an inner-convex drawing. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits an inner-convex drawing. We present linear time algorithms to construct inner-convex drawings for both cases.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Seok-Hee Hong, Hiroshi Nagamochi,