Graph TheoryHardPlanar Graphs
Planar Graphs · Hard problem
A connected simple planar bipartite graph is -regular (every vertex has degree ), and every face in its plane drawing is a quadrilateral (achieving the bipartite edge bound with equality). How many edges does it have?