| Abstract |
Information visualization, and especially graph drawing, is a key component of support tools for many applications in science and engineering. The automatic generation of drawings of graphs finds many applications, including software engineering, information systems and database systems. In this thesis we introduce a new class of graphs, which we name (page-) layout-graphs. The edges of a layout-graph are labeled as either right, down, left or up. Given a layout-graph G, we define the Frame Layout problem as follows: Decide whether the nodes of G can be drawn in the plane as a set of rectangular frames, such that any two frames corresponding to an edge of G touch each other according to the label of this edge. Our motivation is the following: Suppose we are managing a collection D of information items (e.g., a database), each of which can be visually represented in a rectangular frame, e.g., the way we usually see in the various web-pages. Items may be main text, photos, figures, captions, links, toolbars, banners etc. A subset of items of D may be dynamically selected to be presented, so a page must be set, divided into a set of frames, where each frame is preserved for each item to be presented. For any two items i1 , i2 of D, there may exist the condition that i2 should appear immediately to the right of i1 , expressing some kind of relevance important between i1 and i2 , so the corresponding frames should touch appropriately. Our work explores the possibility of the automatic layout of a page which will be presented on a computer monitor (e.g., a web-page). Each item of collection D becomes a node in our layout graph G, and each contact information between a pair of items becomes an edge in G. We define the Frame Layout problem and solve it in P-time in three phases, through a context-free grammar, planar graphs theory and linear programming. In our thesis we prove that automatic page-layout (e.g., for web applications or/and personalizing applications through user profiles) is theoretically feasible (can be accomplished in P-time). Our algorithms, however, should be optimized in order to be efficient in the context of real-time constraints.
|
Αυτόματη Σχεδίαση Σελίδων : Μια Γραφοθεωρητική Προσέγγιση μλεσω Προσανατολίσιμων Κύκλων
