Visibility representations of four-connected plane graphs with near optimal heights

AbstractA visibility representation of a graph G is to represent the nodes of G with non-overlapping horizontal line segments such that the line segments representing any two distinct adjacent nodes are vertically visible to each other. If G is a plane graph, i.e., a planar graph equipped with a planar embedding, a visibility representation of G has the additional requirement of reflecting the given planar embedding of G. For the case that G is an n-node four-connected plane graph, we give an O(n)-time algorithm to produce a visibility representation of G with height at most ⌈n2⌉+2⌈n−22⌉. To ensure that the first-order term of the upper bound is optimal, we also show an n-node four-connected plane graph G, for infinite number of n, whose visibility representations require heights at least n2