Toward Tighter Tables

Tables are provided in virtually all document formatting systems and are one of the most powerful and useful design elements in current web document standards. Unfortunately, optimal layout of tables which contain text is NP-hard for reasonable layout requirements such as minimizing table height for a given width. We present two new independently-applicable techniques for table layout. The first technique is to solve a continuous approximation to the original layout problem by using a constant-area approximation of the cell content combined with a minimum width and height for the cell. The second technique starts by setting each column to its narrowest possible width and then iteratively reduces the height of the table by judiciously widening its columns. This second technique uses the actual text and line-break rules rather than the constant-area approximation used by the first technique. We also investigate two hybrid approaches both of which use iterative column widening to improve the quality of an initial solution found using a different technique. In the first hybrid approach we use the continuous approximation technique to compute the initial column widths while in the second hybrid approach a modification of the HTML table layout algorithm is used to compute the initial widths. We found that all four techniques are reasonably fast and give significantly more compact layout than that of HTML layout engines.