11institutetext: Institut für Informatik, Universität Würzburg, Würzburg,
Germany
<EMAIL_ADDRESS>
# Hypergraph Representation via Axis-Aligned Point-Subspace Cover

Oksana Firman 11 0000-0002-9450-7640 Joachim Spoerhase 11 0000-0002-2601-6452

###### Abstract

We propose a new representation of $k$-partite, $k$-uniform hypergraphs (i.e.
a hypergraph with a partition of vertices into $k$ parts such that each
hyperedge contains exactly one vertex of each type; we call them
$k$-hypergraphs for short) by a finite set $P$ of points in $\mathbb{R}^{d}$
and a parameter $\ell\leq d-1$. Each point in $P$ is covered by
$k={d\choose\ell}$ many axis-aligned affine $\ell$-dimensional subspaces of
$\mathbb{R}^{d}$, which we call $\ell$-subspaces for brevity. We interpret
each point in $P$ as a hyperedge that contains each of the covering
$\ell$-subspaces as a vertex. The class of $(d,\ell)$-hypergraphs is the class
of $k$-hypergraphs that can be represented in this way, where
$k={d\choose\ell}$. The resulting classes of hypergraphs are fairly rich:
Every $k$-hypergraph is a $(k,k-1)$-hypergraph. On the other hand,
$(d,\ell)$-hypergraphs form a proper subclass of the class of all
$d\choose\ell$-hypergraphs for $\ell<d-1$.

In this paper we give a natural structural characterization of
$(d,\ell)$-hypergraphs based on vertex cuts. This characterization leads to a
polynomial-time recognition algorithm that decides for a given
$d\choose\ell$-hypergraph whether or not it is a $(d,\ell)$-hypergraph and
that computes a representation if existing. We assume that the dimension $d$
is constant and that the partitioning of the vertex set is prescribed.

##  1 Introduction

#### Motivation and Related Work.

Geometric representations of graphs or hypergraphs is a wide and intensively
studied field of research in particular in the geometric context. Well-known
examples are geometric intersection or incidence graphs with a large body of
literature [16, 6, 17]. The benefit of studying geometric graph
representations is two-fold. On the one hand, knowing that a given graph can
be represented geometrically may give new insights because the geometric
perspective is often more intuitive. On the other hand, giving a graphical
characterization for certain types of geometric objects may help pin down the
essential combinatorial properties that can be exploited in the geometric
setting.

One example of this interplay is the study of geometric set cover and hitting
set problems [2, 18, 3]. In this important branch of geometric optimization,
incidence relations of two types of geometric objects are studied where one
object type is represented by vertices of a hypergraph whose hyperedges are,
in turn, represented by the other object type. In this representation a vertex
is contained in a hyperedge if and only if the corresponding geometric objects
have a certain geometric relation such as containment or intersection. The
objective is to find the minimum number of nodes hitting all hyperedges111For
the sake of presentation, we use here the representation as hitting set
problem rather than the equivalent and maybe more common geometric set cover
interpretation.. In this line of research, the goal is to exploit the geometry
in order to improve upon the state of the art for general hypergraphs. This is
known to be surprisingly challenging even in many seemingly elementary
settings.

For example, in the well-studied point line cover problem [11, 14] we are
given a set of points in the plane and a set of lines. The goal is to identify
a smallest subset of the lines to cover all the points. This problem can be
cast as a hypergraph vertex cover problem. Points can be viewed as hyperedges
containing the incident lines as vertices. The objective is to cover all the
hyperedges by the smallest number of vertices.

It seems quite clear that point line cover instances form a heavily restricted
subclass of general hypergraph vertex cover. For example, they have the
natural intersection property that two lines can intersect in at most one
point. However, somewhat surprisingly, in terms of approximation algorithms,
no worst-case result improving the ratios for general hypergraph vertex cover
[1, 10, 5] is known. In fact, it has been shown that merely exploiting the
above intersection property in the hypergraph vertex cover is not sufficient
to give improved approximations [15]. Giving a simple combinatorial
characterization of the point line cover instances seems to be challenging.

In this paper, we study a representation of hypergraphs that arises from a
natural variant of point line cover where we want to cover a given set $P$ of
points in $\mathbb{R}^{d}$ by axis-parallel lines, see Fig. 1 for an
illustration. While the axis-parallel case of point line cover has been
considered before [9] the known algorithms do not improve upon the general
case of hypergraph vertex cover [1, 5]. More generally, we investigate the
generalization where we are additionally given a parameter $\ell\leq d-1$ and
we would like to cover $P$ by axis-aligned affine $\ell$-dimensional subspaces
of $\mathbb{R}^{d}$, which we call $\ell$-subspaces. The resulting classes of
hypergraphs is fairly rich as any $k$-partite $k$-uniform hypergraph (i.e. a
hypergraph with a partition of vertices into $k$ parts such that each
hyperedge contains exactly one vertex of each type) can be represented by a
set of points in $\mathbb{R}^{k}$ to be covered by $(k-1)$-subspaces. On the
other hand for $\ell<d-1$ we obtain proper subclasses of all $k$-hypergraphs.

We remark that our representation does not exploit the geometry of the
Euclidean $\mathbb{R}^{d}$. Rather, the representation can also be considered
on a hypercube $X^{d}$ for some set $X$ where subspaces are subsets of $X^{d}$
fixing certain coordinates. We feel that the usage of the geometric language
is more intuitive.

(a)

(b)

Figure 1: A graph (1(a)) and a hypergraph (1(b)) and their representations in
2D and 3D, respectively.

#### Related Work.

The question of representing (hyper-)graphs geometrically is related to the
area of graph drawing. For example, Evans et al. [8] study drawing hypergraphs
in 3D by representing vertices as points and hyperedges as convex polygons
while preserving incidence relations. Note that in our work we study the
“dual” where hyperedges are represented as points and vertices are represented
as axis-parallel lines or affine subspaces. Another related problem in graph
drawing has been introduced by Chaplick et al. [4]. They study drawings of
graphs on the plane or in higher dimension so that the vertices (and the edges
in some variants) of the graph can be covered by a minimum number of lines or
hyperplanes.

