B0-VPG Representation of AT-free Outerplanar Graphs

Abstract

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. In fact, we show the existence of a B$_{0}$-VPG representation for a superclass of AT-free graphs namely linear outerplanar graphs which we define as the class of subgraphs of biconnected outerpaths. Outerpaths are outerplanar graphs which admit a planar drawing whose weak dual is a path.
    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.