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 , pp. 254-261(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_377).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_377
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.560 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/187

Actions (login required)

View Item View Item