On Planar Polyline Drawings

Zhang, Huaming and Sadasivam, Sadish (2008) On Planar Polyline Drawings. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 213-218 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_22).

Full text not available from this repository.

Abstract

We present a linear time algorithm that produces a planar polyline drawing for a plane graph with $n$ vertices in a grid of size bounded by $(p+1) times (n-2)$, where $p leq (lfloor frac2n-53rfloor)$. It uses at most $p leq lfloorfrac2n-53rfloor$ bends, and each edge uses at most one bend. Compared with the area optimal polyline drawing algorithm in [3], our algorithm uses a larger grid size bound in trade for a smaller bound on the total number of bends. Their bend bound is $(n-2)$. Our algorithm is based on a transformation from Schnyder's realizers [6, 7] of maximal plane graphs to transversal structures [4, 5] for maximal internally 4-connected plane graphs. This transformation reveals important relations between the two combinatorial structures for plane graphs, which is of independent interest.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_22
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
ID Code:840

Repository Staff Only: item control page

References

G. di Battista, P. Eades, R. Tamassia, and I. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1998

N. Bonichon, B. Le Saec and M. Mosbah, Wagner's theorem on realizers, in: Proc. ICALP'02, Lecture Notes in Computer Science, Vol. 2380, (Springer, Berlin, 2002) 1043-1053.

N. Bonichon, B. Le Saec and M. Mosbah, Optimal area algorithm for planar polyline drawings, in: Proc. WG'02, Lecture Notes in Computer Science, Vol. 2573, (Springer, Berlin, 2002) 35-46.

É. Fusy, Transversal structures on triangulations, with application to straight-line drawing, in Proc. of 13th International Symposium on Graph Drawing Lecture Notes in Computer Science, Vol. 3843 (2005), pp. 177-188

X. He, On finding the rectangular duals of planar triangular graphs. SIAM Journal on Computing 22 (1993), 1218-1226.

W. Schnyder, Planar graphs and poset dimension. Order 5 (1989), 323-343.

W. Schnyder, Embedding planar graphs on the grid, in Proc. of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 138-148, SIAM, Philadelphia, 1990.