<p>I doubt your features simplify the problem at all, but it's very easy to 6-color a planar graph: find and remove a vertex of minimum degree, color the remaining graph recursively, put back the removed vertex, and give it a color that's different from all of its neighbors.</p>

<p>If you maintain an array indexed by vertex degree, with a list of the vertices with that degree in each array cell, and move the vertices to different lists when a removal causes their degrees to change, then you can find the minimum degree vertex by scanning the array from low to high degrees, and the overall algorithm will be linear time.</p>

<p>This also has the advantage that it automatically and quickly takes care of the completely surrounded regions: they have degree one, so they're dealt with first.</p>

<p>I think the best known time bound for 4-coloring planar graphs is still larger — more specifically, $O(n^2)$ from the work of Robertson, Sanders, and Thomas in the mid-1990s. But there are more complicated methods for 5-coloring planar graphs in linear time; one relevant reference is the paper by Hagerup, Chrobak, and Diks in ICALP 1987, and another is by Frederickson in <a href="http://linkinghub.elsevier.com/retrieve/pii/0020019084900565" rel="nofollow">IPL 1984</a>.</p>

CC BY-SA 2.5
2011-02-22T12:24:11.130Z
Hi David, thanks for your reply.  I'd like to understand the 6-coloring algorithm you describe better, but I'm having trouble finding a write up of it (it must be too trivial to merit it!)  Would you happen to know a reference?
kjo
CC BY-SA 2.5
2011-02-22T16:19:24.940Z
See http://en.wikipedia.org/wiki/Greedy_coloring and particularly the paragraph starting "A commonly used ordering for greedy coloring is to choose a vertex v of minimum degree", the references in that paragraph, and the link to "degeneracy" in that paragraph.
David Eppstein
CC BY-SA 2.5
2011-02-26T16:20:10.573Z
Thanks.  FWIW, the earliest source I was able to find for the algorithm you described is Matula D. W.; Marble, G.; and Isaacson, J. D. "Graph Coloring Algorithms." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.
kjo
CC BY-SA 2.5
2011-02-22T04:21:40.610Z
2011-02-22T04:53:40.777Z
2011-02-22T04:53:40.777Z
David Eppstein
<p>I have a large collection of microscopy images of cell cultures.  Each image consists of $10^{10} \times 10^{10}$ pixels.  These images have been "segmented", meaning that their pixels have been partitioned into disjoint sets (aka regions) corresponding either to the background or to individual cells.  I'm looking for a reasonably efficient algorithm to assign "colors" to these regions so that no two adjacent regions have the same color, and the number of colors used is "small".</p>

<p>In principle, 4 colors should do, but the problem of finding a 4-coloring for a partition of a plane region into disjoint subregions is NP-hard.</p>

<p>Nevertheless, this statement (and the 4-color problem in general) applies to a more general situation (e.g. arbitrarily complex shapes) than the one I am dealing with, so I'm alert to the possibility that some features of this special case may make the problem reasonably tractable in practice.</p>

<p>First, typically most of the cell regions are in fact isolated (i.e. they are surrounded entirely by background), so the problem of assigning a color to them is trivial.  Second, even when there are adjacent cell regions, these regions have relatively "well-behaved" shapes: they are basically roundish blobs, with no weird curlicues, etc.  In fact, any two pixels in a cell region are connected by a <em>taxicab-path</em> consisting of pixels all belonging to the region.  (By <em>taxicab-path</em> I mean one in which the Manhattan distance between adjacent pixels is always 1; i.e. each step along the path is either vertical or horizontal.)  Also, there is some leeway on the exact boundary of these regions, so it may be acceptable to modify the segmentation algorithm in such a way that the resulting regions are more easily colorable.</p>

<p>I have not found any prior work on coloring that attempts to exploit the features described above, so I thought I'd ask here.</p>

<p>It may very well be that these features of my special case do not result in any simplification of the 4-coloring problem, in which case an algorithm that can efficiently produce a 5-coloring, or even a 6-coloring, would be adequate.</p>

