Abstract:

Embedded hypermedia documents are becoming more common in aircraft cockpits, power- and industrial-plant control panels, and other exacting multimodal user interfaces. These high-performance hypermedia documents (HPHDs) are often large and heavily cross referenced, yet they must support extremely efficient user navigation. Designing such documents well is difficult. In this paper, we describe an approach to structuring HPHDs automatically. We show how ease of navigation can be formulated as a set of optimality criteria. Given these criteria, we describe how an abstract statement of the document-structuring problem is equivalent to a version of the well-known optimization problem of graph partitioning. We present a system that uses known graph-partitioning heuristics to structure HPHDs with near optimality. Keywords: high-performance hypermedia documents, hypermedia-document structuring, hypermedia design, graph partitioning, heuristic search.