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, Würzburg, Germany , 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
ID Code:1449

Repository Staff Only: item control page


Biedl, T. Height-preserving transformations of planar graph drawings. In: Duncan, C., Symvonis, A. eds. (2014) GD 2014. Springer, Heidelberg, pp. 380-391

Biedl, T. A 4-approximation for the height of drawing 2-connected outer-planar graphs. In: Erlebach, T., Persiano, G. eds. (2013) Approximation and Online Algorithms. Springer, Heidelberg, pp. 272-285

Biedl, T.C.: Transforming planar graph drawings while maintaining height. CoRR abs/1308.6693 (2013), http://arxiv.org/abs/1308.6693

Bonichon, N., Saëc, B., Mosbah, M. Wagner’s Theorem on Realizers. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. eds. (2002) Automata, Languages and Programming. Springer, Heidelberg, pp. 1043-1053

Brandenburg, F.J. (2008) Drawing planar graphs on $\frac{8}{9}n^2$ area. Electronic Notes in Discrete Mathematics 31: pp. 37-40

Chrobak, M., Nakano, S. Minimum width grid drawings of plane graphs. In: Tamassia, R., Tollis, I.G. eds. (1995) Graph Drawing. Springer, Heidelberg, pp. 104-110

Fraysseix, H., Pach, J., Pollack, R. (1990) How to draw a planar graph on a grid. Combinatorica 10: pp. 41-51

Djidjev, H., Venkatesan, S.M. (1997) Reduced constants for simple cycle graph separation. Acta Informatica 34: pp. 231-243

Dujmović, V. On the parameterized complexity of layered graph drawing. In: Meyer auf der Heide, F. eds. (2001) Algorithms - ESA 2001. Springer, Heidelberg, pp. 488-499

Frati, F., Patrignani, M. A note on minimum-area straight-line drawings of planar graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. eds. (2008) Graph Drawing. Springer, Heidelberg, pp. 339-344

Hossain, M.I., Mondal, D., Rahman, M.S., Salma, S.A. (2013) Universal line-sets for drawing planar 3-trees. Journal of Graph Algorithms and Applications 17: pp. 59-79

Jordan, C. (1969) Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik 70: pp. 185-190

Mondal, D., Alam, M.J., Rahman, M.S. Minimum-layer drawings of trees - (extended abstract). In: Katoh, N., Kumar, A. eds. (2011) WALCOM: Algorithms and Computation. Springer, Heidelberg, pp. 221-232

Mondal, D., Nishat, R.I., Rahman, M.S., Alam, M.J. (2011) Minimum-area drawings of plane 3-trees. Journal of Graph Algorithms and Applications 15: pp. 177-204

Pach, J., Tóth, G. (2004) Monotone drawings of planar graphs. Journal of Graph Theory 46: pp. 39-47

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of ACM-SIAM SODA, January 22-24, pp. 138–148. ACM (1990)

Suderman, M. (2004) Pathwidth and layered drawing of trees. Journal of Computational Geometry & Applications 14: pp. 203-225

Suderman, M. (2004) Pathwidth and layered drawings of trees. International Journal of Computational Geometry and Applications 14: pp. 203-225