Logo

Login | Create Account

Grid Intersection and Box Intersection Graphs on Surfaces

Kratochvíl, Jan and Przytycka, Teresa (1996) Grid Intersection and Box Intersection Graphs on Surfaces. [Conference Paper]

Full text not available from this repository.

Abstract

As analogs to grid intersection graphs and rectangle intersection graphs in the plane, we consider grid intersection graphs, grid contact graphs and box intersection graphs on the other two euclidean surfaces - the annulus and the torus. Our first results concern the inclusions among these classes, and the main result is negative - there are bipartite box intersection graphs on annulus (torus), which are not grid intersection graphs on the particular surfaces (in contrast to the planar case, where the two classes are equal, cf. Bellantoni, Hartman, Przytycka, Whitesides: Grid intersection graphs and boxicity, Discrete Math. 114 (1993), 41-49). We also consider the question of computational complexity of recognizing these classes. Among other results, we show that recognition of grid intersection graphs on annulus and torus are both polynomial time solvable, provided orderings of both vertical and horizontal segments are specified.

Item Type:Conference Paper
Classifications:Z Theory > Z.250 Geometry
M Methods > M.100 Algebraic
G Algorithms and Complexity > G.560 Geometry
ID Code:179
Deposited By:Maciejak, Agnes
Deposited On:14 Oct 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

1. Bellantoni, S., Ben-Arroyo Hartman, I., Przytycka, T., Whitesides, S.: Grid intersection graphs and boxicity, Discrete Math. 114 (1993), 41-49

2. Cozzens, M. B., Roberts, F. S.: On dimensional properties of graphs, Graphs and Combinatorics 5 (1989), 29-46

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

4. Kratochvíl, J.: A special planar satisfiability problem and a consequence of its NP-completeness, Discrete Appl. Math. 52 (1994) 233-252

5. Mohar, B. (private communication)

6. Mohar, B., Rosenstiehl, P.: Tessellation and visibility representations of maps on the torus (preprint)

7. 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, pp. 301-310

8. Rosenstiehl, P., Tarjan, R. E.: Rectilinear planar layouts and bipolar orientations of graphs, Discrete Comput. Geometry 1 (1986), 343-353

9. Tamassia, R., Tollis, I. G.: A unified approach to visibility representations of planar graphs, Discrete Comput. Geometry 1 (1986), 321-341

10. Wood, D.: The riches of rectangles, In: Proceedings 5th International Meeting of Young Computer Scientists, Smolenice (1988), 67-75.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.