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.

Additional Metadata
Persistent URL hdl.handle.net/1765/88074
Journal Australasian Journal of Combinatorics
Citation
Laskar, R.C, Mulder, H.M, & Novick, B. (2012). Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs. Australasian Journal of Combinatorics, 52, 185–195. Retrieved from http://hdl.handle.net/1765/88074