Linear arrangement of Halin graphs

Thumbnail
Date Issued
2015-09-01
Author(s)
Kfoury, Assaf
Mirzaei, Saber
Share to FacebookShare to TwitterShare by Email
Export Citation
Metadata
Show full item record
Permanent Link
https://hdl.handle.net/2144/21776
Citation (published version)
Kfoury, Assaf; Mirzaei, Saber. Linear Arrangement of Halin Graphs. Technical Report BU-CS-TR 2015-012, Computer Science Department, Boston University, 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 general Halin graphs. We prove a lower bound on the cost of OLA of any Halin graph, and define classes of Halin graphs for which the cost of OLA matches this lower bound. We show for these classes of Halin graphs, OLA can be computed in nlog n, where n is the number of vertices.
Collections