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 represent the vertices as L-shaped orthogonal polygons or if we do not respect the embedding but still have at most one crossing per edge. We also extend the study to other representation models and, among other results, construct asymptotically optimal O(npw(G)) area bar-1-visibility representations, where pw(G) ∈ O(log n) is the pathwidth of the outer-1-planar graph G.