B₀-VPG representation of AT-free outerplanar graphs

DOI10.1007/978-3-030-95018-7_9MaRDI QIDQ6102269zbMATH OpenFDO

Authors Sparsh Jain, Sreejith K. Pallathumadam, Deepak Rajendraprasad

Publication date 8 May 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.08269

zbMATH Keywords

\(\mathrm{B}_0\)-VPGat-freegraph drawinggrid intersection graphouterplanar

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: 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. Following a long line of improvements, Gonc{c}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.

Recommendations

• 1-string \(B_2\)-VPG representation of planar graphs
• 1-string B₂-VPG representation of planar graphs
• Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
• On some special classes of contact \(B_0\)-VPG graphs
• Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• Characterising chordal contact \(B_0\)-VPG graphs
• Planar graphs as VPG-graphs
• Planar graphs as VPG-graphs
• scientific article; zbMATH DE number 841650

Cites work

• 1-string B₂-VPG representation of planar graphs
• A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Bounds on the bend number of split and cocomparability graphs
• Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• scientific article; zbMATH DE number 3547322 (Why is no real title available?)
• scientific article; zbMATH DE number 739017 (Why is no real title available?)
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• Intersection graphs of segments
• Max point-tolerance graphs
• On grid intersection graphs
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs
• Planar graphs as VPG-graphs
• Posets and VPG graphs
• Recognizing some subclasses of vertex intersection graphs of 0-bend paths in a grid
• Recognizing string graphs in NP
• String graphs. II: Recognizing string graphs is NP-hard
• Triangle-Free Planar Graphs and Segment Intersection Graphs
• Vertex Intersection Graphs of Paths on a Grid
• Vertex intersection graphs of paths on a grid: characterization within block graphs
• VPG and EPG bend-numbers of Halin graphs

Cited in

(1)

• B0-VPG Representation of AT-free Outerplanar Graphs

This page was built for publication: \(B_0\)-VPG representation of AT-free outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102269)