Star-shaped and L-shaped orthogonal drawings

An orthogonal drawing of a plane graph G is a planar drawing of G, denoted by D (G) D(G), such that each vertex of G is drawn as a point on the plane, and each edge of G is drawn as a sequence of horizontal and vertical line segments with no crossings. An orthogonal polygon P is called orthogonally convex if the intersection of any horizontal or vertical line L and P is either a single line segment or empty. An orthogonal drawing D(G) is called orthogonally convex if all of its internal faces are orthogonally convex polygons. An orthogonal polygon P is called a star-shaped polygon if there is a point p ∈ P such that the entire P is visible from p. An orthogonal drawing D(G) is called a star-shaped orthogonal drawing (SSOD) if all of its internal faces are star-shaped polygons. Every SSOD is an orthogonally convex drawing, but the reverse is not true. SSOD is visually more appealing than orthogonally convex drawings. Recently, Chang et al. gave a necessary and sufficient condition for a plane graph to have an orthogonally convex drawing. In this paper, we show that if G satisfies the same condition given by Chang et al., it not only has an orthogonally convex drawing, but also a SSOD, which can be constructed in linear time. An orthogonal drawing D(G) is called an L-shaped drawing if each face of D(G) is an L-shaped polygon. In this paper we also show that an L-shaped orthogonal drawing can be constructed in O(n) time. The same algorithmic technique is used for solving both problems. It is based on regular edge labeling and is quite different from the methods used in previous results.