Name
Abstract | ||
|---|---|---|
We consider the following graph embedding problem: Given a bipartite graph G = (V1,V2;E), where the max- imum 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 ver- tex 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, as well as related problems. |
Year | Venue | Keywords |
|---|---|---|
2006 | canadian conference on computational geometry | bipartite graph,graph embedding |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Line graph,Loop (graph theory),Bound graph,Vertex (graph theory),Bipartite graph,Cycle graph,Neighbourhood (graph theory),Degree (graph theory),Mathematics | Journal | abs/cs/0609127 |
Citations | PageRank | References |
1 | 0.36 | 10 |
Authors | ||
11 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anil Ada | 1 | 47 | 3.88 |
| Melanie Coggan | 2 | 1 | 0.69 |
| Paul Di Marco | 3 | 1 | 0.69 |
| Alain Doyon | 4 | 20 | 1.89 |
| Liam Flookes | 5 | 1 | 0.69 |
| Samuli Heilala | 6 | 2 | 1.05 |
| ethan dh kim | 7 | 1 | 0.36 |
| Jonathan Li On Wing | 8 | 1 | 0.69 |
| Louis-francois Preville-ratelle | 9 | 1 | 0.69 |
| Sue Whitesides | 10 | 1449 | 197.63 |
| Nuo Yu | 11 | 1 | 1.03 |