Orthogonal grid pointset embeddings of maximal outerplanar graphs

摘要

An orthogonal drawing of a planar graph G is a drawing of G where each vertex is mapped to a point, each edge is drawn as a sequence of alternate horizontal and vertical line segments on the grid lines, and any two edges do not cross except at their common end. Clearly the maximum degree of G is at most 4 if G has an orthogonal drawing. Let G be a planar graph with n vertices, and let S be a set of n prescribed grid points. An orthogonal grid pointset embedding of G on S is an orthogonal drawing of G such that each vertex of G is drawn as a point in S. Although every planar graph of maximum degree 4 has an orthogonal drawing, not every such graph has an orthogonal grid pointset embedding. Not much works on orthogonal grid pointset embedding are found in literature. In this paper we give lineartime algorithms for finding three variants of orthogonal pointset embeddings of a maximal outerplanar graph of maximum degree 4. We also give a linear-time algorithm to determine whether an outerplanar graph can be triangulated to a maximal outerplanar graph of maximum degree 4 and find such a triangulation if it exists.