On Representations of Some Thickness-Two Graphs

Hutchinson, Joan P. and Shermer, Thomas and Vince, Andrew (1996) On Representations of Some Thickness-Two Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 324-332 (Official URL: http://dx.doi.org/10.1007/BFb0021815).

Full text not available from this repository.

Abstract

This paper considers representations of graphs as rectangle-visibility graphs and as doubly linear graphs. These are, respectively, graphs whose vertices are isothetic rectangles in the plane with adjacency determined by horizontal and vertical visibility, and graphs that can be drawn as the union of two straight-edges planar graphs. We prove that these graphs have, with n vertices, at most 6n-20 (resp., 6n-18) edges, and we provide examples of these graphs with 6n-20 edges for each n\ge8.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021815
Classifications:P Styles > P.720 Straight-line
P Styles > P.900 Visibility
M Methods > M.600 Planar
ID Code:160

Repository Staff Only: item control page

References

J. Battle, F. Harary, and Y. Kodama, Every planar graph with nine points has a nonplanar complement, Bull. Amer. Math. Soc. 68 (1962) 569-571.

A. Dean and J. P. Hutchinson, Rectangle-visibility representations of bipartite graphs, Extended Abstract, Lecture Notes in Computer Science (Proc. DIMACS Workshop Graph Drawing, 1994), R. Tamassia and I. G. Tollis, eds., vol. 894, Springer-Verlag, 1995, 159-166.

A. Dean and J. P. Hutchinson, Rectangle-visibility representations of bipartite graphs (submitted).

M. Gardner, Mathematical Games, Scientific American 242 (Feb. 1980) 14-19.

M. R. Garey, D. S. Johnson, and H.C. So, An application of graph coloring to printed circuit testing, IEEE Trans. Circuits and Systems CAS-23 (1976) 591-599.

J. P. Hutchinson, Coloring ordinary maps, maps of empires, and maps of the Moon, Math. Mag. 66 (1993) 211-226.

J. P. Hutchinson, T. Shermer, and A. Vince, On representations of some thickness-two graphs (submitted).

D. G. Kirkpatrick and S. K. Wismath, Weighted visibility graphs of bars and related flow problems, Lecture Notes in Computer Science (Proc. 1st Workshop Algorithms Data Struct.), vol. 382, Springer-Verlag, 1989, 325-334.

A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Phil. Soc. 93 (1983) 9-23.

H. Meijer, personal communication.

J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, N. Y., 1987.

G. Ringel, Färbungsprobleme auf Flächen und Graphen, Deutscher Verlag der Wissenschaften, Berlin, 1959.

E. Steinitz and H. Rademacher, Vorlesungen über die Theorie der Polyeder, Springer, Berlin, 1934.

R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Disc. and Comp. Geom. 1 (1986) 321-341.

C. Thomassen, Rectilinear drawings of graphs, J. Graph Theory 12 (1988) 335-341.

W. T. Tutte, On the non-biplanar character of the complete 9-graph, Canad. Math. Bull. 6 (1963) 319-330.

William T. Tutte,The thickness of a graph, Indag. Math. 25 (1963) 567-577.

J. D. Ullman, Computational Aspects of VLSI Design, Computer Science Press, Rockville, Md., 1984.

S. K. Wismath, Characterizing bar line-of-sight graphs, Proc. 1st Symp. Comp. Geom., ACM (1985) 147-152.