International Journal of Foundations of Computer Science · 2006 · 55 citations · 2 references
ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryGraph AlgorithmsGraph DrawingGraph Layout AlgorithmsGraph TheoryLine DrawingGraph Drawing AlgorithmsPlanar Graph AlgorithmsPlanar Graph DrawingPlanar Graph RepresentationsPlanar Graphs
We investigate the computational complexity of the following problem. Given a planar graph in which some vertices have already been placed in the plane, place the remaining vertices to form a planar straight-line drawing of the whole graph. We show that this extensibility problem, proposed in the 2003 "Selected Open Problems in Graph Drawing" [1], is NP-hard.
2
Planar Formulae and Their Uses
David Lichtenstein · SIAM Journal on Computing · 1982 · 754 citations
S. K. Stein · Proceedings of the American Mathematical Society · 1951 · 85 citations · Full text