Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area

Chambers, Erin and Eppstein, David and Goodrich, Michael T. and Löffler, Maarten (2011) Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010 , pp. 129-140(Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_12).

Full text not available from this repository.


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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-18469-7_12
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.070 Area / Edge Length
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1200

Actions (login required)

View Item View Item