<p>If I would like to know something about intersection models, the first reference I would check is the "Topics in Intersection Graph Theory" by McKee and McMorris.  Theorem 1.5 answers your (combinatorial) question.</p>

CC BY-SA 3.0
2014-04-12T05:10:11.437Z
Thanks; as you can expect I don't have access to this book so may I ask what is the exact result? After all this site is about the free exchange of scientific information :)
NisaiVloot
CC BY-SA 3.0
2014-06-12T20:38:07.303Z
Thm 1.5 of the book states that a if graph class is a nicely-behaved hereditary class, then it is an intersection class. And it goes on to say: "While [thm 1.5] can be used to show that a particular set of graphs is an intersection class, that is a long way from actually finding a suitable [representation] and proving that it works." So I don't think this necessarily answers the question here. Theorem 1.1 also states "Every graph is an intersection graph." The interesting open question on weakly chordal graphs is whether there is a nice/geometric intersection model for them (and to find it)
JimN
CC BY-SA 3.0
2014-04-12T04:34:55.303Z
2014-04-12T04:34:55.303Z
Yixin Cao
<p>Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :)</p>

<p>Among the many known classes of perfect graphs, there are three classes that I find especially interesting:</p>

<p>(1) the weakly chordal graphs, whose obstruction set is $\{C_n,\bar{C_n} : n \geq 5\}$,</p>

<p>(2) the chordal graphs, whose obstruction set is $\{C_n : n \geq 4\}$,</p>

<p>(3) the strongly chordal graphs, whose obstruction set is $\{C_n : n \geq 4\} \cup \{S_n : n \geq 3\}$.</p>

<p>Here, $C_n$ denotes the $n$-cycle, and $S_n$ denotes the $n$-sun (obtained by starting from a cycle $x_1 ... x_n$ and adding the edges $x_i y_i x_{i+1}$ for $1 \leq i \leq n$).</p>

<p>These classes admit polynomial algorithms for clique/independent set, the most general one being for the class of weakly chordal graphs and uses a clever 'two-pair contraction' argument (see 'Optimizing weakly triangulated graphs' by R. Hayward, C.T. Hoang and F. Maffray).</p>

<p>Intersection models are known for classes (2) and (3) as they correspond to the clique graphs of acyclic, resp. totally balanced, hypergraphs. Are there any known results about intersection models for weakly chordal graphs?</p>

<p>As a side note, there is a recursive construction of totally balanced hypergraphs due to Lehel (see 'A characterization of totally balanced matrices'), and I was also wondering about possible algorithmic applications of this result?</p>

