Drawing Planar Graphs with Many Collinear VerticesDa Lozzo, Giordano and Dujmović, Vida and Frati, Fabrizio and Mchedlidze, Tamara and Roselli, Vincenzo (2016) Drawing Planar Graphs with Many Collinear Vertices. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 152165(Official URL: http://dx.doi.org/10.1007/9783319501062_13). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_13
AbstractGiven a planar graph G, what is the maximum number of collinear vertices in a planar straightline drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known: Every nvertex planar graph has a planar straightline drawing with Ω(√n) collinear vertices; for every n, there is an nvertex planar graph whose every planar straightline drawinghas O(n^0.986) collinear vertices; every nvertex planar graph of treewidth at most two has a planar straightline drawingwith Θ(n) collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs, partially answering two problems posed by Ravsky and Verbitsky. Similar results are not possible for all bounded treewidth or bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.
Actions (login required)