#### Our Contribution and Outlook.

To the best of our knowledge, we are the first to study the representation of
$k$-hypergraphs via axis-aligned point subspace cover instances in this
generality. Our main insight is that the axis-aligned case of point subspace
cover allows for a natural, combinatorial characterization contrasting what is
known for the non-aligned (see discussion above). The characterization is
based on vertex cuts and can be leveraged to obtain a polynomial time
recognition algorithm for such hypergraphs assuming the dimension $d$ is a
constant and that we are given the partition of the vertices (which is NP-hard
to compute for $k\geq 3$ [13]).

We believe that it is an interesting research direction to exploit these
combinatorial properties in order to obtain improved results for various
optimization problems in hypergraphs such as hypergraph vertex cover or
hypergraph matching. We also hope that our combinatorial characterization may
help make progress on geometric problems. We conclude our paper by an outlook
containing related open questions and some first small motivating results in
this direction.

##  2 Point Line Cover and Hypergraph Representation

For the sake of an easier presentation, we first describe the result for the
special case of point line covers, that is, for $(d,1)$-hypergraphs. We later
describe how the result generalizes to higher-dimensional axis-aligned affine
subspaces. Generally, we use $d,\ell$ to denote the dimensions of the
(sub-)space and $k={d\choose\ell}$ to denote the number of parts in the
corresponding hypergraph. For the special case of point line cover considered
in this section we have $k=d$.

Let $P$ be a finite set of points in $\mathbb{R}^{k}$. We define the
$k$-hypergraph $G_{P}$ as follows. The vertex set of $G_{P}$ is the set of
axis-parallel lines containing at least one point in $P$. The hyperedges in
$G_{P}$ correspond to the points in $P$ where the hyperedge corresponding to
some $p\in P$ contains the $k$ axis-parallel lines incident on $p$ as
vertices. Note that $G_{P}$ is $k$-partite and $k$-uniform (that is $G_{P}$ is
a $k$-hypergraph) where the $k$ parts of the partition correspond to the $k$
dimensions.

Our main task is to decide for a given hypergraph $G$ whether there is a point
line cover instance $P$ such that $G$ and $G_{P}$ are isomorphic. We say that
$G$ is represented by $P$ and, thus, representable. We assume that the
partition of $G$ into $k$ parts is given.

More formally, we want to compute for a given $k$-hypergraph $G=(V=V_{1}\cup
V_{2}\cup,\ldots,\cup V_{k},E)$ a point line cover instance $P$ such that each
$e=(v_{1},\ldots,v_{k})\in E$ corresponds to some
$p^{e}=(x^{e}_{1},\ldots,x^{e}_{k})\in P$ and where $v_{i}\in V_{i}$
corresponds to the line $\ell^{v_{i}}$ that is parallel to the $i$-th
coordinate axis and contains $p_{e}$, that is, for all $j\neq i$, we fix the
coordinates $x^{e}_{j},j\neq i$ whereas the $i$th coordinate is free, see Fig.
1 for examples.

We remark that every bipartite graph is representable in $\mathbb{R}^{2}$
because we can derive a grid-like representation as shown in Fig. 1(a)
directly from the adjacency matrix of this graph. However, for $k\geq 3$ the
class of $(k,1)$-hypergraphs forms a non-trivial subclass of all
$k$-hypergraphs.

##  3 Characterization of Representable Hypergraphs

We use the notation $[k]=\\{1,\ldots,k\\}$ for $k\in\mathbb{N}$. Let
$G=(V=V_{1}\cup\dots\cup V_{k},E)$ be a $k$-hypergraph.

###### Definition 1

Let $s,t\in V$. An $s$–$t$ path is a sequence of vertices
$s=v_{1},\ldots,v_{r}=t$ such that $v_{i}$ and $v_{i+1}$ are both contained in
some hyperedge $e\in E$ for all $i\in[r-1]$. Similarly, if $e,e^{\prime}\in E$
then an $e$–$e^{\prime}$ path is a $v$–$v^{\prime}$ path such that $v\in e$
and $v^{\prime}\in e^{\prime}$.

The following two separability conditions based on vertex cuts are key for our
characterization.

######  Definition 2 (Vertex separability)

For a given $k$-hypergraph $G$ we say that two distinct vertices $v$ and
$v^{\prime}$ from the same part $V_{i}$, $i\in[k]$ are separable if there
exists some $j\in[k]$ with $j\neq i$ such that every $v$–$v^{\prime}$ path
contains a vertex in $V_{j}$. (Informally, removing $V_{j}$ from the vertex
set and from the edges separates $v$ and $v^{\prime}$.) A hypergraph is called
vertex-separable if every two vertices from the same part are separable.

######  Definition 3 (Edge separability)

For a given $k$-hypergraph $G$ we say that two distinct hyperedges $e$ and
$e^{\prime}$ are separable if there exists some $j\in[k]$ such that every
$e$–$e^{\prime}$ path contains a vertex in $V_{j}$. A hypergraph is called
edge-separable if every two hyperedges are separable.

Note that any pair of hyperedges sharing two or more vertices are not
separable. Therefore, edge-separable hypergraphs do not contain such hyperedge
pairs.

###### Lemma 1

For any given $k$-hypergraph, vertex separability implies edge separability.

###### Proof

Assume that a given $k$-hypergraph $G$ is not edge-separable. This means that
there are two distinct hyperedges $e$ and $e^{\prime}$ that are not separable.
Then $\forall j\in[k]$ there is an $e$–$e^{\prime}$ path that does not contain
a vertex from $V_{j}$. Because $e$ and $e^{\prime}$ are distinct, there are
distinct vertices $v$ and $v^{\prime}$ with $v\in e$ and $v^{\prime}\in
e^{\prime}$ from the same part $V_{i}$ for some $i\in[k]$. Now, for each
$j\in[k]$, $j\neq i$ there exists an $e$–$e^{\prime}$ path $\pi_{j}$ that does
not contain any vertex from $V_{j}$. But then $v,\pi_{j},v^{\prime}$ forms a
$v$–$v^{\prime}$ path not containing any vertex from $V_{j}$. This means that
$G$ is not vertex-separable.

