Posets and VPG Graphs |
| |
| Authors: | Elad Cohen Martin Charles Golumbic William T. Trotter Ruidong Wang |
| |
| Affiliation: | 1.Caesarea Rothschild Institute and Department of Computer Science,University of Haifa,Haifa,Israel;2.School of Mathematics,Georgia Institute of Technology,Atlanta,U.S.A. |
| |
| Abstract: | We investigate the class of intersection graphs of paths on a grid (VPG graphs), and specifically the relationship between the bending number of a cocomparability graph and the poset dimension of its complement. We show that the bending number of a cocomparability graph G is at most the poset dimension of the complement of G minus one. Then, via Ramsey type arguments, we show our upper bound is best possible. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
