Grid Intersection and Box Intersection Graphs on SurfacesKratochvíl, Jan and Przytycka, Teresa (1996) Grid Intersection and Box Intersection Graphs on Surfaces. In: Symposium on Graph Drawing, GD 1995, September 2022, 1995 , pp. 365372(Official URL: http://dx.doi.org/10.1007/BFb0021820). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BFb0021820
AbstractAs 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), 4149). 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.
Actions (login required)