Figure 2: A hypergraph $G$ (on the left) that is edge-separable, but not
vertex-separable (the vertices $v$ and $v^{\prime}$ from $V_{2}$ are not
separable). In a hypothetical representation of $G$ (on the right), the line
$\ell^{v^{\prime}}$ must simultaneously intersect $\ell^{u^{\prime}}$ and
$\ell^{w^{\prime}}$ and therefore must be equal to $\ell^{v}$—a contradiction.

The converse is not true, see Fig. 2. In the instance depicted, the two red
edges containing $v$,$u$ and $u^{\prime}$, $v^{\prime}$ or the two black edges
containing $v$, $w$ and $w^{\prime}$, $v^{\prime}$, for example, are separated
by removing the blue vertex part $V_{2}$ (which we can not do to show that
vertices $v$ and $v^{\prime}$ are separable).

###### Definition 4

Let $G$ be a $k$-hypergraph. For each $i\in[k]$ we construct a graph
$G_{i}=(E,E_{i})$ as follows: $e$ and $e^{\prime}\in E$ are adjacent if and
only if $e$ and $e^{\prime}$ have a common vertex in a part $V_{j}$ with
$j\neq i$.

In the following theorem we state our characterization of $k$-hypergraphs
representable by point line covers via vertex separability.

###### Theorem 3.1

A $k$-hypergraph $G$ is representable if and only if it is vertex-separable.

###### Proof

We construct for each hyperedge $e$ a point $p^{e}\in\mathbb{R}^{k}$ and for
each vertex $v_{i}\in V_{i}$ with $i\in[k]$ a line
$\ell^{v_{i}}\subseteq\mathbb{R}^{k}$ that is parallel to the $x_{i}$-axis. We
do this as follows. For $G$ we construct the graphs $G_{i}$, $i\in[k]$. For
each graph $G_{i}$, $i\in[k]$ we consider the connected components of $G_{i}$
and assign to each connected component a unique (integer) value in
$\\{1,2,\dots,|V(G_{i})|\\}$.

Now, if $p^{e}_{i}$ is the value of the connected component in $G_{i}$ that
contains $e$ then we let the point $p^{e}=(p^{e}_{1},\ldots,p^{e}_{k})$
represent the hyperedge $e$, see Fig. 3 for an example.

Recall that any line parallel to the $x_{i}$-axis can be defined by fixing its
$x_{j}$-coordinate for all $j\neq i$, while leaving $x_{i}$ free. Now, if the
hyperedge $e=\\{v_{1},\ldots,v_{k}\\}$ is represented by
$p^{e}=(p^{e}_{1},\ldots,p^{e}_{k})$ then for each $i\in[k]$, the line
$\ell^{v_{i}}$ that represents the vertex $v_{i}$ is defined by coordinates
$p^{e}_{j}$, $j\neq i$ while leaving the $x_{i}$-coordinate free, see Fig. 3.
It is important to note, that the representation $\ell^{v_{i}}$ is well-
defined although $v_{i}$ may be contained in multiple hyperedges in $G$. This
follows from the fact that all the hyperedges containing $v_{i}$ belong to the
same connected component in $G_{j}$, $j\in[k]$, $j\neq i$ because each pair of
them is joined by some edge in $G_{j}$ corresponding to $v_{i}$ and in
particular these hyperedges form a clique. Therefore, there is no disagreement
in the $x_{j}$-coordinate where $j\neq i$. Hence, we uniquely define the
coordinates that determine a line.

$(\Leftarrow)$ Assume that $G$ is vertex-separable. By the construction of the
point line cover instance we have:

  * •

every point $p^{e}$ is in fact covered by the lines
$\ell^{v_{1}},\ldots,\ell^{v_{k}}$ where $e=\\{v_{1},\ldots,v_{k}\\}$, because
by construction every line $\ell^{v_{i}}$ and point $p^{e}$ have the same
$x_{j}$-coordinate with $j\neq i$.

  * •

$\forall v\neq v^{\prime}\in V$ it holds that $\ell^{v}\neq\ell^{v^{\prime}}$.
This is obviously true if vertices belong to different parts, because then the
free coordinate of $v$ is fixed for $v^{\prime}$ and vice versa. If
$v,v^{\prime}\in V_{i}$ for some $i\in[k]$ then, by vertex separability, there
exists $j\neq i$ such that $v$ and $v^{\prime}$ are not connected in graph
$G_{j}$ and get different $x_{j}$-coordinates. So they represent distinct
lines.

  * •

$\forall e\neq e^{\prime}\in E$ it holds that $p^{e}\neq p^{e^{\prime}}$.
Indeed, by Lemma 1, $G$ is edge-separable and by definition of edge
separability (see Def. 3) distinct hyperedges are not connected in at least
one graph $G_{i}$ and get different $x_{i}$-coordinates. So they represent
distinct points.

Figure 3: The graphs $G_{1},G_{2},G_{3}$ and the coordinates of the points and
lines corresponding to the hyperedges and vertices. The dots instead of
coordinates mean that those coordinates are free.

By the above construction, for every incident vertex-hyperedge pair $v\in
V,e\in E$, that is, $v\in e$, the corresponding geometric objects $\ell^{v}$
and $p^{e}$ are incident as well. We claim that if $v$ and $e$ are not
incident, that is, $v\notin e$ then $\ell^{v}$ and $p^{e}$ are not incident as
well. This is because every point $p^{e}$ is already incident to precisely $k$
lines $\ell^{v}$ by construction, because the lines $\ell^{v}$ are pairwise
distinct, and because $p^{e}$ cannot be incident on more than $k$ axis-
parallel lines. Thus we constructed a point line cover instance that
represents the hypergraph $G$ and this means that $G$ is representable.

