OPTIMAL-AREA VISIBILITY REPRESENTATIONS OF OUTER-1-PLANE GRAPHS

This paper studies optimal-area visibility representations of n-vertex outer-1-plane graphs, i.e., graphs with a given embedding where all vertices are on the boundary of the outer face and each edge is crossed at most once. We show that any graph of this family admits an embedding-preserving visibility representation whose area is O(n1.5) and prove that this area bound is worst-case optimal. We also show that O(n1.48) area can be achieved if we do not respect the embedding but still have at most one crossing per edge. A key ingredient of our constructions is the existence of a special root-to-leaf path for trees of arbitrary degree, which extends a previous result by Chan for binary trees and forms a result of independent interest.