Algorithms for polyline drawings of plane 3-trees

Abstract

This thesis deals with polyline grid drawings of planar graphs. A polyline drawing of a planar graph is a drawing of the graph where each vertex is drawn on a grid point and each edge is drawn by a polygonal chain. A point at which an edge changes its direction in a polyline drawing is called a bend. It is known that every plane graph of n≥3 vertices has a straight line grid drawing on a grid of size (|4 n| × |2 n|). It has been conjectured that every plane graph has a straight line grid drawing on a grid of size |2n | × |2n |, but the conjecture still remains as an open problem. Grid area can be minimized if we allow bends on edges. Linear-time algorithms are known for polyline drawings of planar graphs on grid of size ( 4(n−1)2 ) with at most (n − 2) bends as well as on grid of size |2n−5 × (n − 2) with at most |2n−5 bends. In this paper we give a simple algorithm that gives polyline drawing of a plane 3-tree on a grid of size (|3n+2 | − 1) × (|3n+2 ) and with at most |n/2 bends. We also give some linear-time algorithms those give polyline drawings of some subclasses of plane 3-trees on compact grid area with constant bends. We have also studied on polyline rook drawings of planar graphs. A polyline rook drawing of a planar graph is a drawing of the graph where each vertex is drawn on a grid point and each edge is drawn by a polygonal chain where each gridline contains exactly one vertex. There is a

linear-time algorithm to get polyline rook drawing of planar graphs with at most 2n−5

bends.

In this paper, we give a linear-time algorithm that gives polyline rook drawing of a plane 3-tree with number of bends |n |.