Unit-length rectangular drawings of graphs (Q6636988)

A subgraph of a complete grid is called a grid graph. The recognition of grid graphs is NP-complete, even if restricted to trees of maximum degree three [\textit{A. Gregori}, Inf. Process. Lett. 31, No. 4, 167--173 (1989; Zbl 0672.68014)]. A similar reduction from PLANAR 3SAT shows the hardness for the restriction to biconnected plane graphs with internal faces of size four and six. Since the edges cannot be stretched, each \(C_4\) becomes a square and each \(C_6\) becomes a rectangle in every such embedding. The problem becomes solvable in polynomial time if also the external face has to become rectangular in shape and internal faces have even sizes.