Realizability of Rectangular Euler Diagrams
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913384555872256 |
|---|---|
| author | Dürrschnabel, Dominik Priss, Uta |
| author_facet | Dürrschnabel, Dominik Priss, Uta |
| contents | Euler diagrams are a tool for the graphical representation of set relations. Due to their simple way of visualizing elements in the sets by geometric containment, they are easily readable by an inexperienced reader. Euler diagrams where the sets are visualized as aligned rectangles are of special interest. In this work, we link the existence of such rectangular Euler diagrams to the order dimension of an associated order relation. For this, we consider Euler diagrams in one and two dimensions. In the one-dimensional case, this correspondence provides us with a polynomial-time algorithm to compute the Euler diagrams, while the two-dimensional case is linked to an NP-complete problem which we approach with an exponential-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_03801 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Realizability of Rectangular Euler Diagrams Dürrschnabel, Dominik Priss, Uta Computational Geometry Combinatorics 06A07, 68R05 G.2.1; I.2.4; F.2.2 Euler diagrams are a tool for the graphical representation of set relations. Due to their simple way of visualizing elements in the sets by geometric containment, they are easily readable by an inexperienced reader. Euler diagrams where the sets are visualized as aligned rectangles are of special interest. In this work, we link the existence of such rectangular Euler diagrams to the order dimension of an associated order relation. For this, we consider Euler diagrams in one and two dimensions. In the one-dimensional case, this correspondence provides us with a polynomial-time algorithm to compute the Euler diagrams, while the two-dimensional case is linked to an NP-complete problem which we approach with an exponential-time algorithm. |
| title | Realizability of Rectangular Euler Diagrams |
| topic | Computational Geometry Combinatorics 06A07, 68R05 G.2.1; I.2.4; F.2.2 |
| url | https://arxiv.org/abs/2403.03801 |