On the difficulty of embedding planar graphs with inaccuracies (Extended Abstract)
Godau, Michael (1995) On the difficulty of embedding planar graphs with inaccuracies (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 254-261 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_377).
Full text not available from this repository.
In this paper it will be shown that the following problem is NP-hard. We are given a labeled planar graph, each vertex of which is assigned to a disc in the plane. Decide whether it is possible to embed the graph in the plane with line segments as edges such that each vertex lies in its disc.
Repository Staff Only: item control page