Skip to main content
To refer to this page use:
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 $K_{3,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)$-Laman graphs --- a certain family of graphs that contains all maximal bipartite planar graphs.
Publication Date: Jan-2016
Electronic Publication Date: 21-Aug-2015
Citation: M. Chudnovsky, G. Kalai, E. Nevo, I. Novik, and P. Seymour, Bipartite minors , J. Combin. Theory Ser. B, to appear, DOI 10.1016/j.jctb.2015.08.001.
DOI: 10.1016/j.jctb.2015.08.001
Pages: 219–228
Type of Material: Journal Article
Journal/Proceeding Title: Journal of combinatorial theory. Series B.
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.