Logo

Login

Colorability in Orthogonal Graph Drawing

Stola, Jan (2008) Colorability in Orthogonal Graph Drawing. [Conference Paper]

Full text not available from this repository.

Abstract

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
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
Z Theory > Z.999 Others
ID Code:849
Deposited By:GDEA, Administration
Deposited On:24 Jun 2008
Last Modified:18 Sep 2008 13:09
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=4875&spage=327

Repository Staff Only: item control page

References

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

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

3. 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

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

rectangle visibility graphs, Proc. Graph Drawing 96,

25-44

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

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

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

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

Appl., 1-21

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

8. 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

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

University, Prague, Czech Republic

http://kam.mff.cuni.cz/~stola/chromaticInvariants.pdf

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

11. 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

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

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.