Talk:Intersection graph

See also containment order

user:David Eppstein found this pointer to be of "marginal relevance" and deleted it. I restored it because I disagree strongly. The concepts are (at least very nearly) dual. Just as every simple undirected graph has an intersection representation that labels each vertex with the set of edges incident on it, so every poset has a containment representation that labels each element with the set of comparabilities of which it is the second element. And just as intersection is one of the fundamental operations on sets, so containment is one of the fundamental relations on sets. Seems pretty relevant to me! David, do you still disagree?—PaulTanenbaum 03:24, 10 September 2007 (UTC)[reply]

What you say makes some sense. I think it would be helpful if this were explained in a sentence in the text, rather than just a link in a "see also" section, though. And is intersection graph really the right dual for a containment relation? I'd think the complement of a comparability graph would be closer. —David Eppstein 03:34, 10 September 2007 (UTC)[reply]

I'll work up some text to include in the body as you suggest. Don't see your suggestion about cocomparability graphs, though (not that I'm prepared to assert unequivocally any duality either!). PaulTanenbaum 03:41, 10 September 2007 (UTC)[reply]

Intersection (Line) Graphs of hypergraphs

The article Intersection (Line) Graphs of hypergraphs has some valuable examples and results and should be merged into this article. Zaslav (talk) 06:49, 3 April 2008 (UTC)[reply]

This artcle is confusing totally; It may be deleted or linked to somewhere. It lists various definitions - that's it without any meanings or understandings. I do not know why we have such articles on wikipedia.

--Tangi-tamma (talk) 10:53, 3 April 2008 (UTC)[reply]

I don't think your objection is entirely fair. However, I do agree this article needs improvement, e.g., with good examples. That's a reason to put the material on uniform hypergraphs from "Intersection (Line) Graphs of hypergraphs" in here. The name "Intersection graph" is simplest, most general, and most common (according to my observations), so I recommend that as the combined article name.

Please see my detailed discussion of this issue at Talk:Intersection (Line) Graphs of hypergraphs. Thank you for the comments. Zaslav (talk) 19:39, 3 April 2008 (UTC)[reply]

Read my reply on your talk page. Thanks. Let us keep all dialogues on your talk page - you take the credit.

---Tangi-tamma (talk) 21:56, 3 April 2008 (UTC)[reply]

When someone sets flag, please donot delete without asking. This artilcle does not meet the requirements and technically incorrect. Also it is too difficult for a layman to understand. It needs additional work.

--Tangi-tamma (talk) 01:34, 4 April 2008 (UTC)[reply]

Complete in which complexity class?

"However, intersection graphs of line segments may be nonplanar as well, and recognizing intersection graphs of line segments is complete for the existential theory of the reals (Schaefer 2010)." Maybe NP-complete? 46.5.2.53 (talk) 09:23, 26 October 2018 (UTC)[reply]