Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistinguishing classes of intersection graphs of homothets or similarities of two convex disks
300
0
0.0
(
0
)
Added by
Bartosz Walczak
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
For smooth convex disks $A$, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes $G^{text{hom}}(A)$ and $G^{text{sim}}(A)$ of intersection graphs that can be obtained from homothets and similarities of $A$, respectively. Namely, we prove that $G^{text{hom}}(A)=G^{text{hom}}(B)$ if and only if $A$ and $B$ are affine equivalent, and $G^{text{sim}}(A)=G^{text{sim}}(B)$ if and only if $A$ and $B$ are similar.
rate research
Read More
We obtain improved upper bounds and new lower bounds on the chromatic number as a linear function of the clique number, for the intersection graphs (and their complements) of finite families of translates and homothets of a convex body in $RR^n$.
We consider asymmetric convex intersection testing (ACIT). Let $P subset mathbb{R}^d$ be a set of $n$ points and $mathcal{H}$ a set of $n$ halfspaces in $d$ dimensions. We denote by $text{ch}(P)$ the polytope obtained by taking the convex hull of $P$, and by $text{fh}(mathcal{H})$ the polytope obtained by taking the intersection of the halfspaces in $mathcal{H}$. Our goal is to decide whether the intersection of $mathcal{H}$ and the convex hull of $P$ are disjoint. Even though ACIT is a natural variant of classic LP-type problems that have been studied at length in the literature, and despite its applications in the analysis of high-dimensional data sets, it appears that the problem has not been studied before. We discuss how known approaches can be used to attack the ACIT problem, and we provide a very simple strategy that leads to a deterministic algorithm, linear on $n$ and $m$, whose running time depends reasonably on the dimension $d$.
A conflict-free $k$-coloring of a graph $G=(V,E)$ assigns one of $k$ different colors to some of the vertices such that, for every vertex $v$, there is a color that is assigned to exactly one vertex among $v$ and $v$s neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well studied in graph theory. Here we study the conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of $n$ geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in $Omega(log n/loglog n)$ and in $Omega(sqrt{log n})$ for disks or squares of different sizes; it is known for general graphs that the worst case is in $Theta(log^2 n)$. For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.
Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest pair problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.
A graph $G$ is said to be the intersection of graphs $G_1,G_2,ldots,G_k$ if $V(G)=V(G_1)=V(G_2)=cdots=V(G_k)$ and $E(G)=E(G_1)cap E(G_2)capcdotscap E(G_k)$. For a graph $G$, $mathrm{dim}_{COG}(G)$ (resp. $mathrm{dim}_{TH}(G)$) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives $G$. We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph $G$: (a) $mathrm{dim}_{COG}(G)leqmathrm{tw}(G)+2$, (b) $mathrm{dim}_{TH}(G)leqmathrm{pw}(G)+1$, and (c) $mathrm{dim}_{TH}(G)leqchi(G)cdotmathrm{box}(G)$, where $mathrm{tw}(G)$, $mathrm{pw}(G)$, $chi(G)$ and $mathrm{box}(G)$ denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph $G$. We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on $mathrm{dim}_{COG}(G)$ and $mathrm{dim}_{TH}(G)$ when $G$ belongs to some special graph classes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
