Timeline for Algorithms on graphs of bounded degeneracy/arboricity
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 14, 2010 at 5:03 | comment | added | Rune | By arbitrarily large I just meant that for any given k there exists a planar graph with tree width > k. Of course the tree width can never be more than the number of vertices, so that's always an upper bound on the tree width of a graph. | |
| Jan 11, 2010 at 4:54 | comment | added | Carter Tazio Schonwald | well, then the question is are they related in some way? Also, It'd be more accurate I think to say that planar graphs can have tree width linear in the number of nodes rather than arbitrarily large (or is there a class of graphs that does worse than then NxN grid?) | |
| Jan 11, 2010 at 3:33 | comment | added | Rune | Tree width is actually a different concept. Planar graphs for instance have constant arboricity, but can have arbitrarily large tree width. | |
| Jan 11, 2010 at 2:05 | history | edited | Carter Tazio Schonwald | CC BY-SA 2.5 |
added supplementary remarks
|
| Jan 11, 2010 at 0:29 | history | answered | Carter Tazio Schonwald | CC BY-SA 2.5 |