Grid Drawings and the Chromatic Number

Balko, Martin (2013) Grid Drawings and the Chromatic Number. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 315-326 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_28).

Full text not available from this repository.

Abstract

A grid drawing of a graph maps vertices to the grid $ℤ^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 $ℤ^d$ in which no line segment intersects more than q grid points. This strengthens the result of D. Flores Pen̋aloza 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 Pen̋aloza and F. J. Zaragoza Martinez.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_28
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.720 Straight-line
ID Code:1320

Repository Staff Only: item control page

References

Balko, M.: Grid representations and the chromatic number. In: 28th European Workshop on Computational Geometry, EuroCG 2012, pp. 45–48 (2012)

Cáceres, J., Cortés, C., Grima, C.I., Hachimori, M., Márquez, A., Mukae, R., Nakamoto, A., Negami, S., Robles, R., Valenzuela, J.: Compact Grid Representation of Graphs. In: Márquez, A., Ramos, P., Urrutia, J. (eds.) EGC 2011. LNCS, vol. 7579, pp. 166–174. Springer, Heidelberg (2012)

Chappell, G.G., Gimbel, J., Hartman, C.: Thresholds for path colorings of planar graphs. Topics in Discrete Mathematics, 435–454 (2006)

Chrobak, M., Nakano, S.: Minimum-width grid drawings of plane graphs. Computational Geometry 11, 29–54 (1995)

Flores Pen̋aloza, D., Zaragoza Martinez, F.J.: Every four-colorable graph is isomorphic to a subgraph of the visibility graph of the integer lattice. In: Proceedings of the 21st Canadian Conference on Computational Geometry, CCCG 2009, pp. 91–94 (2009)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Goddard, W.: Acyclic colorings of planar graphs. Discrete Math. 91, 91–94 (1991)

Kára, J., Pór, A., Wood, D.R.: On the chromatic number of the visibility graph of a set of points in the plane. Discrete Comput. Geom. 34, 497–506 (2005)

Lovász, L.: On decomposition of graphs. Studia Math. Hung. 1, 237–238 (1966)

Pór, A., Wood, D.R.: No-three-in-line-in-3d. Algorithmica 47, 481–488 (2007)

Schnyder, W.: Embedding planar graphs on the grid. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990, pp. 138–148. Society for Industrial and Applied Mathematics (1990)