Euler diagram decomposition

Andrew Fish, Jean Flower

Research output: Chapter in Book/Conference proceeding with ISSN or ISBNConference contribution with ISSN or ISBN

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 5th International Conference on the Theory and Application of Diagrams
Place of PublicationBerlin Heidelberg
PublisherSpringer-Verlag
Pages28-44
Number of pages17
Volume5223
ISBN (Electronic)9783540877301
ISBN (Print)9783540877295
DOIs
Publication statusPublished - 1 Jan 2008
EventProceedings of the 5th international conference on the theory and application of diagrams - Herrsching, Germany, 19-21 September, 2008
Duration: 1 Jan 2008 → …

Publication series

NameLecture Notes in Computer Science

Conference

ConferenceProceedings of the 5th international conference on the theory and application of diagrams
Period1/01/08 → …

Fingerprint Dive into the research topics of 'Euler diagram decomposition'. Together they form a unique fingerprint.

  • Cite this

    Fish, A., & Flower, J. (2008). Euler diagram decomposition. In Proceedings of the 5th International Conference on the Theory and Application of Diagrams (Vol. 5223, pp. 28-44). (Lecture Notes in Computer Science). Springer-Verlag. https://doi.org/10.1007/978-3-540-87730-1_7