On Bus Graph Realizability

Simple item page
dc.creatorAda, Anil
dc.creatorCoggan, Melanie
dc.creatorDi Marco, Paul
dc.creatorDoyon, Alain
dc.creatorFlookes, Liam
dc.creatorHeilala, Samuli
dc.creatorKim, Ethan
dc.creatorWing, Jonathan Li On
dc.creatorPreville-Ratelle, Louis-Francois
dc.creatorWhitesides, Sue
dc.creatorYu, Nuo
dc.date2006-09-22
dc.date.accessioned2026-07-07T07:23:56Z
dc.date.available2026-07-07T07:23:56Z
dc.descriptionIn 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.
dc.descriptionTech Report in School of Computer Science, McGill University Poster version of this paper was presented at the International Symposium on Graph Drawing 2006
dc.identifierhttps://arxiv.org/abs/cs/0609127
dc.identifierhttp://arxiv.org/abs/cs/0609127
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116170
dc.subjectComputational Geometry
dc.subjectDiscrete Mathematics
dc.titleOn Bus Graph Realizability
dc.typetext

Files

Collections

arXiv