Drawing Planar Graphs with Reduced Height

Durocher, Stephane and Mondal, Debajyoti (2014) Drawing Planar Graphs with Reduced Height. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 392-403(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_33).

Full text not available from this repository.


A straight-line (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 n-vertex 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 n-vertex planar 3-trees, we compute straight-line 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_33
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.600 Planar
P Styles > P.480 Layered
P Styles > P.540 Planar
P Styles > P.600 Poly-line
P Styles > P.720 Straight-line
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 12:47
Last Modified: 22 May 2015 12:47
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1449

Actions (login required)

View Item View Item