Wei Lai [HREF1], Department of Mathematics and Computing, University of Southern Queensland, QLD 4350, Australia. wlai@usq.edu.au
Mao Lin Huang [HREF2], Department of Computer Science and Software Engineering, University of Newcastle, NSW 2308, Australia. mhuang@cs.newcastle.edu.au
Yanchun Zhang [HREF3], Department of Mathematics and Computing, University of Southern Queensland, QLD 4350, Australia. yan@usq.edu.au
Mark Toleman [HREF4], Department of Mathematics and Computing, University of Southern Queensland, QLD 4350, Australia. markt@usq.edu.au
Most Web browsers, such as Netscape and Microsoft Internet Explorer, cannot give users a visual "map" to guide their Web journey. Our approach is to use a graph for Web navigation. We look at the whole of cyberspace as one huge graph. To explore this huge graph, it is critical to find an effective method of tracking and displaying an on-line sub-graph of the huge graph based on the user's focus. This paper introduces our method for Web graph displays. Any on-line Web sub-graph should fit in the display window. To enhance the display of a Web sub-graph, there should not be any overlap between node images in the Web sub-graph. Our system ensures that any on-line Web sub-graph has no overlapping node images by letting the user, or the system itself, define visible and invisible parts of the Web graph.
Most Web browsers, such as Netscape and Microsoft Internet Explorer, cannot provide a contextual overview required for global orientation; instead they can only give book-marks and history lists which are at most a linear list. They cannot provide relationships between the URLs.
How can we find alternative paths, or shortest paths, other than try adding interesting URLs to our unmanageable list of favourites, so all pages are one-hop away. There is little assistance in current browsers for selecting the mirror site that is Web-closest to out local network. Maps provide a capacity to plan routes, to retrace steps, and to evaluate alternatives.
In our real world, travellers, pilots and sailors need maps to guide their journey. Why do we ignore use of maps and why shouldn't we have a map in our Web journey?
Some researchers have proposed "site mapping" methods (Pilgrim and Leung 1996, Maarek and Shaul 1997, Chen and Koutsofios 1997) to aid in navigation and maintain a sense of orientation. This approach attempts to find an effective way of constructing a structured geometrical map for one Web site (a local map). However, this can only guide the user through a very limited region of cyberspace, and does not help users in their overall journey through cyberspace.
Our approach is to use a graph for World Wide Web (WWW) navigation. Nodes in a graph can be used to represent URLs, and edges between nodes represent links between URLs. We look at the whole cyberspace of the WWW as one graph - a huge and dynamic growing graph. We call this graph the Web graph. The Web graph can give the user a 2-dimensional view for URLs and their interconnections. However, it is impossible to display this huge Web graph on the computer screen.
This paper introduces our method of using visible subsets of the Web graph for WWW navigation. A visible subset is formed based on the user's interaction. The visible subset should be changed dynamically and should follow the user's focus in navigation. This change from one visible subset to another should preserve the user's mental map (Eades et al 1991, Misue et al 1995) for WWW navigation. We adapt Huang et al's on-line exploratory visualisation technique (Huang et al 1998) which provides a major departure from traditional site-mapping methods. It does not pre-define the geometrical structure of a specific Web site (a part of cyberspace); instead it incrementally calculates and maintains a small visualisation of a subset of cyberspace on-line, corresponding to the change of the user's focus. That is, it automatically displays a sequence of Web sub-graphs with smooth animation following the user's orientation. This feature enables the user to logically explore the entire cyberspace without requiring the whole structure of the cyberspace to be known.
However, Huang et al's approach uses the FIFO (first in and first out) rule to animate Web sub-graphs, which cannot support the user's involvement in defining a Web sub-graph. Also, Huang et al's approach cannot ensure its Web sub-graph layout has no overlapping node images. Our method for Web graph displays overcomes these drawbacks.
There are two major features of our Web graph displays. One is that the user can interact with the Web graph to let a node's sub-graph be visible or invisible. The other is that overlapping node images / sub-graphs are detected and defined as visible or invisible automatically based on the user's focus.
The best way to show our Web graph display system is to use some examples. Figure 1 shows an on-line Web sub-graph. Our system can ensure that any on-line Web sub-graph has no overlapping node images and it fits in the window. If the user clicks a node in the Web sub-graph, the node's sub-graph is changed from invisible to visible or from visible to invisible. Figure 2 shows the results after the user clicks the nodes - Phone Fax Email and Teaching in the Web sub-graph shown in Figure 1. If the user clicks these nodes again, their sub-graphs would become invisible (i.e. they would disappear as shown in Figure 1). In this way, the user can define a visible or invisible sub-graph by direct manipulation.
When a node's sub-graph becomes visible, our system checks whether there will be overlaps between any part of the current display and this sub-graph. If so, those parts overlapping the sub-graph would become invisible automatically. For instance, in Figure 3 after the user clicks the node with label Research the sub-graph of this node appears and the sub-graph of the node Teaching automatically disappears.
A node in the Web graph is linked to a URL. For example, the node with label USQ is linked to the home page of the University of Southern Queensland. The system provides two modes from which the user can select. One is the Navigation mode, the other is the ShowPage mode. The user can switch between the modes by clicking the middle mouse button. Our system can support the display of a detailed Web page corresponding to a node in a Web sub-graph (after the ShowPage model is set up). Figure 4 shows the result of the user's selecting the node with label USQ in the ShowPage mode.
In our prototype implementation of the system, we use the node with label Links to connect other Web sites. In this way, we could test that the system can navigate from one Web site to another one. For example, the node with label CNN is one of the lists under the node with label Links Figure 5 shows a Web sub-graph about CNN and the CNN Web page following the user's interaction. The Web sub-graph about CNN also keeps track of the user's navigation. That is, it includes two nodes - Wei Lai and Links for indicating the previous two steps of navigation.
Our system design integrates techniques on graphical user interfaces, automatic graph layouts, distributed computing, Internet and Web programming, computer networks and communications. This section introduces some design issues.
The architecture for our system includes two major components: a Web graph user interface component and a dialog component for the communication between the diagram user interface and the WWW.
The Web graph user interface component displays Web sub-graphs and provides some editing functions for the user to adjust a diagram layout, to navigate the Web graph by choosing a focused node, and so on. It provides two kinds of modes for the user's interaction with the Web graph: Navigation and ShowPage as mentioned in Section 2.
The dialog component supports the construction of Web sub-graphs by communicating with Web sites over the Internet. It can quickly search the entire neighbourhood of the focused node to form a Web sub-graph.
The most difficult editing function for a Web graph is layout - assigning a position for each node and a curve for each edge. The assignment must be chosen to make the resulting picture easy to understand and easy to remember. A good layout can be like a picture - worth a thousand words; a poor layout can confuse or mislead the user. This problem is called the graph drawing problem - how to create a nice layout, automatically. Automatic layout can release the user from the time-consuming and detail-intensive chore of generating a readable diagram. However, most existing systems that incorporate diagrams, such as CASE tools, do not support automatic layout; the layout decisions in these systems have to be made by the user by using the mouse and the screen to replace the pen and paper.
Most classical graph drawing algorithms (Battista, et al, 1994) produce aesthetically pleasing abstract graph layouts. These algorithms can be applied to draw practical graphs as long as the sizes of nodes take very little space. This is because such algorithms were often originally designed for abstract graphs where nodes take up little or no space. However, in applications, the images of nodes are circles, boxes, diamonds and similar shapes, and may contain a considerable amount of text and graphics. In some systems (Eades & Lai, 1990; Harel, 1988; Sugiyama & Misue, 1991) nodes are used to represent sub-graphs, and may be quite unpredictable in size and shape. Applying such algorithms to practical graphs may result in overlapping nodes and/or edge-node intersections. Algorithms which exemplify this problem can be found in (Eades, 1984; Kamada & Kawai, 1989) - they produce diagrams which are nicely symmetric and well spread out, and have great potential for use in visualisation of network structures. However nodes of nontrivial size in a diagram produced by these algorithms tend to overlap.
We are interested in the problem of how to display diagrams, that is, how to lay out practical graphs in applications. The term abstract graph layout refers to layout techniques for abstract graphs where nodes are negligible in size. The term practical graph layout refers to layout techniques for practical graphs where nodes vary in shape and size.
Our approach is to make use of existing classical graph drawing algorithms. That is, to apply a classical graph drawing algorithm to a practical graph. Then we need to develop some post-processes to avoid overlaps of node images and edge-node intersections by rearranging the graph layout (Lai & Eades, 1998). The techniques for adjusting a graph layout should preserve the mental map of the original graph (Eades, et al, 1991; Misue, 1995).
We have applied some techniques on graph layout and navigation (Lai & Eades, 1995, Lai & Danaher, 1996; Lai & Eades, 1998) to our Web graph display system.
We should provide a formalised graph structure that can represent a wide variety of complex relations and support powerful automatic graph layout operations.
Harel presents higraphs (Harel, 1988) which can represent complex relations. They involve multi-level blobs that can enclose or intersect each other.
Sugiyama and Misue present compound digraphs (Sugiyama & Misue, 1991). The compound digraph is an extension of the directed graph.
Automatic drawing procedures for higraphs are difficult to develop since higraphs pose many additional difficulties for good layout. The main source of difficulty is that "blobs" are allowed to intersect in arbitrary ways.
The algorithm for drawing compound digraphs (Sugiyama & Misue, 1991), derived from the directed graph drawing algorithm, generate the overall layout by optimizing specific prescribed aesthetics. It lacks flexibility in supporting the user control of the layout process with varying aesthetics.
CIgraphs (Compound graphs with Integrated layout functions) (Lai & Eades, 1995) can represent more complicated graph structures and integrate automatic layout facilities. In a CIgraph, each node may consist of a (sub)CIgraph. Layout functions are assigned to nodes (that is, to sub-CIgraphs) in an object-oriented fashion, allowing considerable user control. In our Web graph displays, we use the CIgraph model.
We have developed a linkage mechanism between the Web graph interface and the WWW. This linkage mechanism was developed using techniques in computer network and Internet programming.
To quickly obtain the linkage information (the neighbourhood of the focused URL) for dynamically creating a Web sub-graph, we need a fast accessible linkage server. This server is deduced from the main Web server. It can produce the entire neighbourhood of focus nodes. In its basic operation, the server accepts a query of a URL of the user clicked focus node, and then returns a list of all pages that point to/are pointed from the page that represents the focus node.
We are using Java as the major software development tool for the implementation of our system. A prototype of the Web graph user interface for WWW navigation has been developed. Some examples of diagram displays from the prototype have been shown in Section 2.
This paper introduces a new Web graph display system. The major feature of the system is to provide visible subsets of the Web graph for WWW navigation. Our Web graph display technique creates an automatic layout that does not overlap or exceed the viewing area.
Further work is needed to improve the Web graph user interface. In particular, We will continue to investigate layout techniques that will enhance potential usability of the system. Also, we need to test our Web graph interface with end-users to see whether they prefer this kind of interface for WWW navigation over more traditional styles.
Battista, G. D., Eades, P., Tamassia, R. and Tollis, T. (1994). Algorithms for drawing graphs: an annotated bibliography. Computational Geometry Theory and Applications, vol. 4, 235-282.
Chen, Y. and Koutsofios, E. (1997). WebCiao: A Website visualisation and tracking system. Proceedings of WebNet 97 Conference.
Eades, P. (1984). A heuristic for graph drawing. Congressus Numerantium, 42:149-160.
Eades, P. and Lai, W. (1990). Visual interface design for relational systems. Proceedings of the 5th Australian Software Engineering Conference, Sydney, pages 259-263.
Eades, P., Lai, W., Misue, K. and Sugiyama, K. (1991). Preserving the mental map of a diagram. Proceedings of COMPUGRAPHICS 91, pages 34-43.
Harel, D. (1988). On visual formalisms. Communications of the ACM, 31(5):514-530.
Huang, M. L., Eades, P. and Cohen, R. F. (1998). WebOFDAV - Navigating and visualising the Web on-line with animated context swapping. Proceedings of the 7th International World Wide Web Conference, pages 638-642.
Kamada, K. and Kawai, S. (1989). An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15.
Lai, W. and Danaher, M. (1996). Diagram navigation for information browsing. Proceedings of APCHI'96 (Asia Pacific Conference on Computer Human Interaction), Singapore, pages 339-345.
Lai, W. and Eades, P. (1995). CIGRAPHS: A new graph model. Australian Computer Science Communications, 17(1):262--270.
Lai, W. and Eades, P. (1998). Routing drawings in diagram displays [HREF7]. Proceedings of APCHI'98 (3rd Asia Pacific Conference on Computer Human Interaction), Japan, pages 291-296, Japan, IEEE Computer Society Press.
Maarek Y. S. and Shaul, I. Z. B. (1997). WebCutter: A system for dynamic and tailorable site mapping. Proceedings of the Sixth International World Wide Web Conference, pages 713-722.
Misue, K., Eades, P., Lai, W. and Sugiyama, K. (1995). Layout adjustment and the mental map [HREF6]. Journal of Visual Languages and Computing, (6): 183- 210.
Pilgrim, C. and Leung, Y. (1996). Applying bifocal displays to enhance WWW navigation. Proceedings of the Second Australian World Wide Web Conference [HREF5].
Sugiyama, K. and Misue, K. (1991). Visualization of structural information: Automatic drawing of compound digraphs. IEEE Transactions on Systems, Man and Cybernetics, 21(4):876-892.
Wei Lai, Mao Ling Huang, Yanchun Zhang and Mark Toleman, © 1999. The author assigns to Southern Cross University and other educational and non-profit institutions a non-exclusive licence to use this document for personal use and in courses of instruction provided that the article is used in full and this copyright statement is reproduced. The author also grants a non-exclusive licence to Southern Cross University to publish this document in full on the World Wide Web and on CD-ROM and in printed form with the conference papers and for the document to be published on mirrors on the World Wide Web.