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, Berkeley, California, , 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
ID Code:168

Repository Staff Only: item control page

References

Bellantoni, S., Ben-Arroyo Hartman, I., Przytycka, T., Whitesides, S.: Grid intersection graphs and boxicity, Diskr. Appl. Math. (1994), 41-49.

Breu, H., Kirkpatrick, D.: On the compexity of recognizing intersection and touching graphs of disks, In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 88-98. Springer-Verlag, 1996.

Chandramouli, M., Diwan, A.A.: Upward numbering testing for triconnected graphs, In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 140-151. Springer-Verlag, 1996.

Eherlich, G., Even, S., Terjan, R.E.: Intersection graphs of curves in the plane, J. Combin. Theory Ser. B 21 (1976), 8-20.

de Fraysseix, H., de Mendez, P.O., Pach, J.: Representation of planar graphs by segmentes, Intuitive Geometry, Colloquia Mathematica Societatos Janos Bolyai 63 (1991), 109-117.

M.R. Garey and D.S. Johnson, Computers and Intractability,W.H. Freeman and Co., 1978.

P. Hlineny: Contact graphs of curves. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 312-323. Springer-Verlag, 1996.

Koebe, P.: Kontaktprobleme den konformen Abbildung, Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften, Leipzig, Math.-Physische Klasse 88 (1936), 141-164.

Kratochvíl, J.: String graphs I. There are infinitely many critical nonstring graphs, J. Combin. Theory Ser. B 52 (1991), 53-66.

Kratochvíl, J.: String graphs II. Recognizing string graphs is NP-hard, J. Combin. Theory Ser. B 52 (1991), 67-78.

Kratochvíl, J.: A special planar satisfiability problem and some consequences of its NP-completeness, Discr. Appl. Math. 52 (1994), 233-252.

Kratochvíl, J., Matousek, J.: Intersection graphs of segments, J. Combin. Theory Ser. B 68 (1994), 317-339.

Kratochvíl, J.: Intersection graphs of noncrossing arc-connected sets in the plane (technical report), KAM Series, Charles University, 1996.

Kratochvíl, J., Przytycka, T.: Grid intersection and box intersection graphs on surfaces (extended abstract), In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 365-372. Springer-Verlag, 1996.

Roberts, F.S.: On the boxicity and cubicity of a graph, In W.T. Tutte, ed., Recent Progress in Combinatorics, Academic Press, New-York, 1969, pages 301-310.

Sinden, F.W.: Topology of thin film RC-circuits, Bell systems Tech. J. (1966), 1639-1662.

Wood, D.: The riches of rectangles. In Proc. 5th International Meeting of Young computer Scientists, Smolenice, 1988, 67-75.