On the complexity of orthogonal compaction

摘要

We consider three closely related optimization problems, arising from the graph drawing and the VLSI research areas, and conjectured to be NP-hard, and we prove that, in fact, they are NP-complete. Starting from an orthogonal representation of a graph, i.e., a description of the shape of the edges that does not specify segment lengths or vertex positions, the three problems consist of providing an orthogonal grid drawing of it, while minimizing the area, the total edge length, or the maximum edge length, respectively. This result confirms a long surviving conjecture of NP-hardness, justifies the research about applying sophisticated, yet possibly time consuming, techniques to obtain optimally compacted orthogonal grid drawings, and discourages the quest for an optimally compacting polynomial-time algorithm.