Bounds on the bend number of split and cocomparability graphs

DOI10.1007/s00224-019-09912-4zbMath1420.05120arXiv1804.06584OpenAlexW2914707557WikidataQ128413152 ScholiaQ128413152MaRDI QIDQ2322713

Dibyayan Chakraborty, Joydeep Mukherjee, Sandip Das, 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

split graphscocomparability graphsstring graphsposet dimensionbend number\(B_k\)-VPG graphs

Mathematics Subject Classification ID

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

Related Items (3)

\(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Dominating sets for split and bipartite graphs
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs requiring exponential representations
• Comparability graphs and intersection graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
• Vertex Intersection Graphs of Paths on a Grid
• String graphs and separators
• Maximum Independent Set on $$B_1$$ B 1 -VPG Graphs
• Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
• 1-String B_2-VPG Representation of Planar Graphs
• Topology of Thin Film RC Circuits
• String graphs and incomparability graphs
• Recognizing string graphs in NP
• Posets and VPG graphs

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