Title: Linear Arrangement of Halin Graphs
Authors: Saber Mirzaei and Assaf Kfoury
Date: September 1, 2015
Abstract:
We study the Optimal Linear Arrangement (OLA) problem of Halin
graphs, one of the simplest classes of non-outerplanar graphs. We
present several properties of OLA of Halin graphs in general. We prove
a lower bound on the cost of OLA of any Halin graph, and define
classes of Haling graphs for which the cost of OLA matches this lower
bound. We show for these classes of Halin graphs, OLA can be computed
in (n log n) time, where n is the number of vertices.