Adding a new dimension to the upward drawing

Abstract

In this thesis, we principally investigated the visualization of data that can be represented by an ordered set by means of its upward drawing (Hasse Diagrams). Difficulties are such that "Upward Planarity Testing" is NP-complete [GT95] and "Upward Crossing Minimization" is NP-Hard [Lin94]. Also, the "drawing area" requirement of upward planar directed graphs using straight-line edges on a grid has an exponential lower bound [DTT92]. We present a new approach of drawing Ordered Sets which is a modified version of Hasse Diagrams. The new restriction is that all existing edges are only directed from "Bottom to Top" (upward) and from "Left to Right" (LR). This new dimension is motivated by the rise of a flow of comparability between elements and thus produces readability improvement. The idea is achieved by using special types of decompositions of the ordered set P that will serve as the underlying structure for the drawing. We propose an O( n * width(P)) algorithm which satisfies this new requirement. Furthermore, this new idea is studied for the subclass of N-free ordered sets. We present some techniques of improving the readability by locally reducing crossings around some component of the drawing. We also present a polynomial algorithm which brings an enhancement of the overall picture. The resulting rectangle used has an O(n 2) area. Additionally, to have an approximation of the general ordered set drawing, we present a space-efficient algorithm to convert any ordered set into N-Free.