A grid drawing of a graph maps vertices to the grid Z~d and edges to line segments that avoid grid points representing other vertices. We show that a graph G is q~d-colorable, d, q ≥2, if and only if there is a grid drawing of G in Z~d in which no line segment intersects more than q grid points. This strengthens the result of D. Flores Penaloza and F. J. Zaragoza Martinez. Second, we study grid drawings with a bounded number of columns, introducing some new NP-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D. Flores Penaloza and F. J. Zaragoza Martinez.
展开▼
机译：图形的网格图将顶点映射到网格Z_d，将边缘映射到线段，这些线段避免了代表其他顶点的网格点。我们证明，当且仅当在Z〜d中存在G的网格图（其中线段相交不超过q个网格点）时，图G才是q〜d可着色的，d，q≥2。这加强了D. Flores Penaloza和F. J. Zaragoza Martinez的成绩。其次，我们研究带有有限列数的网格图，并介绍了一些新的NP完全问题。最后，我们证明任何平面图都有一个平面网格图，其中每个线段都恰好包含两个网格点。这个结果证明了D.Flores Penaloza和F.J.Zaragoza Martinez提出的猜想。
展开▼
