Chordal graphs and perfect elimination

Asked by Ged Ridgway on 2010-07-26

I am interested in testing whether a graph is chordal, or, relatedly, finding the lengths of its chordless cycles.
  http://en.wikipedia.org/wiki/Chordal_graph
As described on that page, a further problem is finding a "perfect elimination ordering" of a chordal graph.

I have briefly searched the help here,
  http://www.stanford.edu/~dgleich/programs/matlab_bgl/matlab_bgl_v2.1.pdf
for "chord", "cycle", "perfect", and a few other terms, but was unable to find anything.

Are there any tools in matlabBGL that would help with this problem?

Many thanks,
Ged

Question information

Language:
English Edit question
Status:
Solved
For:
Matlab BGL Edit question
Assignee:
No assignee Edit question
Solved by:
David Gleich
Solved:
Last query:
Last reply:
Revision history for this message
David Gleich (dgleich) said :
#1

There is nothing in there yet unless you have a planar graph. If you have a planar graph than the maximal_planar_graph will produce a chordal graph.

David

Revision history for this message
Ged Ridgway (ged-ridgway) said :
#2

Hi David,

If I have a tree, like:
  G = sparse(toeplitz([0 1 0]))
it is both planar and chordal (unless I am getting confused), but
make_maximal_planar (as it seems to be called in version 4.0.1, which
I believe is the latest downloadable from matlab central) adds the
missing edge to complete the triangle.

So am I right in concluding the following: if make_maximal_planar
leaves the graph unchanged, then it must be chordal, but if
make_maximal_planar changes the graph, then this does not imply that
it is not chordal?

Thanks for your help,
Ged

P.S. Can I infer from your use of the word "yet" that there is a
chance of this making it's way into a future release, or do you have
no particular plans for features related to finding cycle lengths or
to finding a perfect elimination ordering for a chordal graph? Not
meaning to nag, but rather to judge whether any efforts I spent in
this direction would be soon duplicated.

On 26 July 2010 17:46, David Gleich
<email address hidden> wrote:
> Your question #119018 on Matlab BGL changed:
> https://answers.launchpad.net/matlab-bgl/+question/119018
>
>    Status: Open => Answered
>
> David Gleich proposed the following answer:
> There is nothing in there yet unless you have a planar graph.  If you
> have a planar graph than the maximal_planar_graph will produce a chordal
> graph.
>
> David
>
> --
> If this answers your question, please go to the following page to let us
> know that it is solved:
> https://answers.launchpad.net/matlab-bgl/+question/119018/+confirm?answer_id=0
>
> If you still need help, you can reply to this email or go to the
> following page to enter your feedback:
> https://answers.launchpad.net/matlab-bgl/+question/119018
>
> You received this question notification because you are a direct
> subscriber of the question.
>

Revision history for this message
Best David Gleich (dgleich) said :
#3

Hmm... I'll have to think more about what make_maximal_planar does
with respect to trees and chordal graphs. The output from
make_maximal_planar is always chordal from what I remember about it.

Working with Chordal graphs is something I was going to look into for
the next version. Why don't you file a bug with a wishlist priority
on the topic?

It looks like RBGL has an implementation of this feature. If you
wanted to port their implementation to pure BGL and then submit it, I
could include it in the next matlab bgl easily.

David

Thanks,
David

On Mon, Jul 26, 2010 at 10:24 AM, Ged Ridgway
<email address hidden> wrote:
> Question #119018 on Matlab BGL changed:
> https://answers.launchpad.net/matlab-bgl/+question/119018
>
>    Status: Answered => Open
>
> Ged Ridgway is still having a problem:
> Hi David,
>
> If I have a tree, like:
>  G = sparse(toeplitz([0 1 0]))
> it is both planar and chordal (unless I am getting confused), but
> make_maximal_planar (as it seems to be called in version 4.0.1, which
> I believe is the latest downloadable from matlab central) adds the
> missing edge to complete the triangle.
>
> So am I right in concluding the following: if make_maximal_planar
> leaves the graph unchanged, then it must be chordal, but if
> make_maximal_planar changes the graph, then this does not imply that
> it is not chordal?
>
> Thanks for your help,
> Ged
>
> P.S. Can I infer from your use of the word "yet" that there is a
> chance of this making it's way into a future release, or do you have
> no particular plans for features related to finding cycle lengths or
> to finding a perfect elimination ordering for a chordal graph? Not
> meaning to nag, but rather to judge whether any efforts I spent in
> this direction would be soon duplicated.
>
>
> On 26 July 2010 17:46, David Gleich
> <email address hidden> wrote:
>> Your question #119018 on Matlab BGL changed:
>> https://answers.launchpad.net/matlab-bgl/+question/119018
>>
>>    Status: Open => Answered
>>
>> David Gleich proposed the following answer:
>> There is nothing in there yet unless you have a planar graph.  If you
>> have a planar graph than the maximal_planar_graph will produce a chordal
>> graph.
>>
>> David
>>
>> --
>> If this answers your question, please go to the following page to let us
>> know that it is solved:
>> https://answers.launchpad.net/matlab-bgl/+question/119018/+confirm?answer_id=0
>>
>> If you still need help, you can reply to this email or go to the
>> following page to enter your feedback:
>> https://answers.launchpad.net/matlab-bgl/+question/119018
>>
>> You received this question notification because you are a direct
>> subscriber of the question.
>>
>
> --
> You received this question notification because you are an answer
> contact for Matlab BGL.
>

Revision history for this message
Ged Ridgway (ged-ridgway) said :
#4

Hi David,

Sorry, my previous message wasn't clear; make_maximal_planar does return a chordal graph, it's just that this can't be used to check if the original graph was already chordal, because it might have been chordal but not maximal planar, like a tree. In my case, I don't want to find a new (maximal planar) chordal graph, but to investigate the properties of the original graph. I will file a wishlist bug, as you suggest.

Many thanks,
Ged