×

zbMATH — the first resource for mathematics

A special planar satisfiability problem and a consequence of its NP- completeness. (English) Zbl 0810.68083
Summary: We introduce a weaker but still NP-complete satisfiability problem to prove NP-completeness of recognizing several classes of intersection graphs of geometric objects in the plane, including grid intersection graphs and graphs of boxicity two.

MSC:
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] S. Bellantoni, I. Ben-Arroyo Hartman, T. Przytycka and S. Whitesides, Grid intersection graphs and boxicity, preprint. · Zbl 0784.05031
[2] Ben-Arroyo Hartman, I.; Newman, I.; Ziv, R, On grid intersection graphs, Discrete math., 87, 41-52, (1991) · Zbl 0739.05081
[3] Cozzens, M.B., Higher and multi-dimensional analogues of interval graphs, ()
[4] Ehrlich, G.; Even, S.; Tarjan, R.E., Intersection graphs of curves in the plane, J. combin. theory ser. B, 21, 8-20, (1976) · Zbl 0348.05113
[5] Golumbic, M.C., Interval graphs and related topics, Discrete math., 55, 113-121, (1985) · Zbl 0568.05046
[6] Graham, R.L., Problem 1, open problems at 5th Hungarian colloquium on combinatorics, keszthely, (), Keszthely
[7] Kratochvíl, J.; Goljan, M.; Kučera, P., String graphs, (1986), Academia Prague · Zbl 0607.05031
[8] Kratochvíl, J., String graphs II. recognizing string graphs in NP-hard, J. combin. theory ser. B, 52, 67-78, (1991) · Zbl 0661.05054
[9] J. Kratochvíl and J. Matoušek, Intersection graphs of segments, J. Combin. Theory Ser. B, to appear.
[10] Kratochvíl, J.; Matoušek, J., NP-hardness results for intersection graphs, Comment. math. univ. carolin, 30, 761-773, (1989) · Zbl 0697.05052
[11] Kratochvíl, J.; Nešetřil, J., INDEPENDENT SET and CLIQUE problems in intersection defined classes of graphs, Comment. math. univ. carolin., 31, 85-93, (1990) · Zbl 0727.05056
[12] Kratochvíl, J.; Nešetřil, J., Open problem, (), 380-381
[13] Lichtenstein, D., Planar formulae and their uses, SIAM J. comput., 11, 329-343, (1982) · Zbl 0478.68043
[14] Mansfield, A., Determining the thickness of graphs is NP-hard, Proc. math. Cambridge phil. soc., 39, 9-23, (1983) · Zbl 0503.68048
[15] Roberts, F.S., On the boxicity and cubicity of a graph, (), 301-310 · Zbl 0193.24301
[16] Sinden, F.W., Topology of thin film RC-circuits, Bell system technol. J., 1639-1662, (1966) · Zbl 0144.45601
[17] Tovey, C.A., A simplified satisfiability problem, Discrete appl. math., 8, 85-89, (1984) · Zbl 0534.68028
[18] Valiant, L.G., University considerations in VLSI circuits, IEEE trans. comput., 30, 135-140, (1981) · Zbl 0455.94046
[19] Wood, D., The riches of rectangles, Proceedings fifth international meeting of Young computer scientists, Smolenice, 67-75, (1988)
[20] Yannakakis, M., The complexity of the partial order dimension problem, SIAM J. algebraic discrete methods, 3, 351-358, (1982) · Zbl 0516.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.