Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00409
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
|
Journal Supporters
|