The unit bar visibility number of a graph

Abstract: A extit{

t

-unit-bar representation} of a graph

G

is an assignment of sets of at most

t

horizontal unit-length segments in the plane to the vertices of

G

so that (1) all of the segments are pairwise nonintersecting, and (2) two vertices

x

and

y

are adjacent if and only if there is a vertical channel of positive width connecting a segment assigned to

x

and a segment assigned to

y

that intersects no other segment. The extit{unit bar visibility number} of a graph

G

, denoted

u b (G)

, is the minimum

t

such that

G

has a

t

-unit-bar visibility representation. Our results include a linear time algorithm that determines

u b (T)

when

T

is a tree, bounds on

u b (K_{m, n})

that determine

u b (K_{m, n})

asymptotically when

n

and

m

are asymptotically equal, and bounds on

u b (K_{n})

that determine

u b (K_{n})

exactly when

n e q u i v 1, 2 p m o d 6

.

Recommendations

Cited in

(11)

This page was built for publication: The unit bar visibility number of a graph