Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs

R.C. Laskar, Martyn Mulder and Beth Novick

No EI 2011-16, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: Maximal outerplanar graphs are characterized using three different classes of graphs. A path-neighborhood graph is a connected graph in which every neighborhood induces a path. The triangle graph $T(G)$ has the triangles of the graph $G$ as its vertices, two of these being adjacent whenever as triangles in $G$ they share an edge. A graph is edge-triangular if every edge is in at least one triangle. The main results can be summarized as follows: the class of maximal outerplanar graphs is precisely the intersection of any of the two following classes: the chordal graphs, the path-neighborhood graphs, the edge-triangular graphs having a tree as triangle graph.

Keywords: chordal graph; elimination ordering; maximal outerplanar graph; path-neighborhood graph; triangle graph (search for similar items in EconPapers)
Date: 2011-06-07
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/23560/EI2011-16.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:23560

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).