Navigating posets with few maps and representing graphs with convex polygons
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.