Intersection Graphs of Noncrossing ArcConnected Sets in the PlaneKratochvíl, Jan (1997) Intersection Graphs of Noncrossing ArcConnected Sets in the Plane. In: Symposium on Graph Drawing, GD '96, September 1820, 1996 , pp. 257270(Official URL: http://dx.doi.org/10.1007/3540624953_53). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540624953_53
AbstractArcconnected sets A, B \in E_2 are called noncrossing if both AB, BA are arcconnected. A Graph is called an NCAC graph if it has an intersection representation in which vertices are represented by arcconnected 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 NPhard. A simple observation shows that trianglefree disk intersection and NCAC graphs are planar, and hence recognizable in polynomial time. On the other hand, recognition of trianglefree AC graphs (intersection graphs of arcconnected sets) is still NPhard.
Actions (login required)
