Star-Shaped and L-Shaped Orthogonal Drawings

Abstract

An orthogonal drawing of a plane graph $G$ is a planar drawing of $G$, denoted by $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\in 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.