Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656686 | Journal of Combinatorial Theory, Series B | 2016 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Maria Chudnovsky, Gil Kalai, Eran Nevo, Isabella Novik, Paul Seymour,