TY - GEN

T1 - Euler diagram decomposition

AU - Fish, Andrew

AU - Flower, Jean

PY - 2008/1/1

Y1 - 2008/1/1

N2 - Euler diagrams are a common visual representation of set-theoretic statements, and they have been used for visualising the results of database search queries or as the basis of diagrammatic logical constraint languages for use in software specification. Such applications rely upon the ability to automatically generate diagrams from an abstract description. However, this problem is difficult and is known to be NP-complete under certain wellformedness conditions. Therefore methods to identify when and how one can decompose abstract Euler diagrams into simpler components provide a vital step in improving the efficiency of tools which implement a generation process. One such decomposition, called diagram nesting, has previously been identified and exploited. In this paper, we make substantial progress, defining the notion of a disconnecting contour and identifying the conditions on an abstract Euler diagram that allow us to identify disconnecting contours. If a diagram has a disconnecting contour, we can draw it more easily, by combining the results of drawing smaller diagrams. The drawing problem is just one context which benefits from such diagram decomposition - we can also use the disconnecting contour to provide a more natural semantic interpretation of the Euler diagram.

AB - Euler diagrams are a common visual representation of set-theoretic statements, and they have been used for visualising the results of database search queries or as the basis of diagrammatic logical constraint languages for use in software specification. Such applications rely upon the ability to automatically generate diagrams from an abstract description. However, this problem is difficult and is known to be NP-complete under certain wellformedness conditions. Therefore methods to identify when and how one can decompose abstract Euler diagrams into simpler components provide a vital step in improving the efficiency of tools which implement a generation process. One such decomposition, called diagram nesting, has previously been identified and exploited. In this paper, we make substantial progress, defining the notion of a disconnecting contour and identifying the conditions on an abstract Euler diagram that allow us to identify disconnecting contours. If a diagram has a disconnecting contour, we can draw it more easily, by combining the results of drawing smaller diagrams. The drawing problem is just one context which benefits from such diagram decomposition - we can also use the disconnecting contour to provide a more natural semantic interpretation of the Euler diagram.

U2 - 10.1007/978-3-540-87730-1_7

DO - 10.1007/978-3-540-87730-1_7

M3 - Conference contribution with ISSN or ISBN

SN - 9783540877295

VL - 5223

T3 - Lecture Notes in Computer Science

SP - 28

EP - 44

BT - Proceedings of the 5th International Conference on the Theory and Application of Diagrams

PB - Springer-Verlag

CY - Berlin Heidelberg

T2 - Proceedings of the 5th international conference on the theory and application of diagrams

Y2 - 1 January 2008

ER -