A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings

Approximation Algorithm;Outerplanar Graph;Layered Drawing;Umbrella;Umbrella System;Umbrella Depth;Height;Flat Visibility Representation

Demontigny, Philippe

University of Waterloo

关键词: Approximation Algorithm;    Outerplanar Graph;    Layered Drawing;    Umbrella;    Umbrella System;    Umbrella Depth;    Height;    Flat Visibility Representation;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/10652/1/Demontigny_Philippe.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In this thesis, we study drawings of maximal outerplanar graphs that place vertices on integer coordinates. We introduce a new class of graphs, called umbrellas, and a new method of splitting maximal outerplanar graphs into systems of umbrellas. By doing so, we generate a new graph parameter, called the umbrella depth (ud), that can be used to approximate the optimal height of a drawing of a maximal outerplanar graph. We show that for any maximal outerplanar graph G, we can create a flat visibility representation of G with height at most 2ud(G) + 1. This drawing can be transformed into a straight-line drawing of the same height. We then prove that the height of any drawing of G is at least ud(G) + 1, which makes our result a 2-approximation for the optimal height. The best previously known approximation algorithm gave a 4-approximation. In addition, we provide an algorithm for finding the umbrella depth of G in linear time. Lastly, we compare the umbrella depth to other graph parameters such as the pathwidth and the rooted pathwidth, which have been used in the past for outerplanar graph drawing algorithms.