Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
  1. Does graph shown below from the paper Dissection Graphs of Planar Point Sets by P. Erdos, L. Lovasz, A. Simmons, and E.G. Straus have a name?

  2. Does it come from a family of related graphs?

This comes from the Erdos, Lovasz Paper

share|cite|improve this question
This graph is a chordal graph (triangulated graphs) – M.M Jul 25 '15 at 16:50
up vote 0 down vote accepted

As stated in the comments, this is a chordal graph. It's also a block graph with blocks $B_1=\{p'_1,p''_1\}$, $B_2=\{p'_3,p''_3\}$, $B_3=\{p'_5,p''_5\}$, and $B_4=\{p''_1,p'_2,p''_2,p''_3,p'_4,p''_4,p''_5,p'_6,p''_6\}$.

Consider the cycle $C=\{p'_6,p''_6,p''_4,p''_2\}$. The graph is not strongly chordal ($C$ doesn't contain an odd chord). The graph is not a split graph ($C$ is a $4$-cycle, which is a forbidden subgraph for split graphs).

share|cite|improve this answer
I don't think this is a block graph though. In a block graph, the blocks should be complete. You claim $B_4$ is a block, but it is not a clique. – mrm Oct 14 '15 at 13:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.