Talk:1-planar graph

forbidden minors of o1p graphs

The article states about outer-1-planar graphs: "Unlike 1-planar graphs, the outer-1-planar graphs have a characterization in terms of graph minors: a graph is outer-1-planar if and only if it avoids each of a set of five forbidden minors." But, in the cited article, Recognizing outer 1-planar graphs in linear time, I read: "Note that a graph might still be o1p even if it contains a graph in M as a minor, as outer 1-planar graphs are not closed under taking minors." David Eppstein (talk · contribs), could you please clarify? Thanks, SyP (talk) 17:54, 4 November 2017 (UTC)

The two claims in the article, (1) that they always find a witness for non-outer-1-planarity in the form of a forbidden minor, and (2) that having one of these graphs as minors is not a witness, because outer-1-planarity is not minor-closed, cannot simultaneously be correct. At this point I'm not certain which one is wrong, and figuring it out and using the answer here would be original research, so maybe the safest thing to do is just to take out that part altogether? —David Eppstein (talk) 18:13, 4 November 2017 (UTC)

For now, I commented out the sentence. Thanks for the quick answer. SyP (talk) 18:24, 4 November 2017 (UTC)

Ok, thanks. It's not hard to construct examples where a minor of an outer-1-planar graph is not itself outer-1-planar. For example: Draw K4 outer-1-planar (as a square with its two diagonals), and decorate each of its four outside edges with two more vertices attached to both endpoints of the square edge. The resulting graph is outer-1-planar, but if you contract one of the square diagonals (resulting in a triangle with one triangle edge decorated by two attached vertices and two triangle edges decorated by four attached vertices) the result is not outer-1-planar. —David Eppstein (talk) 18:31, 4 November 2017 (UTC)