Abstract
In this paper, we study planar drawings of maximal outerplanar graphs with the objective of achieving small height. (We do not necessarily preserve a given planar embedding.) A recent paper gave an algorithm for such drawings that is within a factor of 4 of the optimum height. In this paper, we substantially improve the approximation factor to become 2. The main ingredient is to define a new parameter of outerplanar graphs (the umbrella depth, obtained by recursively splitting the graph into graphs called umbrellas). We argue that the height of any poly-line drawing must be at least the umbrella depth, and then devise an algorithm that achieves height at most twice the umbrella depth.
TB supported by NSERC. Part of this work appeared as PD’s Master’s thesis [10].
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alam, M.J., Samee, M.A.H., Rabbi, M., Rahman, M.S.: Minimum-layer upward drawings of trees. J. Graph Algorithms Appl. 14(2), 245–267 (2010)
Batzill, J., Biedl, T.: Order-preserving drawings of trees with approximately optimal height (and small width) (2016). CoRR 1606.02233 [cs.CG] (in submission)
Biedl, T.: Drawing outer-planar graphs in O(n log n) area. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 54–65. Springer, Heidelberg (2002). doi:10.1007/3-540-36151-0_6
Biedl, T.: Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discrete and Computational Geometry 45(1), 141–160 (2011)
Biedl, T.: A 4-approximation for the height of drawing 2-connected outer-planar graphs. In: Erlebach, T., Persiano, G. (eds.) WAOA 2012. LNCS, vol. 7846, pp. 272–285. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38016-7_22
Biedl, T.: Height-preserving transformations of planar graph drawings. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 380–391. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45803-7_32
Demaine, E.D., Huang, Y., Liao, C.-S., Sadakane, K.: Canadians Should Travel Randomly. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 380–391. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43948-7_32
Biedl, T.: Ideal tree-drawings of approximately optimal width (and small height). Journal of Graph Algorithms and Applications 21(4), 631–648 (2017)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)
Demontigny, P.: A 2-approximation for the height of maximal outerplanar graphs. Master’s thesis, University of Waterloo (2016). See also CoRR report 1702.01719
Di Battista, G., Frati, F.: Small area drawings of outerplanar graphs. Algorithmica 54(1), 25–53 (2009)
Dujmovic, V., Fellows, M., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F., Whitesides, S., Wood, D.: On the parameterized complexity of layered graph drawing. Algorithmica 52, 267–292 (2008)
Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. J. Graph Alg. Appl 7(4), 335–362 (2003)
Frati, F.: Straight-line drawings of outerplanar graphs in \({O}(dn\log n)\) area. Comput. Geom. 45(9), 524–533 (2012)
Garg, A., Rusu, A.: Area-efficient planar straight-line drawings of outerplanar graphs. Discrete Applied Mathematics 155(9), 1116–1140 (2007)
Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM Journal on Computing 21(5), 927–958 (1992)
Krug, M., Wagner, D.: Minimizing the area for planar straight-line grid drawings. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 207–212. Springer, Heidelberg (2008). doi:10.1007/978-3-540-77537-9_21
Mondal, D., Alam, M.J., Rahman, M.S.: Minimum-layer drawings of trees. In: Katoh, N., Kumar, A. (eds.) WALCOM 2011. LNCS, vol. 6552, pp. 221–232. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19094-0_23
Schnyder, W.: Embedding planar graphs on the grid. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 1990), pp. 138–148 (1990)
Suderman, M.: Pathwidth and layered drawings of trees. Intl. J. Comp. Geom. Appl, 14(3), 203–225 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Biedl, T., Demontigny, P. (2017). A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings. In: Ellen, F., Kolokolova, A., Sack, JR. (eds) Algorithms and Data Structures. WADS 2017. Lecture Notes in Computer Science(), vol 10389. Springer, Cham. https://doi.org/10.1007/978-3-319-62127-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-62127-2_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62126-5
Online ISBN: 978-3-319-62127-2
eBook Packages: Computer ScienceComputer Science (R0)