CC BY-SA 3.0
2014-04-11T22:24:56.650Z
Does this answer your question: http://www.sciencedirect.com/science/article/pii/S0166218X08005349? It was an obvious Google search away.
Sasho Nikolov
CC BY-SA 3.0
2014-04-11T22:27:55.007Z
Besides throwing in a couple of side remarks about algorithms, this is still a math question. I asked you this once but your answer made little sense: is there a reason you are posting your questions here, where you don't get answers and they are not popular, rather than in Math@SE or in Mathoverflow where they would fit better? It makes no sense to me? And are effectively "spamming" the site.
Sasho Nikolov
CC BY-SA 3.0
2014-04-11T23:00:08.727Z
I agree with @SashoNikolov. While I'm loathe to send math questions away (CS is math too!), your questions have little connection to anything in TCS, and it doesn't appear that you wish to make the effort to tie them in. In that case, [math.SE] or [mathoverflow.SE] makes a lot more sense.
Suresh Venkat
CC BY-SA 3.0
2014-04-11T23:04:29.183Z
@SashoNikolov: I didn't read the paper, but judging from the abstract it doesn't answer my question as it only considers a proper subclass of the weakly chordal graphs. Therefore, I assume that the question is still open.
NisaiVloot
CC BY-SA 3.0
2014-04-11T23:10:26.657Z
@SureshVenkat: well, from an European perspective my questions belong to theoretical computer science in a broad sense - and the more math-oriented questions still have some constructive/algorithmic aspects that make them suited to this site, I think. Then again I can understand that people from 'Theory A' are more interested in things like TOC/CC/AGT and the like, but this shouldn't be a reason for peer exclusion I presume?
NisaiVloot
CC BY-SA 3.0
2014-04-11T23:41:31.780Z
They can of course: but it's the poster's job to make the connections explicit. that's all we're asking.
Suresh Venkat
CC BY-SA 3.0
2014-04-12T01:06:55.597Z
I doubt the truth of your statement above. While algebra or logic may be more relevant to theory B, a non-computational question about these will not be theory B in general. Unless you do try to connect your questions to some kind of computer science, be it theory A or B or something else, I don't think they will be more popular. And I still don't understand why you would neither provide the connection, nor ask at Math@SE. (You are right about this question, they only characterize a subclass of weakly chordal graphs.)
Sasho Nikolov
CC BY-SA 3.0
2014-06-12T19:52:52.227Z
@SashoNikolov This is definitely a theoretical computer science question. It is naive to say that since you don't see the connection to TCS, it belongs in math. A graph representation is essentially a data structure. See e.g. Spinrad's text on Graph Representations. Here is an example: the graph of intersections of time intervals can be represented as an adjacency matrix or adj list, potentially O(n^2) space. But the intersection model says that each vertex (an interval) can be [a,b] with a,b on the number line, or 2n=O(n) numbers. Algorithmic implications of a small representation are plenty.
JimN
CC BY-SA 3.0
2014-06-13T14:58:39.187Z
@JimNastos My reaction to the question might have been too strong, since it came in the middle of a long sequence of questions that IMO were posted in bad faith. However, I am not convinced by your argument: I do not doubt the algorithmic usefulness of "nice" graph representations (that would be silly), but I do not see the algorithmic motivation in this question (note the question does not ask for a low complexity intersection model); if you do, can you please explain it? Otherwise this is like saying that metric embeddings is TCS, because metric embeddings have been very useful in TCS.
Sasho Nikolov
CC BY-SA 3.0
2014-11-08T10:56:39.433Z
Structural characterizations such as these are frequently discussed at conferences such as WG, COCOON and IWOCA which, at least in my opinion, are tcs conferences.
daniello
<hypergraphs><perfect-graph>
Intersection models for weakly chordal graphs?
NisaiVloot
# Intersection models for weakly chordal graphs?

(Asked by: username_0 on 2014-04-11)

Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :)

Among the many known classes of perfect graphs, there are three classes that I find especially interesting:

(1) the weakly chordal graphs, whose obstruction set is $\{C\_n,\bar{C\_n} : n \geq 5\}$,

(2) the chordal graphs, whose obstruction set is $\{C\_n : n \geq 4\}$,

(3) the strongly chordal graphs, whose obstruction set is $\{C\_n : n \geq 4\} \cup \{S\_n : n \geq 3\}$.

Here, $C\_n$ denotes the $n$-cycle, and $S\_n$ denotes the $n$-sun (obtained by starting from a cycle $x\_1 ... x\_n$ and adding the edges $x\_i y\_i x\_{i+1}$ for $1 \leq i \leq n$).

These classes admit polynomial algorithms for clique/independent set, the most general one being for the class of weakly chordal graphs and uses a clever 'two-pair contraction' argument (see 'Optimizing weakly triangulated graphs' by R. Hayward, C.T. Hoang and F. Maffray).

Intersection models are known for classes (2) and (3) as they correspond to the clique graphs of acyclic, resp. totally balanced, hypergraphs. Are there any known results about intersection models for weakly chordal graphs?

As a side note, there is a recursive construction of totally balanced hypergraphs due to Lehel (see 'A characterization of totally balanced matrices'), and I was also wondering about possible algorithmic applications of this result?

