AN APPLICATION OF WELL-ORDERLY TREES IN GRAPH DRAWING
HUAMING ZHANG, Xin He · International Journal of Foundations of Computer Science · 2006
Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height [Formula: see text], which can be constructed in linear time. This improves the best previous bound of [Formula: see text].