Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00409
StarShaped and LShaped Orthogonal Drawings
Xin He and
Dayu He
Vol. 21, no. 2, pp. 155175, 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 starshaped 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 starshaped orthogonal
drawing (SSOD) if all of its internal faces are starshaped 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
SeokHee Hong
