On Bus Graph Realizability
<|reference_start|>On Bus Graph Realizability: 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.<|reference_end|>
@article{ada2006on,
    title={On Bus Graph Realizability},
    author={Anil Ada, Melanie Coggan, Paul Di Marco, Alain Doyon, Liam Flookes,
  Samuli Heilala, Ethan Kim, Jonathan Li On Wing, Louis-Francois
  Preville-Ratelle, Sue Whitesides, and Nuo Yu},
    journal={arXiv preprint arXiv:cs/0609127},
    year={2006},
    number={SOCS-TR-2006.1},
    archivePrefix={arXiv},
    eprint={cs/0609127},
    primaryClass={cs.CG cs.DM}
}