A 2-approximation for the height of maximal outerplanar graph drawings

DOI10.1007/978-3-319-62127-2_13zbMATH Open1491.68134arXiv1702.01719OpenAlexW2528943235MaRDI QIDQ2405282FDOQ2405282

Publication date: 22 September 2017

Abstract: In this paper, we study planar drawings of maximal outerplanar graphs with the objective of achieving small height. 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 so-called 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.

Full work available at URL: https://arxiv.org/abs/1702.01719

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cited In (3)

This page was built for publication: A 2-approximation for the height of maximal outerplanar graph drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2405282)