$(\Rightarrow)$ Assume that $G$ is not vertex-separable but that it has a
point line cover representation. This means that it contains at least two
distinct vertices $v$ and $v^{\prime}$ from the same part $V_{i}$ that are not
separable. Then for each part $V_{j}$ with $j\neq i$, there exists a
$v$–$v^{\prime}$ path $v=v_{1},\dots,v_{r}=v^{\prime}$ such that $v_{t}\notin
V_{j}$ for each $t\in[r]$. All lines $\ell^{v_{t}}$ with $t\in[r]$ that
represent the vertices $v_{1},\ldots,v_{r}$ lie on the same hyperplane $H_{j}$
perpendicular to the $x_{j}$-axis. This is because successive line pairs are
joined by a common point (representing the hyperedge containing both) and
since none of these lines is parallel to the $x_{j}$-axis and so the
$x_{j}$-coordinate stays fixed. Since this holds for all $j\in[k]$, $j\neq i$,
the lines $\ell^{v}$ and $\ell^{v^{\prime}}$ lie in the intersection
$\bigcap\limits_{j\neq i}H_{j}$. But the intersection of such hyperplanes is a
single line. This contradicts that $v$ and $v^{\prime}$ correspond to the
distinct lines.

Note that our characterization in Theorem 3.1 directly gives rise to an
efficient recognition algorithm to check whether or not a given $k$-hypergraph
is representable. We check for every vertex pair from the same part whether
they are vertex-separable.

Below we give an algorithm to actually compute a representation for a given
$k$-hypergraph (or output that a representation does not exist). The algorithm
is an algorithmic implementation of the construction used in the proof Theorem
3.1 to recover a representation from a given (representable) $k$-hypergraph.

#### Computing a representation.

For each $i\in[k]$ we compute a graph $G_{i}$ as in Definition 4. We use the
construction from the proof of Theorem 3.1 to assign the coordinates for all
points and lines (using connected components of $G_{i}$). In particular, we
uniquely number the connected components of each graph $G_{i}$, $i\in[k]$.
Then for any hyperedge $e$ we construct the point $p^{e}$ whose $i$-th
coordinate is the number of the connected component containing $e$ in $G_{i}$.
Based on the representation of the hyperedges we can easily obtain the
representation of the vertices as lines as well. To verify if the resulting
candidate representation is in fact valid, we have to check if any two points
$p^{e},p^{e^{\prime}}$ representing distinct hyperedges $e,e^{\prime}$ are in
fact distinct, that is, differ in at least one coordinate. Similarly, we have
to check distinctness of the lines. If this is the case then the hypergraph
$G$ is representable and we get the point line cover instance corresponding to
$G$.

Constructing a point line cover instance for a given hypergraph can be done in
$\mathcal{O}(k\cdot m^{2})$, where $m$ is the number of hyperedges. Checking
distinctness of the vertex and edge representation takes
$\mathcal{O}(k\cdot(m\log m+n\log n))$ using lexicographic sorting, where $n$
is the number of vertices. In total the runtime of the algorithm is
$\mathcal{O}(k\cdot(m^{2}+n\log n))$.

Notice that there are infinitely many instances corresponding to the same
hypergraph.

##  4 Generalization to Point Subspace Cover

In this section, we generalize the previous result for $(d,1)$-hypergraphs to
the general case of $(d,\ell)$-hypergraphs. That is, we want to characterize
$k$-hypergraphs (where $k={d\choose\ell}$) that are representable as sets of
points in $\mathbb{R}^{d}$ covered by $\ell$-dimensional axis-aligned
subspaces where $1\leq\ell\leq d-1$ and $d\geq 2$. Notice that such an axis-
aligned subspace is equal to the set of $d$-dimensional vectors for which
$d-\ell$ coordinates are fixed and $\ell$ coordinates are free. Note that in
the case $\ell=d-1$ every $k$-hypergraph is representable analogously to the
case of bipartite graphs each of which is representable in dimension two. This
follows immediately from our characterization below but can also be seen in a
direct way analogously to the two-dimensional setting.

For each $\ell\leq d-1$ the class of $(d,\ell)$-hypergraphs forms a subclass
of $k$-hypergraphs (where $k={d\choose\ell}$). Every part of the vertex
partition in the hypergraph represents a set of $\ell$-subspaces that have the
same free coordinates. In what follows we assume that we know the labeling of
the parts of the hypergraph. That is, we assume that for each part of the
hypergraph we know to which $\ell$-subset $I$ of free coordinates this part
corresponds; we write $V_{I}$ to denote this correspondence. To this end, we
guess the correct labeling in a brute force fashion by checking all $O(d^{\ell
d^{\ell}})$ many labelings if it satisfies the characterization for fixed
labeling as described below.

The below definitions and proofs are natural generalizations of the ones for
$(d,1)$-hypergraphs. In the case of $\ell=1$ the idea of separability is
related to cutting the part $V_{j}$ of the graph corresponding to some
coordinate $j\in[k]$. The key idea in the generalized setting is to cut
instead all parts $V_{I}$ that contain a specific coordinate $j$. Below, we
give the full definitions and proofs, which are along the lines of $\ell=1$
but rather use the generalized concept of cuts and separability.

#### Generalization of the vertex separability property

Let ${[d]\choose\ell}$ denote the family of subsets of $[d]$ of cardinality
$\ell$. Note that there are exactly $d\choose\ell$ such sets. For a given
$d\choose\ell$-hypergraph $G$ and for all $I\in{[d]\choose\ell}$ we define the
part $V_{I}$ to be a set of subspaces, in which the coordinates with numbers
from $I$ are free. Now we generalize the vertex separability property using
the definition of a path (Def. 1 from section 3).

######  Definition 5 (Vertex separability)

