Asymptotically Optimal Thickness Bounds of Generalized Bar Visibility Graphs
Date Issued
2009
Date
2009
Author(s)
Sung, Yen-Peng
Abstract
Given a set of disjoint horizontal line segments (call bars), d(b1, b2) of two bars b1 and b2 is the minimum number of the other bars that the vertical line segments whose endpoints are at b1 and b2 passing through. A graph G is a bar k-visibility graph if G can be represented as a set of disjoint bars such that any two vertices are adjacent in G if and only if d(u, v) ≤ k, where u and v are the associated bars with those vertices. A graph G is a semi bar k-visibility graph if G can be represented as a set of disjoint bars whose left endpoints have the same x-coordinates such that any two vertices are adjacent in G if and only if d(u, v) ≤ k, where u and v are the associated bars with those vertices. The thickness of G is the minimum number of planar subgraphs whose union is G. Dean et al. gave the best previously known upper bound 3k(6k + 1) on the thickness of bar k-visibility graphs. Hartke et al. proved that the largest completeraph in bar k-visibility graphs is K_4k+4, so the upper bound on the thickness of bar kvisibility graphs is at least ⌈(2k +3)/3⌉. Felsner and Massow gave an upper bound onhe thickness of semi bar 1-visibility graphs. Felsner and Massow proved that K_2k+3 is the largest complete graph in semi bar k visibility graphs, so the upper bound on thehickness of semi bar k visibility graphs is at least ⌈(2k + 5)/6⌉. We reduce the upper bound to 3k + 3 on the thickness of bar k-visibility graphs, and give an upper bound 2k for semi bar k-visibility graphs.
Subjects
bar visibility graphs
thickness
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922055-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):3757b13cb7cd43a09b022234fa11dd14