B${}_0$-VPG Representation of AT-free Outerplanar Graphs

A $k$-bend path is a non-self-intersecting polyline in the plane made of at most $k+1$ axis-parallel line segments. B${}_k$-VPG is the class of graphs which can be represented as intersection graphs of $k$-bend paths in the same plane. In this paper, we show that all AT-free outerplanar graphs are B${}_0$-VPG, i.e., intersection graphs of horizontal and vertical line segments in the plane. Our proofs are constructive and give a polynomial time B${}_0$-VPG drawing algorithm for the class. Following a long line of improvements, Gonçalves, Isenmann, and Pennarun [SODA 2018] showed that all planar graphs are B${}_1$-VPG. Since there are planar graphs which are not B${}_0$-VPG, characterizing B${}_0$-VPG graphs among planar graphs becomes interesting. Chaplick et al.\ [WG 2012] had shown that it is NP-complete to recognize B${}_k$-VPG graphs within B${}_{k+1}$-VPG. Hence recognizing B${}_0$-VPG graphs within B${}_1$-VPG is NP-complete in general, but the question is open when restricted to planar graphs. There are outerplanar graphs and AT-free planar graphs which are not B${}_0$-VPG. This piqued our interest in AT-free outerplanar graphs.