A Simple Proof for the NP-Hardness of Edge Labeling
Source file as Postscript Document Portable Document Format

Preprint series: Preprint-Reihe Mathematik, 11/2000

MSC 2000

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

CR: F.2.2 G.2.2

Abstract
Kakoulis and Tollis have shown that labeling the edges of a graph drawing with axis-parallel rectangles is NP-hard. In this note we simplify their proof by reducing from planar 3-SAT instead of 3-SAT.

Keywords: Complexity theory, graph drawing, computational geometry, label placement