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.

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
ID Code:187

Repository Staff Only: item control page

References

Eades, P., Wormald, N.: Fixed Edge Length Graph Drawing is NP-hard. Discrete Applied Mathematics. 28 (1990) 111-134.

Cook, S.: The complexity of theorem-proving procedures. Proc. 3rd Ann. ACM Symp. on Theory of Computing (assoc. Comput. Mach., New York, 1971) 151-158.

Lichtenstein, D.: Planar formulae and their uses. SIAM Journal of Computing 11 (1982) no. 2, 329-343.

Tovey, C.: A simplified NP-complete satisfiability problem. Discrete-Applied-Mathematics 8 (1984), no. 1, 85-89.