For a given $d\choose\ell$-hypergraph $G$ two distinct vertices $v$ and
$v^{\prime}$ from the same part $V_{I}$ where $I\in{[d]\choose\ell}$ are
separable if there exists a free coordinate $j\in[d]$, that is not free in
$V_{I}$ such that every $v$-$v^{\prime}$ path contains a vertex in one of the
$d-1\choose\ell-1$ parts that share the free coordinate $j$. (Informally,
removing all those $d-1\choose\ell-1$ parts from the vertex set and from the
hyperedges separates $v$ and $v^{\prime}$.) A hypergraph is called vertex-
separable if every two vertices from the same part are separable.

In an analogous way we can generalize edge separability and Lemma 1 that
vertex separability implies edge separability.

######  Definition 6 (Edge separability)

For a given $d\choose\ell$-hypergraph $G$ two distinct hyperedges $e$ and
$e^{\prime}$ are separable if there exists a free coordinate $j\in[d]$ such
that every $e$–$e^{\prime}$ path contains a vertex in one of the
$d-1\choose\ell-1$ parts that share the free coordinate $j$. A hypergraph is
called edge-separable if every two hyperedges are separable.

###### Lemma 2

For any given ${d\choose\ell}$-hypergraph where $\ell\leq d-1$, vertex
separability implies edge separability.

###### Proof

Assume that a given $d\choose\ell$-hypergraph $G$ is not edge-separable. This
means that there are two distinct hyperedges $e$ and $e^{\prime}$ that are not
separable. Then $\forall j\in[d]$ there is an $e$–$e^{\prime}$ path that does
not contain a vertex from any of the $d-1\choose\ell-1$ parts that share the
free coordinate $j$. Because $e$ and $e^{\prime}$ are distinct, there are
distinct vertices $v$ and $v^{\prime}$ with $v\in e$ and $v^{\prime}\in
e^{\prime}$ from the same part $V_{I}$ for some $I\in{[d]\choose\ell}$. Now,
for each $j\in[d]$, that is not free in $V_{I}$, there exists an
$e$–$e^{\prime}$ path $\pi_{j}$ that does not contain a vertex from any of the
$d-1\choose\ell-1$ parts that share the free coordinate $j$. But then
$v,\pi_{j},v^{\prime}$ forms a $v$–$v^{\prime}$ path not containing a vertex
from any of the mentioned parts. This means that $G$ is not vertex-separable.

As was already mentioned in the previous section, the converse is not true,
see Fig. 2.

###### Definition 7

For a $d\choose\ell$-hypergraph $G$ we construct a graph $G_{i}=(E,E_{i})$ for
each $i\in[d]$ as follows: $e$ and $e^{\prime}\in E$ are adjacent iff $e$ and
$e^{\prime}$ have a common vertex in a part $V_{I}$ where
$I\in{[d]\choose\ell}$ and $i\notin I$.

###### Theorem 4.1

A $d\choose\ell$-hypergraph $G$ is representable if and only if it is vertex-
separable.

###### Proof

The proof is a natural generalization of the proof for line case.

We construct for each hyperedge $e$ a point $p^{e}\in\mathbb{R}^{d}$ and for
each vertex $v_{I}\in V_{I}$ with $I\in{[d]\choose\ell}$ a subspace
$\ell^{v_{I}}\in\mathbb{R}^{d}$ that is parallel to all $x_{i}$-axis where
$i\in I$. We do this as follows. For $G$ we construct the graphs $G_{i}$,
$i\in[d]$. For each graph $G_{i}$ we consider the connected components of the
graph and assign to each of them a unique (integer) value.

Now, if $p^{e}_{i}$ is the value of the connected component in $G_{i}$ that
contains $e$ then we let the point $p^{e}=(p^{e}_{1},\ldots,p^{e}_{d})$
represent the hyperedge $e$, see Fig. 3 for an example.

Recall that any subspace parallel to all $x_{i}$-axis where $i\in I$ can be
defined by fixing its $x_{j}$-coordinate $j\neq i$, while leaving $x_{i}$
coordinates free. Now, if the hyperedge $e=\\{v_{I}\\}$ for all
$I\in{[d]\choose\ell}$ is represented by $p^{e}=(p^{e}_{1},\ldots,p^{e}_{d})$
then for each $I\in{[d]\choose\ell}$, the subspace $\ell^{v_{I}}$ that
represents the vertex $v_{I}$ is defined by coordinates $p^{e}_{j}$, $j\notin
I$ while leaving the $x_{i}$-coordinates free. It is important to note, that
the representation $\ell^{v_{I}}$ is well-defined although $v_{I}$ may be
contained in multiple hyperedges in $G$. This follows from the fact that all
the hyperedges containing $v_{I}$ belong to the same connected component in
$G_{j}$, $j\in[d]$ because each pair of them is joined by some edge in $G_{j}$
corresponding to $v_{I}$ and in particular these hyperedges form a clique.
Therefore, there is no disagreement in the $x_{j}$-coordinate where $j\neq i$
for all $i\in I$. Hence, we uniquely define the coordinates that determine a
subspace.

$(\Leftarrow)$ Assume that $G$ is vertex-separable. By the construction of the
point subspace cover instance we have:

  1. 1.

every point $p^{e}$ is in fact covered by the lines $\ell^{v_{I}}$ where
$e=\\{v_{I}\\}$ for all $I\in{[d]\choose\ell}$. This is because by
construction every line $\ell^{v_{I}}$ and point $p^{e}$ have the same
$x_{j}$-coordinate with $j\notin I$.

  2. 2.

$\forall v\neq v^{\prime}\in V$ it holds that $\ell^{v}\neq\ell^{v^{\prime}}$.
This is obviously true if vertices belong to different parts, because then
there exist at least one free coordinate of $v$ that is fixed for $v^{\prime}$
and vice versa. If $v,v^{\prime}\in V_{I}$ for some $I\in{[d]\choose\ell}$
then, by vertex separability, there exists $j\notin I$ such that $v$ and
$v^{\prime}$ are not connected in graph $G_{j}$ and get different
$x_{j}$-coordinates. So they represent distinct subspaces.

  3. 3.

