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 , 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

Actions (login required)

View Item View Item