Colorability in Orthogonal Graph Drawing

Stola, Jan (2008) Colorability in Orthogonal Graph Drawing. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 327-338 (Official URL:

Full text not available from this repository.


This paper studies the question: What is the maximum integer k_b,n such that every k_b,n-colorable graph has a b-bend n-dimensional orthogonal box drawing? We give an exact answer for the orthogonal line drawing in all dimensions and for the 3-dimensional rectangle visibility representation. We present an upper and lower bound for the 3-dimensional orthogonal drawing by rectangles and general boxes. Particularly, we improve the best known upper bound for the 3-dimensional orthogonal box drawing from 183 to 42 and the lower bound from 3 to 22.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_32
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
Z Theory > Z.999 Others
ID Code:849

Repository Staff Only: item control page


D.R. Wood (2000): Three-Dimensional Orthogonal Graph Drawing, Ph.D. Thesis, School of Computer Science and Software Engineering, Monash University

S.P. Fekete, H. Meijer (1997): Rectangle and box visibility graphs in 3D, Int. J. Comput. Geom. Appl. 97, 1-28

S.P. Fekete, M.E. Houle, S. Whitesides (1995): New results on a visibility representation of graphs in 3D, Proc. Graph Drawing 95, 234-241

P. Bose, A. Dean, J. Hutchinson, T. Shermer (1996): On

rectangle visibility graphs, Proc. Graph Drawing 96,


J.P. Hutchinson, T. Shermer, A. Vince (1999): On

representations of some thickness-two graphs, Comput. Geom. 13(3), 161-171

A.M. Dean, J.P. Hutchinson (1998): Rectangle-visibility

Layouts of Unions and Products of Trees, J. Graph Algorithms

Appl., 1-21

T. Shermer (1996): Block visibility representations III:

External visibility and complexity. In Kranakis, Fiala and Sack, eds., Proc. of 8th Canadian Conf. on Comput. Geom., vol. 5 of Int. Informatics Series, Carleton University Press, 234-239

S.P. Fekete, M.E. Houle, S. Whitesides (1997):

The wobbly logic engine: proving hardness of non-rigid geometric graph representation problems, Report No. 97.273, Angewandte Mathematik und Informatik Universität zu Köln

J. Stola (2006): Chromatic invariants in graph drawing, Master's Thesis, Department of Applied Mathematics, Charles

University, Prague, Czech Republic

V. Chvátal (1969): On finite polarized partition relations, Canad. Math. Bul., 12, 321-326

L. W. Beineke, A. J. Schwenk (1975): On a bipartite form of the Ramsey problem, Proc. 5th British Combin. Conf. 1975, Congr. Numer. XV, 17-22

T. Biedl, T. Shermer, S. Whitesides, S. Wismath (1999): Bounds for orthogonal 3D graph drawing, J. Graph Alg. Appl, 3(4):63-79