B_0-VPG Representation of AT-free Outerplanar Graphs
share
B_0-VPG graphs are intersection graphs of axis-parallel line segments in the plane. In this paper, we show that all AT-free outerplanar graphs are B_0-VPG. We first prove that every AT-free outerplanar graph is an induced subgraph of a biconnected outerpath (biconnected outerplanar graphs whose weak dual is a path) and then we design a B_0-VPG drawing procedure for biconnected outerpaths. Our proofs are constructive and give a polynomial time B_0-VPG drawing algorithm for the class. We also characterize all subgraphs of biconnected outerpaths and name this graph class "linear outerplanar". This class is a proper superclass of AT-free outerplanar graphs and a proper subclass of outerplanar graphs with pathwidth at most 2. It turns out that every graph in this class can be realized both as an induced subgraph and as a spanning subgraph of (different) biconnected outerpaths.
READ FULL TEXT