Grid Representations and the Chromatic Number

Details Grid Representations and the Chromatic Number Grid Representations and the Chromatic Number

2012-04-01

arxiv.org/abs/1204.0210v1

Mathematics

Combinatorics

22 pages, 8 figures

Scientific paper

A grid drawing of a graph maps vertices to grid points and edges to line segments that avoid grid points representing other vertices. We show that there is a number of grid points that some line segment of an arbitrary grid drawing must intersect. This number is closely connected to the chromatic number. Second, we study how many columns we need to draw a graph in the grid, 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 David Flores-Pe\~naloza and Francisco Javier Zaragoza Martinez.

Affiliated with

Also associated with

No associations

Rating

Grid Representations and the Chromatic Number does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Grid Representations and the Chromatic Number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grid Representations and the Chromatic Number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552469