<p>Thanks in advance for your suggestions,</p>

<p>kj</p>

<ds.algorithms><graph-algorithms><graph-colouring>
An image coloring problem
kjo
# An image coloring problem

(Asked by: username_0 on 2011-02-22)

I have a large collection of microscopy images of cell cultures. Each image consists of $10^{10} \times 10^{10}$ pixels. These images have been "segmented", meaning that their pixels have been partitioned into disjoint sets (aka regions) corresponding either to the background or to individual cells. I'm looking for a reasonably efficient algorithm to assign "colors" to these regions so that no two adjacent regions have the same color, and the number of colors used is "small".

In principle, 4 colors should do, but the problem of finding a 4-coloring for a partition of a plane region into disjoint subregions is NP-hard.

Nevertheless, this statement (and the 4-color problem in general) applies to a more general situation (e.g. arbitrarily complex shapes) than the one I am dealing with, so I'm alert to the possibility that some features of this special case may make the problem reasonably tractable in practice.

First, typically most of the cell regions are in fact isolated (i.e. they are surrounded entirely by background), so the problem of assigning a color to them is trivial. Second, even when there are adjacent cell regions, these regions have relatively "well-behaved" shapes: they are basically roundish blobs, with no weird curlicues, etc. In fact, any two pixels in a cell region are connected by a *taxicab-path* consisting of pixels all belonging to the region. (By *taxicab-path* I mean one in which the Manhattan distance between adjacent pixels is always 1; i.e. each step along the path is either vertical or horizontal.) Also, there is some leeway on the exact boundary of these regions, so it may be acceptable to modify the segmentation algorithm in such a way that the resulting regions are more easily colorable.

I have not found any prior work on coloring that attempts to exploit the features described above, so I thought I'd ask here.

It may very well be that these features of my special case do not result in any simplification of the 4-coloring problem, in which case an algorithm that can efficiently produce a 5-coloring, or even a 6-coloring, would be adequate.

Thanks in advance for your suggestions,

kj

**Tags:** ds.algorithms, graph-algorithms, graph-colouring


---

## 1 answers

### Answer by username_1 on 2011-02-22. Score: 9 | Accepted answer

I doubt your features simplify the problem at all, but it's very easy to 6-color a planar graph: find and remove a vertex of minimum degree, color the remaining graph recursively, put back the removed vertex, and give it a color that's different from all of its neighbors.

If you maintain an array indexed by vertex degree, with a list of the vertices with that degree in each array cell, and move the vertices to different lists when a removal causes their degrees to change, then you can find the minimum degree vertex by scanning the array from low to high degrees, and the overall algorithm will be linear time.

This also has the advantage that it automatically and quickly takes care of the completely surrounded regions: they have degree one, so they're dealt with first.

I think the best known time bound for 4-coloring planar graphs is still larger — more specifically, $O(n^2)$ from the work of Robertson, Sanders, and Thomas in the mid-1990s. But there are more complicated methods for 5-coloring planar graphs in linear time; one relevant reference is the paper by Hagerup, Chrobak, and Diks in ICALP 1987, and another is by Frederickson in [IPL 1984](http://linkinghub.elsevier.com/retrieve/pii/0020019084900565).

> **Comments:**
> **username_0**: Hi David, thanks for your reply.  I'd like to understand the 6-coloring algorithm you describe better, but I'm having trouble finding a write up of it (it must be too trivial to merit it!)  Would you happen to know a reference?  
> **username_1**: See http://en.wikipedia.org/wiki/Greedy_coloring and particularly the paragraph starting "A commonly used ordering for greedy coloring is to choose a vertex v of minimum degree", the references in that paragraph, and the link to "degeneracy" in that paragraph.  
> **username_0**: Thanks.  FWIW, the earliest source I was able to find for the algorithm you described is Matula D. W.; Marble, G.; and Isaacson, J. D. "Graph Coloring Algorithms." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.  

---