**Tags:** hypergraphs, perfect-graph
> **Comments:**
> **username_1**: Does this answer your question: http://www.sciencedirect.com/science/article/pii/S0166218X08005349? It was an obvious Google search away.  
> **username_1**: Besides throwing in a couple of side remarks about algorithms, this is still a math question. I asked you this once but your answer made little sense: is there a reason you are posting your questions here, where you don't get answers and they are not popular, rather than in Math@SE or in Mathoverflow where they would fit better? It makes no sense to me? And are effectively "spamming" the site.  
> **username_2**: I agree with @SashoNikolov. While I'm loathe to send math questions away (CS is math too!), your questions have little connection to anything in TCS, and it doesn't appear that you wish to make the effort to tie them in. In that case, [math.SE] or [mathoverflow.SE] makes a lot more sense.  
> **username_0**: @SashoNikolov: I didn't read the paper, but judging from the abstract it doesn't answer my question as it only considers a proper subclass of the weakly chordal graphs. Therefore, I assume that the question is still open.  
> **username_0**: @SureshVenkat: well, from an European perspective my questions belong to theoretical computer science in a broad sense - and the more math-oriented questions still have some constructive/algorithmic aspects that make them suited to this site, I think. Then again I can understand that people from 'Theory A' are more interested in things like TOC/CC/AGT and the like, but this shouldn't be a reason for peer exclusion I presume?  
> **username_2**: They can of course: but it's the poster's job to make the connections explicit. that's all we're asking.  
> **username_1**: I doubt the truth of your statement above. While algebra or logic may be more relevant to theory B, a non-computational question about these will not be theory B in general. Unless you do try to connect your questions to some kind of computer science, be it theory A or B or something else, I don't think they will be more popular. And I still don't understand why you would neither provide the connection, nor ask at Math@SE. (You are right about this question, they only characterize a subclass of weakly chordal graphs.)  
> **username_3**: @SashoNikolov This is definitely a theoretical computer science question. It is naive to say that since you don't see the connection to TCS, it belongs in math. A graph representation is essentially a data structure. See e.g. Spinrad's text on Graph Representations. Here is an example: the graph of intersections of time intervals can be represented as an adjacency matrix or adj list, potentially O(n^2) space. But the intersection model says that each vertex (an interval) can be [a,b] with a,b on the number line, or 2n=O(n) numbers. Algorithmic implications of a small representation are plenty.  
> **username_1**: @JimNastos My reaction to the question might have been too strong, since it came in the middle of a long sequence of questions that IMO were posted in bad faith. However, I am not convinced by your argument: I do not doubt the algorithmic usefulness of "nice" graph representations (that would be silly), but I do not see the algorithmic motivation in this question (note the question does not ask for a low complexity intersection model); if you do, can you please explain it? Otherwise this is like saying that metric embeddings is TCS, because metric embeddings have been very useful in TCS.  
> **username_4**: Structural characterizations such as these are frequently discussed at conferences such as WG, COCOON and IWOCA which, at least in my opinion, are tcs conferences.  

---

## 1 answers

### Answer by username_5 on 2014-04-12. Score: 1

If I would like to know something about intersection models, the first reference I would check is the "Topics in Intersection Graph Theory" by McKee and McMorris. Theorem 1.5 answers your (combinatorial) question.

> **Comments:**
> **username_0**: Thanks; as you can expect I don't have access to this book so may I ask what is the exact result? After all this site is about the free exchange of scientific information :)  
> **username_3**: Thm 1.5 of the book states that a if graph class is a nicely-behaved hereditary class, then it is an intersection class. And it goes on to say: "While [thm 1.5] can be used to show that a particular set of graphs is an intersection class, that is a long way from actually finding a suitable [representation] and proving that it works." So I don't think this necessarily answers the question here. Theorem 1.1 also states "Every graph is an intersection graph." The interesting open question on weakly chordal graphs is whether there is a nice/geometric intersection model for them (and to find it)  

---

