Information Technology Reference
In-Depth Information
Considering UCRs with congruent objects, Breu and Kirkpatrick [4] prove that the
recognition of unit disk graphs is NP-complete; indeed, this holds even for the recogni-
tion of bounded-ratio disk graphs. For a survey on recognition-complexity results with
balls and disks we refer to [9].
Czyzowicz et al. [5] are interested in discrete versions of unit disk graphs and study
UCRs of non-rotated copies of regular
k
-gons with two different contact types: vertex-
to-vertex and whole edge contact. For even
k
,thesegraph classes coincide (for odd
k
the
second class is empty). It turns out that these graphs are also unit disk graphs and that
the recognition of graphs allowing for a representation with 4
k
-gons is NP-complete.
In 3D, Bremner et al. [3], show that it is NP-complete to decide whether a graph
admits a UPCR with cubes. In [1, 2] UPCR with cubes of subgraphs of 5 Archimedean
grids are given. These are partly obtained by threshold colorings. However, threshold
colorings cannot be used to find UPCR with cubes for all subgraphs of Archimedean
grids; in particular, not for all subgraphs of the triangular grid [1].
1.2
Our Contributions
We develop a strategy to construct unit proper contact representations (UPCR) in 2D
and 3D for subgraphs of certain highly symmetric grids. This strategyisusedtoshow
that subgraphs of the square grid allow for UPCR with squares. This is a strength-
ening of the unit cube representation of Alam et al. [2]. We generalize this result to
4
k
-gons as well as to higher dimensions, namely, we prove that subgraphs of a
d
-
dimensional grid have UPCR with
d
-cubes. Furthermore, we show that subgraphs of
the triangular grid admit UPCRs with cubes, implying that the same holds for all sub-
graphs of Archimedean grids (grids originating from regular and semi-regular tilingsof
the plane). This solves an open problem posed by Alam et al. [2]. Considering other
geometric objects, we construct UPCRs with regular 3
k
-gons of the hexagonal grid.
Additionally, we observe that with the ideas of [3], we can show the NP-complete-
ness of recognizingunit square proper contact graphs.
2
Definitions and Properties
d
)
,v
Let
G
=(
V,E
) be a graph. A function
ˆ
:
V
ₒP
(
R
ₒ
S
v
is called a
proper
d
of
G
if the sets in
ˆ
(
V
):=
v∈V
ˆ
(
v
) are pairwise
contact representation
(PCR) in
R
interiorly disjoint and (
u,v
)
1)-dimensional. Usually, the as-
signed sets are compact and path-connected and in this paper regular polytopes. A PCR
C
∈
E
⃒⃐
S
u
∩
S
v
is (
d
−
are congruent. This means for UPCR with regu-
lar
n
-gons, the polygons (in a component of
G
) can be transformed into one another by
translations for even
n
, and by translations and rotation by
ˀ
for odd
n
. In particular, we
consider UPCRs of squares (USqPCR), cubes (UCuPCR) and triangles (UTriPCR). We
define a
unit square
in
is called
unit
(UPCR), if all sets in
C
2
by its characteristic corner (
x, y
) as
S
(
x, y
):=[
x, x
+1]
R
×
d
as
Q
(
x
):=[
x
1
,x
1
+1]
[
y,y
+1], and analogously, a
unit
d
-cube
in
[
x
d
,x
d
+1].
Further, we define an upward and downward
unit triangle
with height
h
:= sin(
3
) as
R
×
...
×
