B0-VPG Representation of AT-free Outerplanar Graphs

Sparsh Jain   ; Sreejith Pallathumadam   ; Deepak Rajendraprasad

Journal of graph algorithms and applications, Tome 27 (2023) no. 9, pp. 853-869

Résumé

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.

Détail

DOI : 10.7155/jgaa.00648

Keywords: Outerplanar graphs, AT-free, B0-VPG, Connectivity augmentation, Outerpath, Linear outerplanar graph, Graph drawing