Area-universal drawings of biconnected outerplane graphs

Contact graph representation is a classical graph drawing style where vertices are represented by geometric objects such that edges correspond to contacts between the objects. Contact graph representations using axis-aligned rectilinear polygons are well-investigated. On the other hand, only a scarcity of results and techniques are available for cases using polygons that are not necessarily rectilinear. In this paper, we investigate a type of contact graph representations (named t-TkR) using k-sided convex polygons with their boundaries being t-sided. Given a biconnected outerplane graph, we present a clean necessary and sufficient condition for the graph to admit a t-TkR. We give a linear time algorithm for constructing an area-universal 3-T4R of a given biconnected outerplane graph, which is of interest since most of the previous results on area-universal drawings are with respect to rectilinear settings.