-
-
Save Hermann-SW/123604aaec92bb856112ef2cd2a4585a to your computer and use it in GitHub Desktop.
14 vertices, 31 edges planar graph that makes Boost sequential_vertex_coloring() use 7 colors
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| LEDA.GRAPH | |
| int | |
| int | |
| 14 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 0 | |
| 31 | |
| 1 2 0 | |
| 1 3 0 | |
| 1 4 0 | |
| 1 9 0 | |
| 1 10 0 | |
| 1 14 0 | |
| 2 3 0 | |
| 2 4 0 | |
| 2 9 0 | |
| 3 4 0 | |
| 3 10 0 | |
| 5 6 0 | |
| 5 7 0 | |
| 5 8 0 | |
| 6 7 0 | |
| 6 8 0 | |
| 6 10 0 | |
| 7 8 0 | |
| 7 9 0 | |
| 7 10 0 | |
| 8 9 0 | |
| 8 10 0 | |
| 8 14 0 | |
| 9 10 0 | |
| 9 14 0 | |
| 10 14 0 | |
| 11 12 0 | |
| 11 13 0 | |
| 12 13 0 | |
| 12 14 0 | |
| 13 14 0 |
That is nice, while I handcrafted 7c.u to enforce 7 colors to be used by Boost sequential_vertex_coloring(), adding 5 more edges (the dotted edges in above detail link, to make it maximal planar) …
$ diff 7c.u 7c.mp.u
19c19
< 31
---
> 36
50a51,55
> 1 13 1
> 11 1 1
> 11 9 1
> 11 14 1
> 3 9 1
$
… still forces sequential_vertex_coloring() to use 7 colors for (vertex) coloring of 7c.mp.u:
$ ./seqcol 7c.mp.u
7
0 1 2 3 0 1 2 3 4 5 1 0 2 6
I used that graph as example for (Qt5 and Qt6) draw_planar:
https://github.com/Hermann-SW/random_maximal_planar_embedding/tree/main/boost/cgal#build
$ ./draw_planar ../7c.mp.off
Using OpenGL context 4.6 GL
Patched view with vertex numbers for comparison:
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Details:
https://gist.github.com/Hermann-SW/5e74ee13fbf1d0103061e95d8a67c2f7?permalink_comment_id=5138133#gistcomment-5138133