Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00257
Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
Erin W. Chambers,
David Eppstein,
Michael T. Goodrich, and
Maarten Löffler
Vol. 16, no. 2, pp. 243-259, 2012. Regular paper.
Abstract We study the classic graph drawing problem of drawing a planar graph
using straight-line edges with a prescribed convex polygon
as the outer face. Unlike previous algorithms for this
problem, which may produce drawings with exponential area,
our method produces drawings with polynomial area.
In addition, we allow for collinear points on the boundary, provided
such vertices do not create overlapping edges.
Thus, we solve an open problem of Duncan et al., which,
when combined with their work, implies that we can produce
a planar straight-line drawing of a combinatorially-embedded genus-g graph
with the graph's canonical polygonal schema drawn as a convex polygonal
external face.
|
Submitted: July 2011.
Reviewed: October 2011.
Revised: January 2012.
Accepted: February 2012.
Final: February 2012.
Published: February 2012.
Communicated by
Seok-Hee Hong
|
Journal Supporters
|