CanaDAM 2021
On-line, May 25 - 28, 2021

Combinatorics on Posets - Part II
Org: Tom Trotter (Georgia Institute of Technology)

ŁUKASZ BOŻYK, University of Warsaw
Vertex deletion into bipartite permutation graphs  [PDF]

A bipartite permutation graph is a comparability graph of a height-$2$ $2$-dimensional poset. We study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given $n$-vertex graph, whether we can remove at most $k$ vertices to obtain a bipartite permutation graph. We analyze the structure of the so-called almost bipartite permutation graphs which may contain large induced cycles and exploit the structural properties of the shortest hole in such graphs. We use it to obtain an algorithm with running time $O(9^k \cdot n^9)$.

Joint work with Jan Derbisz, Tomasz Krawczyk, Jana Novotná, and Karolina Okrasa.

MICHAŁ SEWERYN, Jagellonian University
Dimension of posets with k-outerplanar cover graphs.  [PDF]

A $k$-outerplanar graph is a planar graph which admits an embedding on the plane such that after a $k$-fold removal of vertices from the exterior face, no vertices of the graph are left. We show that posets with $k$-outerplanar cover graphs have dimension $O(k^3)$. As a consequence, we show that posets of height $h$ with planar cover graphs have dimension $O(h^3)$. This improves the best currently known $O(h^6)$ bound by Kozik, Micek and Trotter. This is joint work with Maximilian Gorsky.

TORSTEN UECKERDT, Karlsruhe Institute of Technology
The queue number of posets  [PDF]

The queue number of a poset is the minimum $k$ such that there exists a linear extension for which no $k+1$ cover relations $a_ib_i$ appear as $a_1 < \cdots < a_{k+1} < b_{k+1} < \cdots < b_1$ in the linear extension. In 1997, Heath and Pemmaraju conjectured that the queue number of a poset is at most its width. This was recently disproven by a construction of posets of width $w$ and queue number $w+1$. We construct posets of width $w$ and queue number $\Omega(w^2)$, and discuss several related results and research directions.

MARCIN WITKOWSKI, Adam Mickiewicz University
Adjacency posets of outerplanar graphs  [PDF]

Felsner, Li and Trotter [1] showed that the dimension of the adjacency poset of an outerplanar graph is at most 5, and gave an example of an outerplanar graph whose adjacency poset has dimension 4. In the talk, we present proof that adjacency posets of outerplanar graphs have dimension at most 4.

[1] S.Felsner, Ch.M.Li, W.T.Trotter, ”Adjacency Posets of Planar Graphs”, Discrete Mathematics, Volume 310, (2010), pp 1097-1104

[2] M. Witkowski, "Adjacency posets of outerplanar graphs", Discrete Mathematics, Volume 344, (2021), pp 112338