$\forall e\neq e^{\prime}\in E$ it holds that $p^{e}\neq p^{e^{\prime}}$.
Indeed, by Lemma 2, $G$ is edge-separable and by the definition of edge
separability (see Def. 6) distinct hyperedges are not connected in at least
one graph $G_{i}$ and get different $x_{i}$-coordinates. So they represent
distinct points.

By the above construction, for every incident vertex-hyperedge pair $v\in
V,e\in E$, that is, $v\in e$, the corresponding geometric objects $\ell^{v}$
and $p^{e}$ are incident as well. We claim that if $v$ and $e$ are not
incident, that is, $v\notin e$ then $\ell^{v}$ and $p^{e}$ are not incident as
well. This is because every point $p^{e}$ is already incident to precisely
$d\choose\ell$ subspaces $\ell^{v}$ by construction, because the subspaces
$\ell^{v}$ are pairwise distinct, and because $p^{e}$ cannot be incident on
more than $d\choose\ell$ axis-parallel subspaces. Thus we constructed a point
subspace cover instance that represents the hypergraph $G$ and this means that
$G$ is representable.

$(\Rightarrow)$ Assume that $G$ is not vertex-separable but that it has a
point subspace cover representation. This means that it contains at least two
distinct vertices $v$ and $v^{\prime}$ from the same part $V_{I}$ that are not
separable. Then for each coordinate $j\notin I$, there exists a
$v$-$v^{\prime}$ path such that none of the vertices on this path has $j$ as a
free coordinate. All subspaces that represent the vertices from the path lie
in the same hyperplane $H_{j}$ perpendicular to the $x_{j}$-axis, i.e.
$x_{j}$-coordinate is fixed and all others are free. This is because
successive subspace pairs are joined by a common point (representing the
hyperedge containing both). Since none of these subspaces is parallel to the
$x_{j}$-axis the $x_{j}$-coordinate stays fixed. Since this holds for all
$j\in[d]$, such that $j\notin I$, the subspaces $\ell^{v}$ and
$\ell^{v^{\prime}}$ lie in the intersection $\bigcap\limits_{j\notin
I}{}H_{j}$. But the intersection of such hyperplanes is a single subspace that
has all coordinates $i\in I$ free. This contradicts that $v$ and $v^{\prime}$
correspond to the distinct subspaces.

Analogously to $(d,1)$-case the above proof leads directly to an algorithm
computing a representation (or notifying about non-existence). A naive
implementation of this algorithm gives a running time of $O(d^{\ell
d^{\ell}+2}(m^{2}+n\log n))$ where the exponential factor in $d$ comes from
guessing the labeling of the parts. It is a very interesting question if the
exponential dependence on $d$ can be removed to get a polynomial algorithm
also for non-constant $d$.

##  5 Conclusion and Outlook

In this paper, we have introduced the class of $(d,\ell)$-hypergraphs forming
a natural class of $k$-hypergraphs. We have given an efficiently checkable
simple characterization of this class based on vertex cuts. The first question
that is still open: Is there a polynomial time recognition algorithm of
$(d,\ell)$-hypergraphs for non-constant $d$?

In Appendix 0.A, we propose possible future research directions. There is a
large body of literature in algorithms and graph theory on hypergraph
problems. This motivates the following two questions

  1. 1.

Can the structure of $(d,\ell)$-hypergraphs be leveraged in (optimization)
problems for hypergraphs such as matching or vertex cover?

  2. 2.

What is the relation to other classes of hypergraphs (for example
geometrically representable hypergraphs)?

For example, maximum matching in $k$-hypergraphs is a very well-studied
problem still exhibiting large gaps in our current understanding [7, 12].
Another example is hypergraph vertex cover for which tight approximability
results are known [10] on general $k$-hypergraphs. While the problem has been
considered on $(k,1)$-hypergraphs before [9] (from the geometric perspective
of point-line covering) no improvement upon the general case is known. We hope
that our structural characterization can help obtaining such improvements. In
Appendix 0.A, we state some first small results opening up these lines of
research, namely we showed that matching on (3,1)-hypergraphs is NP-hard and
considered the relation of $(d,1)$-hypergraphs to point line cover
representations on the plane where we drop the requirement of axis-alignment.
We hope that our structural characterization helps make progress on these
questions.

