Digital Commons Network^™

Excluded-Minor Characterization Of Apex-Outerplanar Graphs, Stanislaw Dziobiak

LSU Doctoral Dissertations

It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K_4 and K_{2,3}. The class of graphs that contain a vertex whose removal leaves an outerplanar graph is also minor-closed. We provide the complete list of 57 excluded minors for this class.

Some Classes Of Graphs That Are Nearly Cycle-Free, Lisa Warshauer

LSU Doctoral Dissertations

A graph is almost series-parallel if there is some edge that one can add to the graph and then contract out to leave a series-parallel graph, that is, a graph with no K₄-minor. In this dissertation, we find the full list of excluded minors for the class of graphs that are almost series-parallel. We also obtain the corresponding result for the class of graphs such that uncontracting an edge and then deleting the uncontracted edge produces a series-parallel graph.

A notable feature of a 3-connected almost series-parallel graph is that it has two vertices whose removal leaves a …