On PointSets That Support Planar GraphsDujmović, Vida and Evans, William S. and Lazard, Sylvain and Lenhart, William J. and Liotta, Giuseppe and Rappaport, David and Wismath, Stephen (2012) On PointSets That Support Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 6474(Official URL: http://dx.doi.org/ 10.1007/9783642258787_7). Full text not available from this repository.
Official URL: http://dx.doi.org/ 10.1007/9783642258787_7
AbstractA universal pointset supports a crossingfree drawing of any planar graph. For a planar graph with n vertices, if bends on edges of the drawing are permitted, universal pointsets of size n are known, but only if the bendpoints are in arbitrary positions. If the locations of the bendpoints must also be specified as part of the pointset, we prove that any planar graph with n vertices can be drawn on a universal set S of O(n2 / log n) points with at most one bend per edge and with the vertices and the bend points in S. If two bends per edge are allowed, we show that O(n log n) points are sufficient, and if three bends per edge are allowed, Θ(n) points are sufficient. When no bends on edges are permitted, no universal pointset of size o(n2 ) is known for the class of planar graphs.We show that a set of n points in balanced biconvex position supports the class of maximum degree 3 seriesparallel lattices.
Actions (login required)
