“Adaptive grid-based document layout” by Jacobs, Li, Bargeron and Salesin

Grid-based page designs are ubiquitous in commercially printed publications, such as newspapers and magazines. Yet, to date, no one has invented a good way to easily and automatically adapt such designs to arbitrarily-sized electronic displays. The difficulty of generalizing grid-based designs explains the generally inferior nature of on-screen layouts when compared to their printed counterparts, and is arguably one of the greatest remaining impediments to creating on-line reading experiences that rival those of ink on paper. In this work, we present a new approach to adaptive grid-based document layout, which attempts to bridge this gap. In our approach, an adaptive layout style is encoded as a set of grid-based templates that know how to adapt to a range of page sizes and other viewing conditions. These templates include various types of layout elements (such as text, figures, etc.) and define, through constraint-based relationships, just how these elements are to be laid out together as a function of both the properties of the content itself, such as a figure’s size and aspect ratio, and the properties of the viewing conditions under which the content is being displayed. We describe an XML-based representation for our templates and content, which maintains a clean separation between the two. We also describe the various parts of our research prototype system: a layout engine for formatting the page; a paginator for determining a globally optimal allocation of content amongst the pages, as well as an optimal pairing of templates with content; and a graphical user interface for interactively creating adaptive templates. We also provide numerous examples demonstrating the capabilities of this prototype, including this paper, itself, which has been laid out with our system.

1. ADLER, S. 2001 Extensible stylesheet language (XSL) version 1.0. W3C recommendation. http://www.w3.org/TR/xsl/.Google Scholar
2. ANDERSON, R. J. 2002. The power of choice: Content selection in page layout. Technical report, University of Washington.Google Scholar
3. ANDERSON, R. J., AND SOBTI, S. 1999. The table layout problem. In Proceedings of the 15th ACM Symposium on Computational Geometry, 115–123. Google Scholar
4. BADROS, G. J., BORNING, A., MARRIOTT, K., AND STUCKEY, P. 1999. Constraint cascading style sheets for the web. Proceedings of UIST’99, 73–82. Google Scholar
5. BADROS, G. J., BORNING, A., AND STUCKEY, P. J. 2001. The Cassowary linear arithmetic constraint solving algorithm. In Computer-Human Interaction 8 (4), 267–306. Google ScholarDigital Library
6. BADROS, G. J., NICHOLS, J., AND BORNING, A. 2000. Scwm—An intelligent constraint-enabled window manager. In Proceedings of SmartGraphics ’00.Google Scholar
7. BIER, E. A., STONE, M. C. 1986. Snap-dragging. In Proceedings of SIGGRAPH ’86, 233–240. Google Scholar
8. BORNING, A., LIN, R., AND MARRIOTT, K. 2000. Constraint-based document layout for the web. In Multimedia Systems 8.3, 177–189. Google ScholarDigital Library
9. BRÜGGEMAN-KLEIN, A., KLEIN, R., AND WOHLFEIL, S. 1998. On the pagination of complex documents. Technical report, Fernuniversität Hagen {University of Hagen}.Google Scholar
10. FEINER, S. 1988. A grid-based approach to automating display layout. In Proceedings of Graphics Interface ’88, 192–197. Google Scholar
11. FURUTA, R., SCHOFIELD, J., AND SHAW, A. 1982. Document formatting systems: Survey, concepts and issues. In ACM Computing Surveys, 417–472. Google Scholar
12. GLEICHER, M. AND WITKIN, A. 1991. Differential manipulation. In Proceedings of Graphics Interface ’91, 61–67.Google Scholar
13. GRAF, W. H. 1992. Constraint-based graphical layout of multimodal presentations. In Proceedings of AVI ’92, 356–387.Google Scholar
14. GRAF, W. H., NEUROHR, S., GOEBEL, R. 1996. YPPS—A constraint-based tool for the pagination of yellow-page directories. In Proceedings of the KI-96 Workshop on Declarative Constraint Programming, 87–97.Google Scholar
15. HARADA, M., WITKIN, A., AND BARAFF, D. 1995. Interactive physically based manipulation of discrete/continuous models. In Proceedings of SIGGRAPH ’95, 199–208. Google Scholar
16. HEYDON, A., AND NELSON, G. 1994. The Juno-2 constraint-based drawing editor. DEC SRC technical report 131a, Digital Systems Research Center.Google Scholar
17. HURLBURT, A. 1977. Layout: The Design of the Printed Page. Watson-Guptill Publications. New York.Google Scholar
18. HURLBURT, A. 1978. The Grid. Van Nostrand Reinhold Company. New York.Google Scholar
19. JOHARI, R., MARKS, J., PARTOVI, A., AND SHIEBER, S. 1997. Automatic yellow-pages pagination and layout. In Journal of Heuristics 2 (4), 321–342.Google ScholarCross Ref
20. KARSENTY, S., LANDAY, J. A., AND WEIKART, C. 1992. Inferring graphical constraints with Rockit. In Proceedings of HCI ’92, 137–153. Google Scholar
21. KNUTH, D. E. 1986. TEX: The Program, Volume B of Computing and Typesetting. Addison Wesley. New York. Google ScholarDigital Library
22. KNUTH, D. E., AND PLASS, M. F. 1981. Breaking paragraphs into lines. In Software—Practice and Experience 11, 1119–1184.Google ScholarCross Ref
23. KRÖNER, A. 1999. The DesignComposer: Context-based automated layout for the internet. In AAAI 1999 Fall Symposium Series: Using Layout for the Generation, Understanding or Retrieval of Documents.Google Scholar
24. KRÖNER, A., BRANDMEIER, P., AND RIST, T. 2002. Managing layout constraints in a platform for customized multimedia content packaging. In Proceedings of AVI ’02, 89–93. Google Scholar
25. KURLANDER, D., AND FEINER, S. 1993. Inferring constraints from multiple snapshots. In ACM Transactions on Graphics, October, 227–304. Google Scholar
26. LIE, H. W., AND BOS, B. 1996. Cascading style sheets, level 1. W3C recommendation. http://www.w3.org/Style/CSS/.Google Scholar
27. LOK, S., AND FEINER, S. 2001. A Survey of automated layout techniques for information presentations. In SmartGraphics ’01, 61–68.Google Scholar
28. MÜLLER-BROCKMANN, J. 1981. Grid Systems in Graphic Design. Hastings House Publishers. New York.Google Scholar
29. PEELS, A. J. H., JANSSEN, N. T. M., AND NAWIJN, W. 1985. Document architecture and text formatting. In ACM Transactions on Information Systems, 347–369. Google Scholar
30. PLASS, M. F. 1981. Optimal pagination techniques for automatic typesetting systems, technical report STAN-CS-81-870, Department of Computer Science, Stanford University.Google Scholar
31. PURVIS, L. 2002. A genetic approach to automated custom document assembly, In Proceedings of ISDA ’02. Google Scholar
32. SUTHERLAND, I. E. 1963. SketchPad: A man-machine graphical communication system. In Proceedings of AFIPS 23, 323–328.Google Scholar
33. VAN WYK, C. J. 1981. IDEAL user’s manual. Bell Laboratories.Google Scholar
34. WANG, X. 1996. Tabular Abstraction, Editing and Formatting. PhD thesis, University of Waterloo. Google Scholar
35. WEITZMAN, L., AND WITTENBURG, K. 1993. Relational grammars for interactive design. In Proceedings of the IEEE Workshop on Visual Languages, 4–11.Google Scholar
36. WEITZMAN, L., AND WITTENBURG, K. 1996. Grammar-based articulation for multimedia document design. In Multimedia Systems 4, 99–111. Google ScholarDigital Library