00:00:00 / 00:00:00

Navigating posets with few maps and representing graphs with convex polygons

By Alexander Wolff

Appears in collection : Geometry & Computing / Géométrie & Informatique

The first part of my talk will be about a recent trend in graph drawing. We aim to visualize a complex combinatorial or geometric object (say, a graph) by means of a collection of drawings, each of which includes all parts (say, edges), but highlights only a subset of them. (For example, Hliněný and Masařík [GD 2023] introduced the notion of an \emph{uncrossed collection} of a graph, that is, a collection of straight-line drawings of the graph such that every edge of the graph is uncrossed in at least one drawing in the collection.) In our case, we represent a given poset by a collection of planar \emph{maps} such that, for every element x of the poset, there is a map that maps x to a point in 2D that dominates exactly the points that correspond to the successors of x in the poset. Such a collection is called an atlas, and the number of maps is the thickness of the atlas. We relate the atlas thickness of a poset to its width and dimension, and show that the atlas thickness it is NP-hard to compute. The second part of my talk will be about contact representations of graphs using convex polygons in 3D. In particular, we show that (i) every graph admits such a representation and (ii) every (sub)cubic graph admits such a representation in cubic space.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.20539503
  • Cite this video Wolff, Alexander (08/10/2026). Navigating posets with few maps and representing graphs with convex polygons. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20539503
  • URL https://dx.doi.org/10.24350/CIRM.V.20539503

Bibliography

  • EVANS, William, RZĄŻEWSKI, Paweł, SAEEDI, Noushin, SHIN, Chan-Su, WOLFF, Alexander. Representing graphs and hypergraphs by touching polygons in 3D. In : International Symposium on Graph Drawing and Network Visualization. Cham : Springer International Publishing, 2019. p. 18-32. - https://doi.org/10.1007/978-3-030-35802-0_2
  • FELSNER, Stefan, HODOR, Jędrzej, ORTALI, Giacomo,WOLFF, Alexander. Navigating Posets with Few Maps. arXiv preprint arXiv:2605.20877, 2026. - https://doi.org/10.48550/arXiv.2605.20877

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Subscribe illustration
Give feedback