Adiga, Abhijin ;
Chandran, L. Sunil ;
Mathew, Rogers
Cubicity, Degeneracy, and Crossing Number
Abstract
A kbox B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 X R_2 X ... X R_k. If each R_i is a unit length interval, we call B a kcube. Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of kboxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of kcubes.
It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan. Representing graphs as the intersection of axisparallel cubes. MCDES2008, IISc Centenary Conference, available at CoRR, abs/cs/0607092, 2006.] that, for a graph G with maximum degree \Delta, cub(G) <= \lceil 4(\Delta +1) ln n\rceil. In this paper we show that, for a kdegenerate graph G, cub(G) <= (k+2) \lceil 2e log n \rceil. Since k is at most \Delta and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(\lceil 2.42 log n\rceil + 1) dimensional cube representation for G.
The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4}{\lceil log t\rceil}^{3/4}) . This bound is tight upto a factor of O((log t)^{3/4}).
Let (P,\leq) be a partially ordered set and let G_{P} denote its underlying comparability graph. Let dim(P) denote the poset dimension of P. Another interesting consequence of our result is to show that dim(P) \leq 2(k+2) \lceil 2e \log n \rceil, where k denotes the degeneracy of G_{P}. Also, we get a deterministic algorithm that runs in O(n^2k) time to construct a 16k(\lceil 2.42 log n\rceil + 1) sized realizer for P. As far as we know, though very good upper bounds exist for poset dimension in terms of maximum degree of its underlying comparability graph, no upper bounds in terms of the degeneracy of the underlying comparability graph is seen in the literature.
BibTeX  Entry
@InProceedings{adiga_et_al:LIPIcs:2011:3342,
author = {Abhijin Adiga and L. Sunil Chandran and Rogers Mathew},
title = {{Cubicity, Degeneracy, and Crossing Number}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {176190},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3342},
URN = {urn:nbn:de:0030drops33428},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.176},
annote = {Keywords: Degeneracy, Cubicity, Boxicity, Crossing Number, Interval Graph, Intersection Graph, Poset Dimension, Comparability Graph }
}
2011
Keywords: 

Degeneracy, Cubicity, Boxicity, Crossing Number, Interval Graph, Intersection Graph, Poset Dimension, Comparability Graph 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Issue date: 

2011 
Date of publication: 

2011 