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

DOI10.1007/978-3-319-62127-2_13MaRDI QIDQ2405282zbMATH OpenOpenAlexFDO

Authors Philippe Demontigny, Therese Biedl

Publication date 22 September 2017

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)

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.

Recommendations

• A 4-approximation for the height of drawing 2-connected outer-planar graphs
• Drawing planar graphs with reduced height
• Drawing Planar Graphs with Reduced Height
• Area-efficient planar straight-line drawings of outerplanar graphs
• Small area drawings of outerplanar graphs

Cited in

(5)

• Degenerate drawing of outerplanar graphs with two edge lengths
• scientific article; zbMATH DE number 1156579 (Why is no real title available?)
• A 4-approximation for the height of drawing 2-connected outer-planar graphs
• Computing β-Drawings of 2-Outerplane Graphs in Linear Time
• Faster algorithms for grid and layered drawings of plane 3-trees

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)