Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane

Kratochvíl, Jan (1997) Intersection Graphs of Noncrossing Arc-Connected Sets in the Plane. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 257-270(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_53).

Full text not available from this repository.

Abstract

Arc-connected sets A, B \in E_2 are called noncrossing if both A-B, B-A are arc-connected. A Graph is called an NCAC graph if it has an intersection representation in which vertices are represented by arc-connected sets in the plane and any two sets of the representation are noncrossing. In particular, disk intersection graphs are NCAC. By a unified reduction we show that recognition of disk intersection and NCAC graphs are NP-hard. A simple observation shows that triangle-free disk intersection and NCAC graphs are planar, and hence recognizable in polynomial time. On the other hand, recognition of triangle-free AC graphs (intersection graphs of arc-connected sets) is still NP-hard.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_53
Classifications: G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/168

Actions (login required)

View Item View Item