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 , pp. 213-218(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_22).

Full text not available from this repository.


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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/840

Actions (login required)

View Item View Item