Search Results

Documents authored by Verciani, Francesco

Artifact
Software
DOI: 10.4230/artifacts.26092
Venn Diagrams Program(s) and Output

Authors: Sofia Brenner, Torsten Mütze, and Francesco Verciani

Abstract
Cite as

Sofia Brenner, Torsten Mütze, Francesco Verciani. Venn Diagrams Program(s) and Output (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{files,
   title = {{Venn Diagrams Program(s) and Output}}, 
   author = {Brenner, Sofia and M\"{u}tze, Torsten and Verciani, Francesco},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:baf5f66047caf6259cf73873956fbaf9305fa782;origin=https://tmuetze.de/papers/venn.zip;visit=swh:1:snp:53f5d3514da4e885a2381a6754d4576ba22dbae2}{\texttt{swh:1:dir:baf5f66047caf6259cf73873956fbaf9305fa782}} (visited on 2026-05-27)},
   url = {https://tmuetze.de/papers/venn.zip},
   doi = {10.4230/artifacts.26092},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.21
On Minimum Venn Diagrams

Authors: Sofia Brenner, Petr Gregor, Torsten Mütze, and Francesco Verciani

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
An n-Venn diagram is a diagram in the plane consisting of n simple closed curves that intersect only finitely many times such that each of the 2ⁿ possible intersections of their interiors is represented by a single connected region. An n-Venn diagram has at most 2ⁿ-2 crossings, and if this maximum number of crossings is attained, then only two curves intersect in every crossing. To complement this, Bultena and Ruskey considered n-Venn diagrams that minimize the number of crossings, which implies that many curves intersect in every crossing. Specifically, they proved that the total number of crossings in any n-Venn diagram is at least L_n≔⌈(2ⁿ-2)/(n-1)⌉, and if this lower bound is attained, then essentially all n curves intersect in every crossing. Diagrams achieving this bound are called minimum Venn diagrams, and are known only for n ≤ 7. Bultena and Ruskey conjectured that they exist for all n ≥ 8. In this work, we establish an asymptotic version of their conjecture. For n = 8 we construct a diagram with 40 crossings, only 3 more than the lower bound L₈ = 37. Furthermore, for every n of the form n = 2^k for some integer k ≥ 4, we construct an n-Venn diagram with at most (1+33/8n)L_n = (1+o(1))L_n many crossings. Via a doubling trick this also gives (n+m)-Venn diagrams for all 0 ≤ m < n with at most 40⋅ 2^m crossings for n = 8 and at most (1+33/8n) (n+m)/n L_{n+m} = (2+o(1))L_{n+m} many crossings for k ≥ 4. In particular, we obtain n-Venn diagrams with the smallest known number of crossings for all n ≥ 8. Our constructions are based on partitions of the hypercube into isometric paths and cycles, using a result of Ramras.
Cite as

Sofia Brenner, Petr Gregor, Torsten Mütze, and Francesco Verciani. On Minimum Venn Diagrams. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brenner_et_al:LIPIcs.SoCG.2026.21,
  author =	{Brenner, Sofia and Gregor, Petr and M\"{u}tze, Torsten and Verciani, Francesco},
  title =	{{On Minimum Venn Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.21},
  URN =		{urn:nbn:de:0030-drops-258278},
  doi =		{10.4230/LIPIcs.SoCG.2026.21},
  annote =	{Keywords: Venn diagram, crossing, conjecture, hypercube, partition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.22
Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams

Authors: Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
In 1984, Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves. This conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hamilton cycle. In this work, we construct counterexamples to Winkler’s conjecture for all n ≥ 6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n = 6 curves (even their number was not previously known), among which we found 72 counterexamples. We also disprove another conjecture about the Hamiltonicity of the arrangement graph of a Venn diagram. Specifically, while working on Winkler’s conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n ≥ 4.
Cite as

Sofia Brenner, Linda Kleist, Torsten Mütze, Christian Rieck, and Francesco Verciani. Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brenner_et_al:LIPIcs.SoCG.2026.22,
  author =	{Brenner, Sofia and Kleist, Linda and M\"{u}tze, Torsten and Rieck, Christian and Verciani, Francesco},
  title =	{{Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.22},
  URN =		{urn:nbn:de:0030-drops-258285},
  doi =		{10.4230/LIPIcs.SoCG.2026.22},
  annote =	{Keywords: Venn diagram, Winkler’s conjecture, Hamilton cycle, perfect matching, hypercube}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.12
Flipping Odd Matchings in Geometric and Combinatorial Settings

Authors: Oswin Aichholzer, Sofia Brenner, Joseph Dorfer, Hung P. Hoang, Daniel Perz, Christian Rieck, and Francesco Verciani

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We study the problem of reconfiguring odd matchings, that is, matchings that cover all but a single vertex. Our reconfiguration operation is a so-called flip where the unmatched vertex of the first matching gets matched, while consequently another vertex becomes unmatched. We consider two distinct settings: the geometric setting, in which the vertices are points embedded in the plane and all occurring odd matchings are crossing-free, and a combinatorial setting, in which we consider odd matchings in general graphs. For the latter setting, we provide a complete polynomial time checkable characterization of graphs in which any two odd matchings can be reconfigured into each another. This complements the previously known result that the flip graph is always connected in the geometric setting [Oswin Aichholzer et al., 2025]. In the combinatorial setting, we prove that the diameter of the flip graph, if connected, is linear in the number of vertices. Furthermore, we establish that deciding whether there exists a flip sequence of length k transforming one given matching into another is NP-complete in both the combinatorial and the geometric settings. To prove the latter, we introduce a framework that allows us to transform partial order types into general position with only polynomial overhead. Finally, we demonstrate that when parameterized by the flip distance k, the problem is fixed-parameter tractable (FPT) in the geometric setting when restricted to convex point sets.
Cite as

Oswin Aichholzer, Sofia Brenner, Joseph Dorfer, Hung P. Hoang, Daniel Perz, Christian Rieck, and Francesco Verciani. Flipping Odd Matchings in Geometric and Combinatorial Settings. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.12,
  author =	{Aichholzer, Oswin and Brenner, Sofia and Dorfer, Joseph and Hoang, Hung P. and Perz, Daniel and Rieck, Christian and Verciani, Francesco},
  title =	{{Flipping Odd Matchings in Geometric and Combinatorial Settings}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.12},
  URN =		{urn:nbn:de:0030-drops-249983},
  doi =		{10.4230/LIPIcs.GD.2025.12},
  annote =	{Keywords: Odd matchings, reconfiguration, flip graph, geometric, combinatorial, connectivity, NP-hardness, FPT}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.30
Flips in Colorful Triangulations

Authors: Rohan Acharya, Torsten Mütze, and Francesco Verciani

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
The associahedron is the graph G_N that has as nodes all triangulations of a convex N-gon, and an edge between any two triangulations that differ in a flip operation. A flip removes an edge shared by two triangles and replaces it by the other diagonal of the resulting 4-gon. In this paper, we consider a large collection of induced subgraphs of G_N obtained by Ramsey-type colorability properties. Specifically, coloring the points of the N-gon red and blue alternatingly, we consider only colorful triangulations, namely triangulations in which every triangle has points in both colors, i.e., monochromatic triangles are forbidden. The resulting induced subgraph of G_N on colorful triangulations is denoted by F_N. We prove that F_N has a Hamilton cycle for all N ≥ 8, resolving a problem raised by Sagan, i.e., all colorful triangulations on N points can be listed so that any two cyclically consecutive triangulations differ in a flip. In fact, we prove that for an arbitrary fixed coloring pattern of the N points with at least 10 changes of color, the resulting subgraph of G_N on colorful triangulations (for that coloring pattern) admits a Hamilton cycle. We also provide an efficient algorithm for computing a Hamilton path in F_N that runs in time O(1) on average per generated node. This algorithm is based on a new and algorithmic construction of a tree rotation Gray code for listing all n-vertex k-ary trees that runs in time O(k) on average per generated tree.
Cite as

Rohan Acharya, Torsten Mütze, and Francesco Verciani. Flips in Colorful Triangulations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{acharya_et_al:LIPIcs.GD.2024.30,
  author =	{Acharya, Rohan and M\"{u}tze, Torsten and Verciani, Francesco},
  title =	{{Flips in Colorful Triangulations}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.30},
  URN =		{urn:nbn:de:0030-drops-213143},
  doi =		{10.4230/LIPIcs.GD.2024.30},
  annote =	{Keywords: Flip graph, associahedron, triangulation, binary tree, vertex coloring, Hamilton cycle, Gray code}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact