B0-VPG Representation of AT-free Outerplanar Graphs - Jain, Sparsh; Pallathumadam, Sreejith; Rajendraprasad, Deepak (Journal of Graph Algorithms and Applications, 2023)
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.