Apparatus for determining the structure of a hypermedia document using graph partitioning

• US 5,546,517 A
• Filed: 12/07/1994
• Issued: 08/13/1996
• Est. Priority Date: 12/07/1994
• Status: Expired due to Fees

• Current Assignee: President and Fellows of Harvard College (Harvard Corporation), Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Information Technology Center America, Inc. (Mitsubishi Electric Corporation)
• Inventors: Hwa, Rebecca P., Shieber, Stuart M., Marks, Joseph W.
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): HONG, STEPHEN S
• Application Number:
  US08/350,656
• Time in Patent Office: 615 Days
• Field of Search: 395/145-148, 395/160, 395/50, 364/282.2, 364/282.3, 364/282.4, 364/283.2, 364/283.3
• US Class Current: 715/206
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134

Abstract

Apparatus for determining the structure of a hypermedia document containingext and graphics that are to be laid out on several linked pages includes a system that specifies the assignment of text and graphics to pages and the links between the pages via a reduction to graph partitioning and the use of optimization techniques for graph partitioning. In one embodiment, display items and relations between these display items are listed along with a measure of their importance. These factors are captured in terms of numeric weights for edges between nodes in the associated graph to permit the system to assign display items to pages, and determine which pages should be linked, so that a user can move between pages in the most efficient manner. In a further embodiment, to accommodate limited display area that restricts the number of display items and page links that can be displayed simultaneously, the system can take into account multistage page moves that allow the user to access display items on different pages in sequence by moving from one page to another via links on other pages, through the use of "stepping-stone" nodes in the associated graph that record possible traversal routes in the document that are not represented in other formulations of the hypermedia-document-layout task.

Claims

1. Apparatus for allocating display items to each page of a hypermedia document containing display items that are to be laid out on several linked pages, comprising:

means for automatically allocating said display items of said document to said pages by automatically specifying the assignment of said display items to each page by using a reduction to graph partitioning and an optimization technique for said graph partitioning and for automatically creating linkages between said pages including means for reducing said assigned display items and linkages to a graph partition to provide an optimized graph partition specifying assignments of display items and linkages, whereby a convenient document structure is automatically provided in which linkages and page content are automatically created, thus eliminating the necessity for the author to prespecify page content or linkage structure.

2. The Apparatus of claim 1 wherein said assigning means includes means for providing a list of display items, edges between display items and a numeric value corresponding to the importance thereof.

3. The Apparatus of claim 2 wherein said numeric value relates to the importance of said edges, thereby to permit said assignment of display items to pages and determination of pages to be linked.

4. The Apparatus of claim 1 wherein said display items include text.

5. The Apparatus of claim 1 wherein said display items include graphics.

6. The Apparatus of claim 1, wherein said graph partition includes stepping-stone nodes which divide one of said edges into two edges.

7. The Apparatus of claim 6, wherein said stepping-stone nodes divide up existing edges in said graph prior to partitioning.

8. The Apparatus of claim 1 wherein one of said means for optimizing includes means for performing a Kernighan-Lin graph partition.