Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00648
B0VPG Representation of ATfree Outerplanar Graphs
Vol. 27, no. 9, pp. 853869, 2023. Regular paper.
Abstract A $k$bend path is a nonselfintersecting polyline in the plane made of at most $k+1$ axisparallel 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 ATfree 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 ATfree 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 NPcomplete to recognize B$_{k}$VPG graphs within B$_{k+1}$VPG. Hence recognizing B$_{0}$VPG graphs within B$_{1}$VPG is NPcomplete in general, but the question is open when restricted to planar graphs. There are outerplanar graphs and ATfree planar graphs which are not B$_{0}$VPG. This piqued our interest in ATfree outerplanar graphs.
This work is licensed under the terms of the CCBY license.

Submitted: January 2023.
Reviewed: November 2023.
Revised: November 2023.
Accepted: December 2023.
Final: December 2023.
Published: December 2023.
Communicated by
William S. Evans

Journal Supporters
