On Bus Graph Realizability

Details On Bus Graph Realizability On Bus Graph Realizability

2006-09-22

arxiv.org/abs/cs/0609127v1

Computer Science

Computational Geometry

Tech Report in School of Computer Science, McGill University Poster version of this paper was presented at the International S

Scientific paper

In this paper, we consider the following graph embedding problem: Given a bipartite graph G = (V1; V2;E), where the maximum degree of vertices in V2 is 4, can G be embedded on a two dimensional grid such that each vertex in V1 is drawn as a line segment along a grid line, each vertex in V2 is drawn as a point at a grid point, and each edge e = (u; v) for some u 2 V1 and v 2 V2 is drawn as a line segment connecting u and v, perpendicular to the line segment for u? We show that this problem is NP-complete, and sketch how our proof techniques can be used to show the hardness of several other related problems.

Affiliated with

Also associated with

No associations

Rating

On Bus Graph Realizability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Bus Graph Realizability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Bus Graph Realizability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-129836