Bounds on the bend number of split and cocomparability graphs

DOI10.1007/S00224-019-09912-4MaRDI QIDQ2322713zbMATH OpenOpenAlexWikidataFDO

Authors Dibyayan Chakraborty, Sandip Das, Joydeep Mukherjee, Uma kant Sahoo

Publication date 5 September 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

\(B_k\)-VPG graphsbend numbercocomparability graphsposet dimensionsplit graphsstring graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics of partially ordered sets (06A07) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A path is a simple, piecewise linear curve made up of alternating horizontal and vertical line segments in the plane. A $k$-bend path is a path made up of at most $k+1$ line segments. A $B_k$-VPG representation of a graph is a collection of $k$-bend paths such that each path in the collection represents a vertex of the graph and two such paths intersect if and only if the vertices they represent are adjacent in the graph. The graphs that have a $B_k$-VPG representation are called $B_k$-VPG graphs. It is known that the poset dimension $dim(G)$ of a cocomparability graph $G$ is greater than or equal to its bend number $bend(G)$. Cohen et al. ({ extsc{order 2015}}) asked for examples of cocomparability graphs with low bend number and high poset dimension. We answer this question by proving that for each $m,tinmathbbN$, there exists a cocomparability graph $G_{t,m}$ with $t<bend(G_{t,m})leq4t+29$ and $dim(G_{t,m})-bend(G_{t,m})>m$. Techniques used to prove the above result, allows us to partially address the open question posed by Chaplick et al. ({ extsc{wg 2012}}) who asked whether $B_k$-VPG-chordal $subsetneq$ $B_{k+1}$-VPG-chordal for all $kinmathbbN$. We address this by proving that there are infinitely many $minmathbbN$ such that $B_m$-VPG-split $subsetneq$ $B_{m+1}$-VPG-split which provides infinitely many positive examples. We use the same techniques to prove that, for all $tinmathbbN$, $B_t$-VPG-$Forb(C_{geq5})$ $subsetneq$ $B_{4t+29}$-VPG-$Forb(C_{geq5})$, where $Forb(C_{geq5})$ denotes the family of graphs that does not contain induced cycles of length greater than 4. Furthermore, we show that for all $tinmathbbN$, $P{B}_t$-VPG-split $subsetneqP{B}_{36t+80}$-VPG-split, where $P{B}_t$-VPG denotes the class of graphs with proper bend number at most $t$.

Recommendations

• Posets and VPG graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• On \(k\)-bend and monotonic \(\ell\)-bend edge intersection graphs of paths on a grid
• VPG and EPG bend-numbers of Halin graphs
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs

Cites work

• 1-string \(B_2\)-VPG representation of planar graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• Comparability graphs and intersection graphs
• Dominating sets for split and bipartite graphs
• scientific article; zbMATH DE number 6850320 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Maximum independent set on \(B_1\)-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 and incomparability graphs
• String graphs and separators
• String graphs requiring exponential representations
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs. II: Recognizing string graphs is NP-hard
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topology of Thin Film RC Circuits
• Vertex Intersection Graphs of Paths on a Grid

Cited in

(6)

• Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
• Posets and VPG graphs
• \(B_0\)-VPG representation of AT-free outerplanar graphs
• The bend number of cocomparability graphs

This page was built for publication: Bounds on the bend number of split and cocomparability graphs

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