3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented Jan 15, 2014 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
    Commented Jan 15, 2014 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
    Commented Jan 16, 2014 at 3:48

1 Answer 1

Reset to default
5
$\begingroup$

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]).

Improve this answer
$\endgroup$
2
  • 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
    Commented Jan 15, 2014 at 12:07
  • $\begingroup$ @JanDvorak wikified, feel free to edit that in (or post your own answer). $\endgroup$
    – Ben Barber
    Commented Jan 15, 2014 at 12:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .