Talk:Cactus graph
Add topic | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Forbidden minor
[edit]I see the claim about the forbidden minors of cactuses was tagged and then untagged as needing a cite today, and I agree that it probably does, but I'm having a hard time tracking it down. It's easy to prove using open ear decomposition of biconnected graphs: each biconnected graph can be formed by starting from a cycle and then repeatedly add paths that start and end at different previously added vertices (I can source this but it would take a little time to track down), the cycle and the first path form a theta (obvious), and contracting any theta produces a diamond (also obvious). But that's too much a synthesis to be adequate as a source here. I did find a closely related statement in Brandstädt, Le, and Spinrad, Graph Classes: A Survey, bottom of p.169: "Cactus graphs are outerplanar since they cannot contain K4 or K2,3 as a minor." But BLS don't state the actual forbidden minor characterization. Will keep looking. —David Eppstein 21:53, 3 October 2007 (UTC)
- Found one! Will add to the article. —David Eppstein 23:32, 3 October 2007 (UTC)
Minimum cuts
[edit]It seems that cactuses are useful to represent the minimum cuts of a graph: http://people.csail.mit.edu/debmalya/papers/soda09-cactus.pdf, http://dx.doi.org/10.1006/jagm.1999.1039 The second paper says "In 1976, Dinits, Karzanov, and Lomonosov published a description of a very simple data structure called a cactus that represents all minimum cuts of a weighted, undirected graph in linear space." Is it worth mentioning ? —Preceding unsigned comment added by 130.192.50.83 (talk) 14:52, 23 April 2009 (UTC)
- Yes, probably in the "algorithms and applications" section. —David Eppstein (talk) 15:21, 23 April 2009 (UTC)
Comment on terminology
[edit]I have moved the following comment by 76.199.11.9 from the article to the talk page, as referring in the article to the article's history is not adequate:
- (Note: an earlier version of this page used the term "cactus graph" instead of "cactus". Just as graph theory studies "trees" rather than "tree graphs", also it is correct to say "cactus" and "cacti" rather than "cactus graph" and "cactus graphs".)
Feel free to include discussion about terminology in the article again if appropriate. Hermel (talk) 19:50, 28 July 2010 (UTC)