Home

CNOP

Research Interests & Publications

Contact

Table Layout

Consider the problem of laying out a two-dimensional table. Each cell of the table has content associated with it and we have choices on the geometry of cells. The table layout problem is to choose configurations for the cells to minimize the table height given a fixed width for the table. This problem has applications in word processing and WWW page design.
Anderson and Sobti [SCG99] showed how to model this a graph problem and how to compute an approximation using iterations of min cut computations like in the hull approach.
Again the CNOP package can be used to get an implementation of this method.
The following table is an excerpt from the german book bestseller list. The table's height is 4 characters and the table's width is 71 characters (also counting whitespaces between words).
Belletristik Sachbücher
Joanne Rowling: Harry Potter Marcel Reich- Ranicki: Mein Leben
Rosamunde Pilcher: Wintersonne Lance Armstrong: Tour des Lebens
Donna Leon: In Sachen Signora Brunetti Florian Illies: Generation Golf

Suppose now that this table is too wide to fit on a page and that the maximum width we can use is 29 characters. Then this is a minimum height table (height is 10 characters) satisfying the width constraint (table content may be broken at whitespaces).
Belletristik Sachbücher
Joanne
Rowling:
Harry Potter		 Marcel Reich-
Ranicki: Mein
Leben
Rosamunde
Pilcher:
Wintersonne		 Lance
Armstrong: Tour
des Lebens
Donna Leon: In
Sachen Signora
Brunetti		 Florian Illies:
Generation Golf

 

Impressum & Webmaster     last change: 04.01.2008   mark.ziegelmanngmx.de