TY - GEN
T1 - Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area
AU - Chambers, Erin W.
AU - Eppstein, David
AU - Goodrich, Michael T.
AU - Löffler, Maarten
PY - 2011
Y1 - 2011
N2 - 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 don't 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.
AB - 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 don't 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.
KW - CG, GRAPH, GD
U2 - 10.1007/978-3-642-18469-7_12
DO - 10.1007/978-3-642-18469-7_12
M3 - Conference contribution
T3 - LNCS 6502
SP - 129
EP - 140
BT - Proc. 18th Symposium on Graph Drawing
ER -