Article ID Journal Published Year Pages File Type
4656686 Journal of Combinatorial Theory, Series B 2016 10 Pages PDF
Abstract

We introduce a notion of bipartite minors and prove a bipartite analog of Wagner's theorem: a bipartite graph is planar if and only if it does not contain K3,3K3,3 as a bipartite minor. Similarly, we provide a forbidden minor characterization for outerplanar graphs and forests. We then establish a recursive characterization of bipartite (2,2)(2,2)-Laman graphs — a certain family of graphs that contains all maximal bipartite planar graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,