Area-universal drawings of biconnected outerplane graphs

作者：Chang Yi Jun; Yen Hsu Chun^*

来源：Information Processing Letters, 2017, 118: 1-5.

DOI：10.1016/j.ipl.2016.09.003

• Computational geometry
• Contact representation
• Graph drawing
• Plane graph

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.

• 出版日期2017-2