## References

  * [1] R. Aharoni, R. Holzman, and M. Krivelevich.  On a theorem of lovász on covers in tau-partite hypergraphs.  Comb., 16(2):149–174, 1996.  doi:10.1007/BF01844843.
  * [2] H. Brönnimann and M. T. Goodrich.  Almost optimal set covers in finite vc-dimension.  Discret. Comput. Geom., 14(4):463–479, 1995.  doi:10.1007/BF02570718.
  * [3] T. M. Chan, E. Grant, J. Könemann, and M. Sharpe.  Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling.  In Y. Rabani, editor, Proc. Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12), pages 1576–1585. SIAM, 2012.  doi:10.1137/1.9781611973099.125.
  * [4] S. Chaplick, K. Fleszar, F. Lipp, A. Ravsky, O. Verbitsky, and A. Wolff.  Drawing graphs on few lines and few planes.  In Y. Hu and M. Nöllenburg, editors, Proc. 24th International Symposium on Graph Drawing and Network Visualization (GD’16), volume 9801 of Lecture Notes in Computer Science, pages 166–180. Springer, 2016.  doi:10.1007/978-3-319-50106-2\\_14.
  * [5] V. Chvátal.  A greedy heuristic for the set-covering problem.  Math. Oper. Res., 4(3):233–235, 1979.  doi:10.1287/moor.4.3.233.
  * [6] H. S. M. Coxeter.  Self-dual configurations and regular graphs.  Bull. Amer. Math. Soc., 56(5):413–455, 09 1950.
  * [7] M. Cygan.  Improved approximation for 3-dimensional matching via bounded pathwidth local search.  In Proc. 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS’13), pages 509–518. IEEE Computer Society, 2013.  doi:10.1109/FOCS.2013.61.
  * [8] W. S. Evans, P. Rzazewski, N. Saeedi, C. Shin, and A. Wolff.  Representing graphs and hypergraphs by touching polygons in 3D.  In D. Archambault and C. D. Tóth, editors, Proc.27th International Symposium on Graph Drawing and Network Visualization (GD’19), volume 11904 of Lecture Notes in Computer Science, pages 18–32. Springer, 2019.  doi:10.1007/978-3-030-35802-0\\_2.
  * [9] D. R. Gaur and B. Bhattacharya.  Covering points by axis parallel lines.  In Proc. 23rd European Workshop on Computational Geometry (EuroCG’07), pages 42–45. Citeseer, 2007.
  * [10] V. Guruswami and R. Saket.  On the inapproximability of vertex cover on k-partite k-uniform hypergraphs.  In S. Abramsky, C. Gavoille, C. Kirchner, F. M. auf der Heide, and P. G. Spirakis, editors, Proc. 37th International Colloquium on Automata, Languages and Programming (ICALP’10), volume 6198 of Lecture Notes in Computer Science, pages 360–371. Springer, 2010.  doi:10.1007/978-3-642-14165-2\\_31.
  * [11] R. Hassin and N. Megiddo.  Approximation algorithms for hitting objects with straight lines.  Discret. Appl. Math., 30(1):29–42, 1991.  doi:10.1016/0166-218X(91)90011-K.
  * [12] E. Hazan, S. Safra, and O. Schwartz.  On the complexity of approximating k-set packing.  Comput. Complex., 15(1):20–39, 2006.  doi:10.1007/s00037-006-0205-6.
  * [13] L. Ilie, R. Solis-Oba, and S. Yu.  Reducing the size of NFAs by using equivalences and preorders.  In A. Apostolico, M. Crochemore, and K. Park, editors, Combinatorial Pattern Matching, pages 310–321. SV, 2005.  doi:10.1007/11496656_27.
  * [14] S. Kratsch, G. Philip, and S. Ray.  Point line cover: The easy kernel is essentially tight.  In C. Chekuri, editor, Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14), pages 1596–1606. SIAM, 2014.  doi:10.1137/1.9781611973402.116.
  * [15] V. S. A. Kumar, S. Arya, and H. Ramesh.  Hardness of set cover with intersection 1.  In U. Montanari, J. D. P. Rolim, and E. Welzl, editors, Proc. International Colloquium on Automata, Languages and Programming (ICALP’00), volume 1853 of Lecture Notes in Computer Science, pages 624–635. Springer, 2000.  doi:10.1007/3-540-45022-X\\_53.
  * [16] T. A. McKee and F. R. McMorris.  Topics in Intersection Graph Theory.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, 1999\.
  * [17] T. Pisanski and M. Randić.  Bridges between geometry and graph theory.  In in Geometry at Work, C.A. Gorini, ed., MAA Notes 53, pages 174–194. America.
  * [18] K. R. Varadarajan.  Weighted geometric set cover via quasi-uniform sampling.  In L. J. Schulman, editor, Proc. 42nd ACM Symposium on Theory of Computing (STOC’10), pages 641–648. ACM, 2010.  doi:10.1145/1806689.1806777.

Appendix

##  Appendix 0.A Outlook

Here we state some first small results using our structural characterization
of $(d,\ell)$-hypergraphs.

###  0.A.1 Complexity of matching on $(3,1)$-hypergraphs

Finding maximum matchings in hypergraphs and in $k$-hypergraphs in particular
is a classic optimization problem. The latter problem is also known as the
$k$-dimensional matching problem. This is a classic NP-hard problem and thus
approximation algorithms have been studied. The currently best approximation
algorithm for $k$-dimensional matching has a ratio $(k+1+\epsilon)/3$ for
arbitrarily small constant $\epsilon>0$ by Cygan [7]. Despite being a very
well-studied problem there is still a big gap to the best known lower bound of
$\Omega(k/\log k)$ on the approximability by Hazan et al. [12].

It is an interesting question if improved results can be obtained for
$(d,\ell)$-hypergraphs. As a first, motivating result we show below that
indeed matching on $(k,1)$-hypergraphs is NP-hard for $k\geq 3$. (For $k=2$
the problem is matching on bipartite graphs and thus easy.)

In the matching problem we are given a $3$-uniform vertex-separable
hypergraph, i.e., a $3$-uniform hypergraph that can be represented as point
line cover instance in 3D. The aim is to find a largest 3-dimensional
matching, that is a set of hyperedges, such that no two have a common vertex.

In terms of point line cover the problem is stated as follows. Given a point
line cover instance in 3D the goal is to find the largest set of points, such
that no two lie on the same axis-parallel line.

We show the NP-hardness of matching on $(3,1)$-hypergraphs by reduction from
independent set problem. Given a graph with $n$ vertices the task is to decide
whether there exists an independent set of size at least $\ell$, that is, a
subset of vertices $I$ with $|I|\geq\ell$, such that no two vertices from $I$
are adjacent. We denote by $\alpha(G)$ the size of a maximum cardinality
independent set.

###### Theorem 0.A.1

The decision version of matching on $(3,1)$-hypergraphs is NP-hard.

###### Proof

Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, we construct in
polynomial time an instance $H$ that has a matching of size at least
$n^{2}-2n+\ell+2m$ if and only if $G$ has an independent set of size at least
$\ell$.

We create such an instance as follows. For every vertex $v\in V$ we create a
vertex path, that is, a path of $2(n-1)$ axis-parallel lines that are
perpendicular to the $z$-axis, see Fig. 5. In the vertex path we introduce a
set $A(v)$ of $n-1$ points of type A (see blue points in the Fig. 5) and a set
$B(v)$ of $n-2$ points of type B (see green squares in the Fig. 5). Note that
$A(v)$ and $B(v)$ form matchings in the set $P(v):=A(v)\cup B(v)$ and that
$A(v)$ is the unique maximum matching in $P(v)$.

