{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:40:09Z","timestamp":1727469609892},"reference-count":0,"publisher":"Journal of Graph Algorithms and Applications","issue":"9","license":[{"start":{"date-parts":[[2023,11,1]],"date-time":"2023-11-01T00:00:00Z","timestamp":1698796800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JGAA"],"abstract":"<jats:p>A $k$-bend path is a non-self-intersecting polyline in the plane made of at most $k+1$ axis-parallel line segments.  \n\tB$_{k}$-VPG is the class of graphs which can be represented as intersection graphs of $k$-bend paths in the same plane.\n\tIn 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.  \nOur proofs are constructive and give a polynomial time B$_{0}$-VPG drawing algorithm for the class.\n\tIn 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. \n\t\tOuterpaths are outerplanar graphs which admit a planar drawing whose weak dual is a path.\n\n\t\u00a0\u00a0\u00a0\u00a0Following a long line of improvements, Gon\u00e7alves, Isenmann, and Pennarun [SODA 2018] showed that all planar graphs are B$_{1}$-VPG. \n\tSince there are planar graphs which are not B$_{0}$-VPG, characterizing B$_{0}$-VPG graphs among planar graphs becomes interesting. \n\tChaplick 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\n\tis open when restricted to planar graphs.\n\tThere are outerplanar graphs and AT-free planar graphs which are not B$_{0}$-VPG. \n\tThis piqued our interest in AT-free outerplanar graphs. <\/jats:p>","DOI":"10.7155\/jgaa.00648","type":"journal-article","created":{"date-parts":[[2023,12,30]],"date-time":"2023-12-30T10:38:39Z","timestamp":1703932719000},"page":"853-869","source":"Crossref","is-referenced-by-count":0,"title":["B0-VPG Representation of AT-free Outerplanar Graphs"],"prefix":"10.7155","volume":"27","author":[{"given":"Sparsh","family":"Jain","sequence":"first","affiliation":[]},{"given":"Sreejith","family":"Pallathumadam","sequence":"additional","affiliation":[]},{"given":"Deepak","family":"Rajendraprasad","sequence":"additional","affiliation":[]}],"member":"4175","published-online":{"date-parts":[[2023,11,1]]},"container-title":["Journal of Graph Algorithms and Applications"],"original-title":[],"link":[{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper648\/2311","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/download\/paper648\/2311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T20:08:30Z","timestamp":1727467710000},"score":1,"resource":{"primary":{"URL":"https:\/\/jgaa.info\/index.php\/jgaa\/article\/view\/paper648"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,1]]},"references-count":0,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2023,11,1]]}},"URL":"https:\/\/doi.org\/10.7155\/jgaa.00648","relation":{},"ISSN":["1526-1719"],"issn-type":[{"type":"electronic","value":"1526-1719"}],"subject":[],"published":{"date-parts":[[2023,11,1]]}}}