Drawing Planar Graphs with Reduced HeightDurocher, Stephane and Mondal, Debajyoti (2014) Drawing Planar Graphs with Reduced Height. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 392403(Official URL: http://dx.doi.org/10.1007/9783662458037_33). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_33
AbstractA straightline (respectively, polyline) drawing Γ of a planar graph G on a set L k of k parallel lines is a planar drawing that maps each vertex of G to a distinct point on L k and each edge of G to a straight line segment (respectively, a polygonal chain with the bends on L k ) between its endpoints. The height of Γ is k, i.e., the number of lines used in the drawing. In this paper we compute new upper bounds on the height of polyline drawings of planar graphs using planar separators. Specifically, we show that every nvertex planar graph with maximum degree Δ, having a simple cycle separator of size λ, admits a polyline drawing with height 4n/9 + O(λΔ), where the previously best known bound was 2n/3. Since λ∈O(n√) , this implies the existence of a drawing of height at most 4n/9 + o(n) for any planar triangulation with Δ∈o(n√) . For nvertex planar 3trees, we compute straightline drawings with height 4n/9 + O(1), which improves the previously best known upper bound of n/2. All these results can be viewed as an initial step towards compact drawings of planar triangulations via choosing a suitable embedding of the input graph.
Actions (login required)
