Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Star-Shaped and L-Shaped Orthogonal Drawings
Xin He and Dayu He
Vol. 21, no. 2, pp. 155-175, 2017. Regular paper.
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.
Submitted: February 2016.
Reviewed: June 2016.
Revised: August 2016.
Reviewed: September 2016.
Revised: December 2016.
Accepted: December 2016.
Final: December 2016.
Published: January 2017.
Communicated by Seok-Hee Hong