TY - GEN
T1 - Star shaped orthogonal drawing
AU - He, Xin
AU - He, Dayu
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - An orthogonal drawing of a plane graph G is a planar drawing, denoted by D(G), of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. D(G) is called orthogonally convex if each of its faces is an orthogonally convex polygon P. (Namely, for any horizontal or vertical line L, the intersection of L and P is a single line segment or empty). Recently, Chang et al. [1] gave a necessary and sufficient condition for a plane graph to have such a drawing. D(G) is called a star-shaped orthogonal drawing (SSOD) if each of its faces is a star-shaped polygon P. (Namely there is a point p ∈ P such that the entire P is visible from p). Every SSOD is an orthogonally convex drawing, but the reverse is false. SSOD is visually more appealing than orthogonally convex drawings. In this paper, we show that if G satisfies the same conditions as in [1], it not only has an orthogonally convex drawing, but also a SSOD, which can be constructed in linear time.
AB - An orthogonal drawing of a plane graph G is a planar drawing, denoted by D(G), of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. D(G) is called orthogonally convex if each of its faces is an orthogonally convex polygon P. (Namely, for any horizontal or vertical line L, the intersection of L and P is a single line segment or empty). Recently, Chang et al. [1] gave a necessary and sufficient condition for a plane graph to have such a drawing. D(G) is called a star-shaped orthogonal drawing (SSOD) if each of its faces is a star-shaped polygon P. (Namely there is a point p ∈ P such that the entire P is visible from p). Every SSOD is an orthogonally convex drawing, but the reverse is false. SSOD is visually more appealing than orthogonally convex drawings. In this paper, we show that if G satisfies the same conditions as in [1], it not only has an orthogonally convex drawing, but also a SSOD, which can be constructed in linear time.
UR - https://www.scopus.com/pages/publications/84929615771
U2 - 10.1007/978-3-319-17142-5_13
DO - 10.1007/978-3-319-17142-5_13
M3 - Conference contribution
AN - SCOPUS:84929615771
T3 - Lecture Notes in Computer Science
SP - 137
EP - 149
BT - Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings
A2 - Jain, Rahul
A2 - Jain, Sanjay
A2 - Stephan, Frank
PB - Springer Verlag
T2 - 12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015
Y2 - 18 May 2015 through 20 May 2015
ER -