Figure 4: A vertex gadget that contains ${n-1}$ blue points (circles) and
$n-2$ green points (squares).

Figure 5: An edge gadget (black) connecting two vertex gadgets (red).

As the next step we introduce an edge gadget. If two vertices $v_{1},v_{2}\in
V$ are adjacent we create an edge path, that is a path of axis-parallel lines
connecting some point in $A(v_{1})$ with some point in $A(v_{2})$, see Fig. 5.
We pick the endpoints of the edge paths so that the edge paths are pairwise
disjoint, which is possible because every vertex $v$ has $|A(v)|=n-1$ and is
incident on at most $n-1$ edges.

Each edge path contains five axis-parallel lines (parallel to different axis,
so that the path does not lie on a plane) and six points as the intersection
of the lines including endpoints of type A from the vertex paths, see Fig. 5.
By inner points we mean points that belong to an edge path but do not belong
to a vertex path. Note that any matching of an edge gadget contains at most
two inner points. Moreover, it can contain two inner points only if at most
one of the endpoints is in this matching.

For an example of the construction of a matching instance from a given graph,
see Fig. 6. Notice that by our construction no two lines overlap and every
vertex path has its own plane perpendicular to $z$-axis.

Figure 6: Illustration of the reduction: a graph (on the left) and a
corresponding point line cover instance (on the right). The input points lie
on the intersections of the lines drawn in the figure.

It remains to prove that $H$ has matching $M$ of size at least
$t=n^{2}-2n+\ell+2m$ if and only if $G$ has an independent set $I$ of size at
least $\ell$.

Assume there is an independent set $I$ of $G$ of size at least $\ell$. In what
follows we construct a matching $M$ of size $t$. If $v\in I$ then we add the
set $A(v)$ to $M$. Otherwise we add $B(v)$ to $M$. Note that this ensures that
for any edge path corresponding to some edge $uv$ in the input graph at most
one of its end points will be included in $M$. This is, because at most one of
the nodes $u,v$ is in $I$. This allows us to add two inner points of each edge
path to $M$. Thus, $|M|=\ell\cdot(n-1)+(n-\ell)\cdot(n-2)+2m$ and this means
that $|M|=t$ as required.

Now, assume conversely that $H$ has a matching $M$ of size at least $t$.
Consider vertex paths of $H$. Observe that if some vertex path $P(v)$ the
matching $M$ contains points both in $A(v)$ and $B(v)$ then $M\cap P(v)$ has
size at most $n-2$. Hence, we can w.l.o.g. assume that $M\cap P(v)=B(v)$. By
this, we can assume that every vertex has either only points of type A or only
points of type B in the matching. Assume that there is an edge path
corresponding to some edge $uv\in E$ where both endpoints are in $M$, that is,
$M\cap P(u)=A(u)$ and $M\cap P(v)=A(v)$. Then this edge path contains only one
inner point that is in $M$. Now we can change the matching $M$ so that $M\cap
P(u)=B(u)$ and so that the edge path contains two points in $M$ without
decreasing the size of $M$ overall. Hence, we can assume that for any edge
$uv\in E$ we do not have $M\cap P(u)=A(u)$ and $M\cap P(v)=A(v)$
simultaneously. We can also assume that any edge path contains two points in
$M$.

Let $I$ be the set of nodes $v\in V$ where $P(v)\cap M=A(v)$. Note that $I$
forms an independent set by our above assumption. Since any edge path contains
two nodes in $M$ the total size of $M$ can be expressed as
$|I|(n-1)+(n-2)(n-|I|)+2m$. This quantity can be at least $t$ only if
$|I|\geq\ell$, which completes the proof.

###  0.A.2 Plane many-directions representations

To address the second research direction mentioned above, we give a first
small result relating the class of $(d,1)$-hypergraphs to other geometrically
represented hypergraphs. Here we consider in particular point line cover
representations on the plane where we drop the requirement of axis-alignment.

#### Obtaining a many-directions representation for a $(d,1)$-hypergraph.

Assume we are given $(d,1)$-hypergraph with an axis-aligned point line
representation $P\subseteq\mathbb{R}^{d}$ in $d$-dimensional space. We create
a point line cover representation on the plane with $d$ distinct directions.
To this end create a random matrix $M\in[0,1]^{2\times d}$ where each entry is
picked uniformly at random from the interval $[0,1]$. Notice that for any two
distinct vectors $x,y\in\mathbb{R}^{d}$ the probability that $Mx=My$ is zero.
Hence, with probability one the set $P^{\prime}=\\{\,Mp\mid p\in
P\,\\}\subseteq\mathbb{R}^{2}$ has cardinality $|P|$. By the same reasoning,
any two non-parallel lines in $\mathbb{R}^{d}$ stay non-parallel under the
mapping induced by $M$. Hence, the axis-parallel lines in $\mathbb{R}^{d}$
covering the points in $P$ are transformed into a set of distinct lines in the
plane using precisely $d$ distinct directions with probability one.

The converse does not hold. For an example of a hypergraph that is not vertex-
separable (thus, does not have a representation in 3D), but is representable
on the plane with 3 directions, see Fig. 7.

Figure 7: A not vertex-separable hypergraph and its representation on the
plane with 3 directions.

Observe that the plane many-directions case is sensitive to the directions we
allow. In the configuration in Fig. 8 there are 4 points and 6 directions of
lines, namely, vertical, horizontal, and slopes 2, -2, 1/2, -1/2. However, it
is not hard to verify that it is not possible to represent an isomorphic
hypergraph with the directions vertical, horizontal, and slopes 2, -2, 1/2,
1/3.

Figure 8: An example of many-directions case with 4 points and 6 directions:
vertical, horizontal, and slopes 2, -2, 1/2, -1/2.