Recall a graph is chordal if it contains no induced cycle of length 4 or more, and outerplanar if it has a crossing-free embedding in the plane such that all vertices are on the same face. While studying a certain problem, I came across chordal outerplanar graphs, which are graphs that are both chordal and outerplanar. ISGCI didn't know of such a class. In fact, the closest thing I was able to find was the class of chordal $\cap$ planar graphs.

Have chordal outerplanar graphs been studied before somewhere? What kind of properties do they have? Are they perhaps equivalent to some well-known (or a better known) graph class?

For example, it seems to me that every inner face of such a graph is a triangle. The motivation for the third question is that I got at most 5 hits when googling for such graphs, so I wonder if such graphs might be commonly known as something other than chordal outerplanar graphs.

  • 1
    $\begingroup$ You didn't try searching Google scholar for "chordal outerplanar", did you? It returns a small but nonzero number of hits. So the answer to "have they been studied before?" is yes. $\endgroup$ – David Eppstein Jan 15 '14 at 13:32
  • $\begingroup$ @DavidEppstein I sure did (and my apologies for not mentioning this explicitly in the question. I know its part of the SE policies). For "outerplanar chordal" I got zero hits, and for "chordal outerplanar" I got 5 hits. I was expecting way more so it made me wonder if I'm even searching for the right thing (i.e. perhaps chordal outerplanar graphs are really known as X graphs, hence the question). $\endgroup$ – Juho Jan 15 '14 at 14:46
  • $\begingroup$ Probably the reason you didn't find more is that most research on graphs like this concerns maximal outerplanar graphs (almost the same thing, but with the additional requirement of being 2-connected). I get many more hits for them. $\endgroup$ – David Eppstein Jan 16 '14 at 3:48

Yes, every inner face must be a triangle, as chords drawn outside a cycle prevent a drawing from being outerplanar. Drawings of chordal graphs are then just triangulations of polygons; conversely, every triangulated polygon is outerplanar (certainly) and chordal (by induction, as cycles are sub-[triangulated polygons]).

  • 6
    $\begingroup$ If we take a union of two polygon triangulations that overlap at one vertex, wouldn't that be a graph that is outerplanar, chordal and and not a polygon triangulation? For me, the classification seems to be "a 2-disconnected union of polygon triangulations (and single edges and disconnected vertices)". $\endgroup$ – John Dvorak Jan 15 '14 at 12:07
  • $\begingroup$ @JanDvorak wikified, feel free to edit that in (or post your own answer). $\endgroup$ – Ben Barber Jan 15 '14 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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