Dushnik-Miller dimension of TD-Delaunay complexes
Daniel Gonçalves Lucas Isenmann


Discrete Morse theory for the collapsibility of supremum sections
    Jeffrey Hatley
    ?; revised ?; accepted ?. - To be entered by editorial office
=================================================================




TD-Delaunay graphs, where TD stands for triangular distance, is a variation of the classical 
Delaunay triangulations obtained from a specific convex distance function <cit.>.
In <cit.> the authors noticed that every triangulation is the TD-Delaunay graph of a set of points in ^2, and conversely every TD-Delaunay graph is planar.  
It seems natural to study the generalization of this property in higher dimensions.  
Such a generalization is obtained by defining an analogue of the triangular distance for ^d.  
It is easy to see that TD-Delaunay complexes of ^d-1 are of Dushnik-Miller dimension d.  
The converse holds for d=2 or 3 and it was conjectured to hold for larger d <cit.> (See also <cit.>).  
Here we disprove the conjecture already for d = 4.
 



§ INTRODUCTION


The order dimension (also known as the Dushnik-Miller dimension) of a poset P has been introduced by Dushnik and Miller <cit.>.
It is the minimum number of linear extensions of P such that P is the intersection of these extensions.
See <cit.> for a comprehensive study of this topic.
Schnyder <cit.> studied the Dushnik-Miller dimension of the incidence posets of graphs.

Some classes of graphs can be characterized by their Dushnik-Miller dimension which is the Dushnik-Miller dimension of their incidence poset.
For example, path forests are the graphs of Dushnik-Miller dimension at most 2.
Schnyder <cit.> obtained a celebrated combinatorial characterization of planar graphs: they are those of Dushnik-Miller dimension at most 3.
The question of characterizing classes of graphs of larger dimension is open.
Nevertheless there are some partial results.
Bayer et al. <cit.> and Ossona de Mendez <cit.> showed that every simplicial complex of Dushnik-Miller dimension d has a straight line embedding in ^d+1 which generalizes the result of Schnyder in a way.
The reciprocal is false by considering K_n which has a straight line embedding in ^3 while it has Dushnik-Miller dimension loglog n <cit.>.
The class of Dushnik-Miller dimension at most 4 graphs is rather rich.
Extremal questions in this class of graphs have been studied: Felsner and Trotter <cit.> showed that these graphs can have a quadratic number of edges.
Furthermore, in order to solve a question about conflict free coloring <cit.>,  Chen et al. <cit.> showed that most of the graphs of Dushnik-Miller dimension 4 only have independent sets of size at most o(n).
This result also implies that there is no constant k such that every graph of Dushnik-Miller dimension at most 4 is k-colorable.
Therefore, graphs of Dushnik-Miller dimension at most 4 seem difficult to characterize. 
Nevertheless, it was conjectured in <cit.> (See also <cit.>) that the class of Dushnik-Miller dimension d complexes is the class of TD-Delaunay complexes which we will define in the next paragraph.
The result holds for d=2 and d=3, but we disprove it already for d=4 in this paper.

We now define the class of TD-Delaunay complexes which finds its origins in spanners introduced by Chew and Drysdale <cit.>.
Given points in the plane, a plane spanner is a subgraph of the complete graph on these points which is planar when joining adjacent points with segments.
The stretch of a plane spanner is the maximum ratio of the distance in the graph between two vertices when using the Euclidean weight function and the Euclidean distance between these two points.
Given points in the plane, the question raised by Chew and Drysdale is to find a plane spanner which minimizes the stretch.
We define the stretch of a class of plane spanners as the maximum stretch of any of these graphs.
Chew <cit.> found the first class of plane spanners.
It consists in the class of L_1-Delaunay graphs which is a variant of the Delaunay graphs where the L_2 norm is replaced by the L_1 norm.
Given a norm N and points P in the plane, we define their Delaunay graph according to this norm as follows.
Given a point x, we define its Voronoi cell as the points y of the plane such that x is among the nearest points of P (according to the norm N) to y.
Two points are connected if and only if their Voronoi cells intersect.
This is equivalent to the fact that there exists a N-disk containing both points but no other in its interior.


Chew <cit.> conjectured that the class of L_2-Delaunay graphs (classical Delaunay graphs) has a finite stretch.
This question initiated a series of papers about this topic which drops the upper bound from 5.08 and 2.42 to 1.998 <cit.>.






A variant of this problem asks for minimizing the maximum degree.
Kanj et al. <cit.> proved that there exists plane spanners of maximum degree 4 and of stretch at most 20. 

Just a few years after introducing the plane spanner problem, Chew <cit.> found a second class of plane spanners.
It consists in TD-Delaunay graphs, obtained using the so-called triangular distance (which is not a distance but which is a convex distance function).
Given a compact convex shape S and a point c in the interior of S, we define the convex distance function, also called Minkowski distance function, between two points p and q as the minimal scaling factor λ such that after rescaling S by λ and translating it in the way to center it on p, then it contains also q.
By taking S the unit circle we get the Euclidean distance.
By taking S the unit square we get the L_∞ distance.
By taking S an equilateral triangle we get what we call the triangular distance.
Chew <cit.> showed that their stretch is at most 2 making the class of TD-Delaunay graphs the best plane spanners class until Xia <cit.> showed that the stretch of L_2-Delaunay graphs is strictly less than 2.
This class is also used to obtain bounded degree plane spanners  <cit.>.
TD-Delaunay graphs can be generalized to higher dimensions by taking the triangular distance in ^d according to a regular d-simplex.



The second section is dedicated to the notion of Dushnik-Miller dimension applied to the inclusion poset of simplicial complexes.
In the third section we define TD-Delaunay complexes.
In the fourth section, we introduce the notion of multi-flows which will be useful to the main theorem.
The fifth section contains our main contribution in the form of a simplicial complex whose inclusion poset has Dushnik-Miller dimension 4 but that is not a TD-Delaunay complex in ^3.
Finally, in the sixth section we prove that rectangular Delaunay complexes <cit.> are TD-Delaunay complexes in ^3.




§ DUSHNIK-MILLER DIMENSION OF SIMPLICIAL COMPLEXES


Bonichon et al. <cit.> showed the following property of TD-Delaunay graphs.

    A graph G is planar if and only if G is a subgraph of a TD-Delaunay graph.


As a graph is planar if and only if G is of Dushnik-Miller dimension at most 3, there is maybe a link between the notions of Dushnik-Miller dimension and TD-Delaunay complexes.
In <cit.> and <cit.> it was independently conjectured that Dushnik-Miller dimension at most d complexes are exactly the subcomplexes of TD-Delaunay complexes of ^d-1.

We now need to define formally the notions used.
First of all abstract simplicial complexes generalize the notion of graphs.

An abstract simplicial complex Δ with vertex set V is a set of subsets of V which is closed by inclusion (i.e. ∀ Y ∈Δ, X ⊆ Y ⇒ X ∈Δ). 
An element of Δ is called a face.
A maximal element of Δ according to the inclusion order is called a facet.






 §.§ Dushnik-Miller dimension


The notion of Dushnik-Miller dimension of a poset has been introduced by Dushnik and Miller <cit.>.
It is also known as the order dimension of a poset.

  The Dushnik-Miller dimension of a poset (≤,V) is the minimum number d such that (≤,V) is the intersection of d linear extensions of (≤,V). This means that there exists d extensions (≤_1,V), … , (≤_d,V) of (≤,V) such that for every x,y ∈ V, x ≤ y if and only if x ≤_i y for every i ∈1d.
     In particular if x and y are incomparable with respect to ≤, then there exists i and j such that x ≤_i y and y ≤_j x.




The notion of Dushnik-Miller dimension can be applied to an abstract simplicial complex as follows.


	Let Δ be an abstract simplicial complex.
    The inclusion poset of Δ is the poset (⊂, Δ).
	The Dushnik-Miller dimension of Δ is the Dushnik-Miller dimension of the inclusion poset of Δ.




We denote _DM(Δ) the Dushnik-Miller dimension of a simplicial complex Δ.
Low dimensions are well known.
We have _DM(Δ)=1 if and only if Δ is a vertex.
We have _DM(Δ)≤ 2 if and only if Δ is a union of paths.
There are complexes with arbitrarily high Dushnik-Miller dimension: for any integer n, _DM(K_n) = O( loglog n) where K_n denotes the complete graph on n vertices.
The following theorem shows that the topological notion of planarity can be understood as a combinatorial property thanks to the Dushnik-Miller dimension.


	
	A graph G is planar if and only if _DM(G) ≤ 3.


A generalization of the notion of planarity for simplicial complexes is the notion of straight line embedding.
As in the planar case, we do not want that two disjoint faces intersect.
We recall that a simplex of ^d is the convex hull of a set of affinely independent points. We denote 𝖢𝗈𝗇𝗏(X), the convex hull of a set of points X.

	
	Let Δ be a simplicial complex with vertex set V.
	A straight line embedding of Δ in ^d is a mapping f : V →^d such that
	
	
	 
  * ∀ X  ∈Δ, f(X) is a set of affinely independent points of ^d,
	 
  * ∀ X,Y ∈Δ, 𝖢𝗈𝗇𝗏(f(X)) ∩𝖢𝗈𝗇𝗏(f(Y)) = 𝖢𝗈𝗇𝗏(f(X ∩ Y)).
	


The following theorem shows that the Dushnik-Miller dimension in higher dimensions also captures some geometrical properties.


	
	Any simplicial complex Δ such that
 _DM(Δ) ≤ d+1 has a straight line embedding in ^d.


For d=2, this theorem states that if a simplicial complex has dimension at most 3 then it is planar. 
Brightwell and Trotter <cit.> proved that the converse also holds (for d=2)[Note that in a straight line embedding in ^2 every triangle is finite, and it is thus impossible to embed a spherical complex like a octahedron or any polyhedron with triangular faces.].
For higher d, the converse is false: take for example K_n the complete graph which has a straight line embedding in ^3 (and therefore in ^d for d ≥ 3) and which has Dushnik-Miller dimension O(loglog n) <cit.>.

	


 §.§ Representations


Representations have been introduced by Schnyder <cit.> in order to prove Theorem <ref>.

It is a tool for dealing with Dushnik-Miller dimension.
Here, only vertices will be ordered while in the Dushnik-Miller dimension every face of the complex must be ordered. 


	Given a linear order ≤ on a set V, an element x ∈ V, and a set F ⊆ V, we say that x dominates F in ≤, and we denote it F≤ x, if f ≤ x for every f ∈ F. 
	A d-representation R on a set V is a set of d linear orders ≤_1 , … , ≤_d on V.	
	Given a d-representation R, an element x ∈ V, and a set F ⊆ V, we say that x dominates F (in R) if x dominates F in some order ≤_i∈ R.
	We define Σ(R) as the set of subsets F of V such that every v ∈ V dominates F.


Note that ∅∈Σ(R) for any representation R. An element x∈ V is a vertex of Σ(R) if {x}⊆ V. Note that sometimes an element x∈ V is not a vertex of Σ(R). Actually, the definition of d-representation provided here is slightly different from the one in <cit.> and <cit.>. There, the authors ask for the intersection of the d orders to be an antichain. With this property, every element of V is a vertex of Σ(R). Note that simply removing the elements of V that are not vertices of Σ(R) yields a representation in the sense of <cit.>.


	For any d-representation R = (≤_1, … , ≤_d) on a set V,
	Σ(R) is an abstract simplicial complex.





	For any F ∈Σ(R), let X be any subset of F, and let v be any element of V.
	Since F ∈Σ(R), there exists ≤_i ∈ R such that y ≤_i v for every y ∈ F.	Particularly, x ≤_i v for every x ∈ X. Thus X ∈Σ(R) and we have proven that Σ(R) is an abstract simplicial complex.


An example is the following 3-representation on {1,2,3,4,5} where each line corresponds to a linear order whose elements appear in increasing order from left to right:


    [ ≤_1   1   2   5   4   3; ≤_2   3   2   1   4   5; ≤_3   5   4   3   2   1 ]

  
The corresponding complex Σ(R) is given by the facets {1,2},
{2,3,4} and {2,4,5}.  For example {1,2,3} is not in
Σ(R) as 2 does not dominate {1,2,3} in any order.
 The following theorem shows that representations and Dushnik-Miller dimension are equivalent notions.
 

	
	Let Δ be a simplicial complex with vertex set V.
	Then _DM(Δ) ≤ d if and only if there exists a d-representation R on V such that Δ is included in Σ(R).


For the following proofs, R will be a d representation (≤_1, … , ≤_d) and R' will be a d-representation (≤_1', … , ≤_d').
The following lemmas are technical and will be useful for the proof of our main result, Theorem <ref>.



	
	Let R = (≤_1, … , ≤_d) be a d-representation on V.
	Let x and y be two different vertices of Σ(R) (i.e. {x} and {y}∈Σ(R)) such that {x,y}∉Σ(R) and such that x and y are consecutive in the order ≤_i.
	The representation obtained after the permutation of x and y in the order i, denoted R'=(≤'_1, …, ≤'_d), is such that Σ(R') = Σ(R). 


	Without loss of generality, we suppose that i = 1 and that x ≤_1 y.
	Let us first show that Σ(R') ⊆Σ(R).

	Towards a contradiction, let us consider a face F ∈Σ(R) such that F ∉Σ(R').
	There exists therefore a vertex z ∈ V which does not dominate F in R'.
	As z dominates F in R, and as ≤_i = ≤'_i for every i≠ 1, we thus have that F ≤_1 z and F ≰_1' z.	This implies that z = y, that x ∈ F. As x and y are not adjacent, we have that y∉ F.
	Furthermore, y only dominates F in order ≤_1 of R.
	We denote f_i the maximum vertex of F in order ≤_i, then f_1 = x and:

	
    [ ≤_1   ⋯   x   y   ⋯; ≤_2   ⋯   y   ⋯ f_2   ⋯;   ⋮       ⋮       ⋮; ≤_d   ⋯   y   ⋯ f_d   ⋯;     ]

	
	As {x,y}∉Σ(R), there exists an element w∈ V such that w <_i max_≤_i(x,y) for every i.
	Thus either w=x, contradicting the fact that {y}∈Σ(R), or w <_i f_i for every i (in particular for i=1 because x and y are consecutive), contradicting the fact that F ∈Σ(R).
	
		
	We showed that Σ(R) ⊆Σ(R'),
	but as this operation is an involution, we have that Σ(R') ⊆Σ(R).
	Thus Σ(R) = Σ(R').


Note that R' is such that for every edge ab∈Σ(R) the orders between its endpoints are preserved. In other words, for any j we have that a≤'_j b if and only if a≤_j b.
Given a d-representation R, an (≤_i)-increasing xy-path is a path (a_0=x, a_1, a_2 , … , a_k=y) in Σ(R) such that a_j ≤_i a_j+1 for every 0≤ j<k. 


    
	Let R be a d-representation on V, let x be a vertex of Σ(R) (i.e. {x}∈Σ(R)), and let ≤_i be any order of R. There exists a d-representation R' such that:
	
	
  * Σ(R')=Σ(R),
	
  * for every j, a path P is (≤'_j)-increasing (in Σ(R')) if and only if it is (≤_j)-increasing (in Σ(R)), 
	
  * ≤'_j  ≡ ≤_j for every j≠ i,
	
  * x ≤'_i y if and only if there exists an (≤'_i)-increasing xy-path in Σ(R') (thus if and only if there exists an (≤_i)-increasing xy-path in Σ(R)), and
	
  * a≤'_i b≤'_i x implies that a≤_i b.
	 


    First note that it is sufficient to prove the second item for length one paths (as longer paths are just concatenations of length one paths).
    We proceed by induction on n, the number of couples (y,z) such that x≤_i y <_i z, such that there exists an (≤_i)-increasing xy-path, and such that there is no (≤_i)-increasing xz-path. In the initial case, n=0, as for every vertex z such that x≤_i z there exists an (≤_i)-increasing xz-path, we are done and R'=R.

    If n>0, consider such couple (y,z) with the property that y and z are consecutive in ≤_i (by taking z as the lowest element in ≤_i such that there is no (≤_i)-increasing xz-path).
    Note that {y,z}∉Σ(R) as otherwise, extending an (≤_i)-increasing xy-path with the edge yz one obtains an (≤_i)-increasing xz-path.
	By Lemma <ref>, the d-representation R' obtained by permuting y and z is such that Σ(R') = Σ(R), such that the orders between the endpoints of any edge are preserved (and thus the increasing paths are preserved), such that ≤'_j  ≡ ≤_j for every j≠ i, such that for any two vertices a and b without (≤'_i)-increasing xa-path nor xb-path, a≤'_i b if and only if a≤_i b, and has only n-1 couples (y',z').
	
	
	
    We can thus apply the induction hypothesis to R' and we obtain that there exists a d-representation R” such that Σ(R”)=Σ(R')=Σ(R), such that the increasing paths are the same as in Σ(R') (and thus as in Σ(R)), such that ≤”_j  ≡ ≤'_j  ≡ ≤_j for every j≠ i, such that  x ≤”_i y if and only if there exists an (≤”_i)-increasing xy-path in Σ(R”), and such that a≤”_i b≤”_i x implies that a≤'_i b, which implies a≤_i b (as there is no (≤'_i)-increasing xa-path nor xb-path).




    
    Let R be a d-representation on V.
    For any face F ∈Σ(R) and any vertex x of Σ(R), there exists an  (≤_i)-increasing f_ix-path for some order ≤_i∈ R, where f_i is the maximal vertex of F in order ≤_i.


    We proceed by induction on n, the number of orders ≤_i ∈ R such that F ≤_i x.
	If n=0 then F∉Σ(R), a contradiction. So the lemma holds by vacuity.
	If n>0, consider an order ≤_i ∈ R such that F ≤_i x. By Lemma <ref> (applied to f_i in ≤_i) either Σ(R) contains an (≤_i)-increasing f_ix-path, and we are done, or there exists a d-representation R' such that Σ(R')=Σ(R), such that the increasing paths are the same as in Σ(R), such that ≤'_j  ≡ ≤_j for every j≠ i, and such that x <'_i f_i. In this case, we apply the induction hypothesis on R'. Indeed, F ∈Σ(R') and R' has only n-1 orders ≤'_j such that F ≤'_j x. Note that as every pair in F corresponds to an edge, the maximal vertices of F in ≤'_j and ≤_j are the same for every j. The induction thus provides us an (≤'_j)-increasing f_jx-path and this path is also (≤_j)-increasing in Σ(R).



    
    Let R be a d-representation on V.
    For any vertex set F ∉Σ(R), there exists a vertex x  which does not dominate F, and 
    such that for every ≤_i ∈ R there exists an (≤_i)-increasing xf^i-path for some vertex f^i∈ F.


	We proceed by induction on the number n of elements which do not dominate F.
	If n=0 then F∈Σ(R), a contradiction. So the lemma holds by vacuity.
    If n>0, consider any such element x which does not dominate F.
    By Lemma <ref> either there are (≤_i)-increasing xf^i-paths for every ≤_i∈ R and we are done, or there exists a d-representation R' such that Σ(R')=Σ(R), 
    such that the increasing paths are the same as in Σ(R),
    such that F ≤'_i x for some order ≤'_i ∈ R', 
    such that a≤'_i b≤'_i x implies that a≤_i b,
    and such that ≤'_j  ≡ ≤_j for every j≠ i.
    
    In this case, we apply the induction hypothesis on R'. Indeed, as any element not dominating F in R' does not dominate F in R, and as x is not dominating F in R', we have at most n-1 elements that do not dominate F in R'. By induction hypothesis there exists a vertex x such that for every ≤'_i ∈ R', Σ(R') has an (≤'_i)-increasing xf^i-path for some vertex f^i∈ F, and this path is also (≤'_i)-increasing in Σ(R). 






§ TD-DELAUNAY COMPLEXES


TD-Delaunay graphs have been introduced by Chew in <cit.>.
Here we generalize this definition to higher dimensions.
We recall that a positive homothety h of ^d is an affine transformation of ^d defined by h(M) = α M + (1-α) Ω where α≥ 0 and Ω∈^d.
The coordinates of a point x ∈^d will be denoted (x_1, … , x_d).
	
For any integer d, let H_d be the (d-1)-dimensional hyperplane of ^d defined by { x ∈^d : x_1 + ⋯ + x_d = 1 }. 
Given c = (c_1, … , c_d) ∈^d, we define a regular simplex S_c of H_d by setting S_c = { u ∈ H_d : u_i ≤ c_i, ∀ i ∈1d }.
A regular simplex S_c is said to be positive if ∑_i=1^d c_i ≥ 1.
For c = (1,… , 1) = 1 we call S_1 the canonical regular simplex.
In this context, a point set 𝒫⊂ H_d is in
general position if for any two vertices x,y∈𝒫,
x_i ≠ y_i for every i ∈1d.
The interior S_c of a regular simplex S_c is defined by S_c = { u ∈ H_d : u_i < c_i , ∀ i ∈1d }



	The positive regular simplices of H_d are the subsets of H_d positively homothetic to S_1.


    Let U be a subset of H_d positively homothetic to S_1.
    Let us show that there exists c ∈^d such that U = S_c and ∑_i=1^d c_i ≥ 1.
    There exists h a positive homothety of ^d of ratio α and center Ω∈ H_d such that h(U) = S_1.
	We define c = (c_1, … , c_d) ∈^d by c_i = α + (1 - α)Ω_i.
	We show that h(S_1) = S_c.
	If α = 0 it is clear that h(S_1) = {Ω} and that S_c = {Ω}.
	We can therefore suppose that α >0.
	
	Let u ∈ S_1.
	Then u_i ≤ 1 for every i ∈1d.
	Then h(u)_i = α u_i + (1-α) Ω_i ≤α + (1-α) Ω_i = c_i.
	Furthermore ∑_i=1^d h(u)_i = α∑_i=1^d u_i + (1- α) ∑_i=1^d Ω_i = α + (1- α) = 1.
	Then h(u) ∈ S_c and thus h(S_1) ⊆ S_c.
	
	Let v ∈ S_c.
	Then v_i ≤ c_i for every i ∈1d.
	Because α≠0, we define u such that h(u) = v, that is such that α u_i + (1- α) Ω_i = v_i. 
	As 1 = ∑_i=1^d v_i = α∑_i=1^d u_i + (1-α) ∑_i=1^d Ω_i = α∑_i=1^d u_i + (1- α), then u ∈ H_d.
	Furthermore for every i ∈1d, α u_i + (1-α) Ω_i = v_i ≤α + (1-α) Ω_i.
	Thus u_i ≤ 1.
	So, u ∈ S_1.
	
	We conclude that h(S_1) = S_c.
	Furthermore if α≥ 0 then S_c is positive.
	Indeed ∑_i=1^d c_i = d α + (1- α) ∑_i=1^d Ω_i = (d-1) α + 1 ≥ 1.
	We deduce that every subset of H_d which is positively homothetic to S_1 is a positive regular simplex.
	
	Let S_c be a positive regular simplex of H_d with c ∈^d such that ∑_i=1^d c_i ≥ 1.
	We look for α≥ 0 and Ω∈ H_d such that c = α + (1-α) Ω.
	Suppose that such an α≥ 0 and an Ω exist.
	Then c_i = α + (1-α) Ω_i for every i ∈1d.
	Then ∑_i=1^d c_i = (d-1) α + 1.
	Thus α = (∑_i=1^d c_i -1)/(d-1) ≥ 0 and Ω_i = (c_i - α)/(1-α).
	It is easy to check that this gives the desired α and Ω and that they are well defined even if α = 0 or 1.
	We conclude that S_c is positevly homothetic to S_1 in H_d.




	
	
	
	
	
	
	
	
Let us now define TD-Delaunay simplicial complexes by extending the notion of TD-Delaunay graph defined by Chew and Drysdale <cit.>.


	Given a set  of points of H_d (⊂^d) in general position, let the TD-Delaunay complex of 𝒫, denoted ( 𝒫), be the simplicial complex with vertex set 𝒫 defined as follows.
	A subset F ⊆ is a face of () if and only if there exists a positive regular simplex S such that S ∩ = F and such that no point of   is in the interior of S.


Let F ⊆, we define c^F ∈^d by c^F_i = max_x ∈ F  x_i.
Remark that ∑_i=1^d c^F_i ≥ 1 because for every x ∈ F, ∑_i=1^d c^F_i ≥∑_i=1^d x_i = 1.


    
    For any set F ⊆, F ∈() if and only if S_c^F does not contain any point of  in its interior.


    Suppose that F ∈().
    Then there exists a positive regular simplex S_c such that S ⋂ = F and such that no point of  is in the interior of S.

    As S_c contains F, for every x ∈ F and every i ∈1d, x_i ≤ c_i.
    Thus c^F_i ≤ c_i for every i and S_c^F⊆ S_c.
    Therefore S_c^F does not contain any point of  in its interior otherwise S_c would contain some.

    Suppose that S_c^F does not contain any point of  in its interior.
    Let x ∈ F.
    By definition of c^F, x_i ≤ c^F_i for every i.
    So x ∈ S_c^F and S_c^F contains F.
    Let x ∈∖ F.
    If x is in S_c^F, then x is not in the interior of S_c^F.
    So there exists i ∈1d such that x_i = c^F_i.
    But there exists y ∈ F (different from x) such that y_i = c^F_i.
    This contradicts the fact that the points of  are in general position.
    Therefore S_c^F∩ = F and F ∈().



	For any point set  in general position in H_d (⊂^d), () is an abstract simplicial complex.


    Consider any F ∈(), and any G ⊊ F.
    Then c^G_i ≤ c^F_i for every i.
   So S_c^G⊆ S_c^F.
   S_c^G does not contain any point of  in its interior otherwise S_c^F would contain some.
   Thus because of the previous lemma, G ∈() and we conclude that () is an abstract simplicial complex.
    
   
   
   





Consider a point set  of ^d in general position.
We define the orders ≤_i on  as x ≤_i y if and only if x_i ≤ y_i, in other words if and only if x_i - y_i ≤ 0. First, note that as the points are in general position these orders are well defined. Note also that the values x_i for x∈ and i∈1d form a solution of a linear system of inequalities (with inequalities of the form x_i - y_i ≤ 0).
In the following we connect TD-Delaunay complexes to representations through systems of inequalities.
To do so we consider these d orders as a d-representation denoted R(). If ⊂ H_d this d-representation is closely related to ().


For any point set  of H_d⊂^d in general position, we have that () = Σ(R()). Thus, any TD-Delaunay complex of H_d≃^d-1 has Dushnik-Miller dimension at most d.


Consider a set of points  of H_d in general position and let R() = (≤_1,…,≤_d) be the d-representation on  such that u≤_i v if and only if u_i ≤ v_i. 

Let us first prove that () ⊆Σ(R()), by showing that for any F∈() we have that F∈Σ(R()). By definition there exists c ∈^d such that S_c contains exactly the points F, and they lie on its border.  
For every i, we denote by f_i the maximum among the elements of F with respect to ≤_i.  
Towards a contradiction we suppose that F ∉Σ(R()). 
Thus there exists a vertex z of  such that z does not dominate F in any order of R(). Thus z <_i f_i for every i. 
Therefore z_i < (f_i)_i for every i. 
But (f_i)_i ≤ c_i because f_i ∈ S_c thus z_i < c_i.
Hence z ∈S_c contradicting the definition of S_c.  


Let us now prove that Σ(R()) ⊆(), by showing that for any F∈Σ(R()) we have that F∈(). Consider any non-empty face F ∈Σ(R) (the case of the empty face is trivial) and suppose towards a contradiction that F∉(). According to Lemma <ref>, there exists x ∈ such that x ∈S_c^F. Thus x_i < c^F_i for every i. For every i, we define f_i as the maximum among the elements of F with respect to ≤_i. Thus x_i < c^F_i = (f_i)_i, and x <_i f_i for every i, which contradicts the fact that F ∈Σ(R).




The reciprocal statement holds for d=2
and 3, as any d-representation R is such that Σ(R) defines a TD-Delaunay complex of H_d. This naturally raised the following conjecture <cit.> (See also in <cit.> as an open problem). 


For every d-representation R, the abstract simplicial complex
Σ(R) is a TD-Delaunay complex of H_d≃^d-1.


Mary <cit.> proved the conjecture when Σ(R)
already admits some particular embedding. In the following we show
that actually this conjecture does not hold, already for d=4.
To do so, in the following we characterize which representations R are such that Σ(R) is a TD-Delaunay complex. Actually we are first going to characterize which d-representations R correspond to some point set  of H_d such that R=R(), and then we are going to show that for those we have () = Σ(R()).
By definition of R(), for any different x,y ∈ and for any order ≤_i∈ R() we have that x≤_i y, if and only if 

    y_i - x_i > 0

Furthermore as we consider a point set  of H_d we have that ∑_1≤ i≤ d x_i =1, which gives:

    x_d = 1-∑_1≤ i< d x_i

In the following we consider a d-representation R, and we define the system of inequalities obtained by taking Inequality (<ref>) for every i∈1d but only for the pairs {x,y}∈Σ(R), and by replacing the d^th coordinates by the right hand of Equation (<ref>).



    	Let R be a d-representation on a vertex set V, and consider the edge set E of Σ(R) defined by E = { X ∈Σ(R) : |X| = 2}.
    	We define the matrix A_R of _ E ×1d , V ×1d-1()
    	where the coefficients, a_(e,i),(v,j) of A_R are indexed by an edge e∈ E, a vertex v∈ V, and two indices i ∈1d and j ∈1d-1.
    
    a_(e={x,y},i),(v,j) = 
        
        +1     if i=j, v ∈ e and v = max_≤_j (x,y)
    
        -1     if i=j, v ∈ e and  v = min_≤_j (x,y)
    
        +1     if i = d, v ∈ e and  v = min_≤_d (x,y)
    
        -1     if i = d, v ∈ e and  v = max_≤_d (x,y)
    
        0     otherwise

    The TD-Delaunay system of the representation R is the following linear system of inequalities :
	
    A_R X > 0

	for some vector X ∈^V ×1d-1.



	We consider the following 3-representation R on V={a,b,c}:
	
	
    [ ≤_1   b   c   a; ≤_2   a   c   b; ≤_3   a   b   c ]

	The complex Σ(R) is given by the facet {a,b,c} and contains 3 edges: ab, bc and ac.
	The matrix of the TD-Delaunay system of R is:
    
    A_R =     (a,1)     (b,1)     (c,1)     (a,2)     (b,2)     (c,2) 
    	(bc,1)        -1     1 
    	(ac,1)     1        -1 
    	(ab,1)     1     -1    
    	(bc,2)                 1     -1 
    	(ac,2)              -1        1 
    	(ab,2)              -1     1    
    	(bc,3)        1     -1        1     -1 
    	(ac,3)     1        -1    1        -1 
    	(ab,3)     1     -1         1     -1

	The system A_R X > 0 where X ∈^V ×1d-1 is equivalent to the following linear system, where v_i denotes X_(v,i). 
	
    b_1 < c_1 
    
    		c_1 < a_1 
    
    		b_1 < a_1 
    
    		c_2 < b_2 
    
    		a_2 < c_2 
    
    		a_2 < b_2 
    
    		c_1 + c_2 < b_1 + b_2 
    
    		c_1 + c_2 < a_1 + a_2 
    
    		b_1 + b_2 < a_1 + a_2

	Note that setting a_3, b_3, and c_3 to 1-a_1-a_2, 1-b_1-b_2, and 1-c_1-c_2 respectively, the last three equations imply that b_3< c_3, a_3< c_3 and a_3< b_3.




For any abstract simplicial complex Δ with vertex set V, Δ is a TD-Delaunay complex of H_d ≃^d-1 if and only if there
exists a d-representation R on V such that Δ = Σ(R)
and such that the corresponding TD-Delaunay system has a solution.


(⇒)
This follows from Theorem <ref> and from the fact that the coordinates of any point set  form a solution to the TD-Delaunay system defined by R().
	
(⇐) Consider now a d-representation R on a set V such that the TD-Delaunay system of R has a solution X ∈^V ×1d-1 and for any v∈ V let us define a point v∈^d by setting v_i = X_(v,i) for i∈1d-1, and v_d = 1-v_1-… -v_d-1. 
This implies that all these points belong to H_d. 
It will be clear from the context when we refer to an element of V or to the corresponding point of ^d.
As in the linear system the inequalities are strict, one can slightly perturb the position of the vertices in order to obtain points in general position that still fulfill the system constraints.
Recall that by construction, for any edge uv of Σ(R) and any i ∈1d, u_i < v_i if and only if u <_i v. This implies that if Σ(R) has an (≤_i)-increasing xy-path then x_i ≤ y_i.

Let us first prove that () ⊆Σ(R).
Consider a face F ∈() and suppose towards a contradiction that F ∉Σ(R). 
As F ∈(), there exists c∈^d such that S_c contains exactly the points F, and they lie on its border. As F ∉Σ(R), then by Lemma <ref>, there exists x∈ V which does not dominate F, and such that for every ≤_i ∈ R there exists an (≤_i)-increasing xf^i-path for some vertex f^i∈ F. Therefore x_i ≤ (f^i)_i ≤ c_i. As x does not dominate F and as the points are in general position one of these inequalities is strict and we conclude that x lies in the interior of S_c, a contradiction.

Let us now prove that Σ(R) ⊆(). Consider any non-empty face F ∈Σ(R). For every i ∈1d, we denote f_i the maximum of F in the order ≤_i and we define c∈^d (and S_c) by setting c_i = (f_i)_i.  
First note that for any vertex u ∈ F and any i ∈1d, as uf_i is an edge, we have that c_i = (f_i)_i ≥ u_i. We hence have that ∑_i=1^d c_i ≥∑_i=1^d u_i = 1. 
As F ∈Σ(R), for every u ∈ F there exists an i ∈1d such that u = f_i.
Therefore u_i = (f_i)_i = c_i and as u_j ≤ c_j for every j (because either u=f_j or {u,f_j}∈Σ(R) and then u_j ≤ (f_j)_j = c_j), we have that u is on the border of S.  
According to Lemma <ref>, for every u ∉F, there exists an (≤_i)-increasing f_iu-path in Σ(R), for some order ≤_i ∈ R. Therefore c_i = (f_i)_i < u_i and u ∉S_c.  
Thus F ∈() and Σ(R) ⊆().







§ MULTI-FLOWS


We disprove Conjecture <ref> using  Theorem <ref> by exhibiting a simplicial complex Δ, such that  Δ = Σ(R) for some 4-representation R, and such that none of the 4-representation R' verifying Δ = Σ(R') admits a solution to its TD-Delaunay system. A common tool to prove that a system of inequalities has no solution is the celebrated Farkas lemma.


    For any m × n real matrix A, either
    
     
  * Ax > 0 admits a solution x∈^m, or
     
  * ^t A y = 0 admits a non-zero solution y∈ (^+)^n.
    
    Furthermore both cases are exclusive.


In the following we show that this lemma defines a dual notion of a TD-Delaunay solution, we call it a multi-flow. To define it, we first need to recall some notions about flows.
Let G=(V,A) be a digraph with vertex set V and arc set A ⊆ V × V.
A flow on G is a function of φ : A →^+.  
Let the divergence 𝖽𝗂𝗏_φ(x) of a vertex x be given by 𝖽𝗂𝗏_φ(x) = ∑_(y,x) ∈ Aφ(y,x) - ∑_(x,y) ∈ Aφ(x,y).


	Let R={≤_1,…,≤_d} be a d-representation on V.
	For i ∈1d, G^i(R) will denote the digraph with vertex set V and arc set A^i where A^i = { (x,y) ∈ V× V : {x,y}∈Σ(R) , x  ≤_i y }.
	A multi-flow is a collection of d flows φ_1, …, φ_d respectively on each digraph G^1(R), … , G^d(R) such that _φ_i(v) = _φ_d(v), for every v∈ V and every i ∈1d.





We can now state the main result of this section.


	
	Let R be a d-representation on a set V.
	Then either
	
	 
  * the corresponding TD-Delaunay  system admits a solution, or
	 
  * R admits a non-zero multi-flow (i.e. a multi-flow with
           some φ_i(uv)>0).
	

	Furthermore both cases are exclusive.


	According to Proposition <ref>, the corresponding TD-Delaunay system admits a solution if and only if A_R x > 0 admits a solution x ∈^V ×1d-1.	
	According to Farkas lemma, it thus remains to show that ^t A_R y = 0 admits a non-zero solution y ∈ (^+)^E ×1d if and only if  R admits a non-zero multi-flow.
	
	Suppose that the system ^t A_R y = 0 admits a non-zero solution y ∈ (^+)^E ×1d.
	
	Then y_(e,i)≥ 0 for all i ∈1d and all e ∈ E.
	For any i ∈1d, we define the flow φ_i on G^i(R) by setting φ_i(a) = y_(e,i) for every a ∈ A^i, where e is the edge of E corresponding to the arc a.
	Since ^t A_R y = 0, the following equations hold for every v∈ V and every j ∈1d-1, 
	
    ∑_ (e,i) ∈ E ×1d a_(e,i),(v,j) y_(e,i)    =     0
    ∑_ (e,i) ∈ E ×1d-1 a_(e,i),(v,j) y_(e,i)    =     - ∑_ (e,i) ∈ E ×{d} a_(e,i),(v,j) y_(e,i)

	Since a_(e,i),(v,j) = 0 whenever i≠ j and i≠ d,
	
    ∑_e ∈ E a_(e,j),(v,j) y_(e,j)    =     - ∑_e ∈ E a_(e,d),(v,j) y_(e,d)

    By definition of A_R,
	
    ∑_e={u,v}∈ E
    s.t.  u≤_j v y_(e,j) - ∑_e={u,v}∈ E
    s.t.  v≤_j u y_(e,j)    =    ∑_e={u,v}∈ E
    s.t.  u≤_d v y_(e,d) - ∑_e={u,v}∈ E
    s.t.  v≤_d u y_(e,d)

    Finally by definition of φ_i, 
	
    ∑_(u,v) ∈ A^jφ_j(u,v) - ∑_(v,u) ∈ A^jφ_j(v,u)     =    ∑_(u,v) ∈ A^dφ_d(u,v) - ∑_(v,u) ∈ A^dφ_d(v,u)
    _φ_j(v)     =    _φ_d(v)

	
	
	
	We conclude that (φ_1, … , φ_d) is a non-zero multi-flow of R.
	
	To prove the converse statement suppose that R admits a non-zero multi-flow (φ_1, … , φ_d).
	We define y ∈^E ×1d by setting y_(e,i) by y_(e,i) = φ_i(a), for any e ∈ E and i ∈1d, and where a is the arc of G^i(R) corresponding to the edge e.
	Clearly y ∈ (^+)^E ×1d, and the multi-flow being non-zero, y is non-zero. As
	_φ_j(v) = _φ_d(v) for every v∈ V and every j∈1d-1, one can deduce (by reversing the above calculus) that ^t A_R y = 0. We thus have that y is a non-zero solution to ^t A_R y = 0.


	


§ A COUNTER-EXAMPLE TO CONJECTURE <REF>


Before showing our counter-example to Conjecture <ref> we need the following definition.

A d-representation R on a set V with at least d elements, is standard if every element v∈ V is a vertex of Σ(R), and if for any order, its maximal vertex is among the d-1 smallest elements in all the other orders of R.

Let us recall that in a simplicial complex, a k-face F is a face such that |F|=k+1.

Let R be a d-representation on V such that every element of V is a vertex of Σ(R).
The representation R is standard if and only if there exists vertices M_1, … M_d such that in Σ(R) every face belongs to at least one (d-1)-face, every (d-2)-face belongs to at least two (d-1)-faces except the (d-2)-faces F_i = {M_1,… M_d}∖ M_i which belong to only one (d-1)-face.




(⟹) Clear from <cit.>.

(⟸) Suppose that there exists vertices {M_1, …, M_d} such that every face belongs to at least one (d-1)-face, every (d-2)-face belongs to at least two (d-1)-faces except the (d-2)-faces F_i = {M_1,… M_d}∖ M_i which belong to only one (d-1)-face.



For any i ∈1d we define F'_i as a (d-1)-face minimizing max_≤_i{f∈ F'_i} in ≤_i among the other (d-1)-faces. Let us denote f'_i,j the element of F'_i that is maximal in ≤_j. As each of the d elements of F'_i dominates it at least once, F'_i = {f'_i,1,…,f'_i,d}. Let us show that F'_i∖{f'_i,i}, which is a (d-2)-face, does not belong to any other (d-1)-face. Indeed, if there exists a vertex x≠ f'_i,i such that F'_i∖{f'_i,i}∪{x} is a (d-1)-face then F'_i<_i x by definition of F'_i, and f'_i,i cannot dominate F'_i∖{f'_i,i}∪{x} (as f'_i,i <_i x and f'_i,i<_j f'_i,j for any j≠ i), a contradiction.

Suppose that there exists i and j ≠ i such that F'_i ∖{f'_i,i} = F'_j ∖{f'_j,j}.
We define X = F'_i ∖{f'_i,i}.
As X is included in F'_i and in F'_j , and as it belongs to only one (d-1)-face F'_i, we have that F'_i = F'_j and thus that f'_i,i = f'_j,j.
Then in the (d-1)-face F'_i = F'_j, the vertex f'_i,i = f'_j,j thus dominates F'_i in two orders, <_i and <_j, and one of the remaining d-1 elements of F'_i cannot dominate it, a contradiction.
We conclude that the faces F'_i ∖{f'_i,i} are distinct and are in bijection with the faces F_i.
We can thus assume that F_i = F'_i ∖{f'_i,i}. 

We now show that the M_i's are the maxima of the representation.
Let i ∈1d and j ≠ i.
Since M_i ∈ F_j, none of the (d-1)-faces is dominated by M_i in the order <_j. Indeed if it was the case then we would have a (d-1)-face F” such that F”≤_j M_i <_j f'_j,j which contradicts the definition of F'_j.
Thus F”≤_i M_i for every (d-1)-face F”.
For every element x, as x is included in at least one (d-1)-face, we have that x ≤_i M_i.
We conclude that M_i is the maximum of ≤_i.

We now show that M_i is among the d-1 smallest elements of the order ≤_j for every j ≠ i.
Since the face F_j contains M_i for every i ≠ j, none of the elements in V∖ F_j dominates F_j in ≤_i.
Thus each of the |V|-(d-1) elements of V∖ F_j dominates F_j in the order ≤_j. M_i is thus among the d-1 smallest elements in order ≤_j.
The representation R is thus standard.



	Let R be the following 4-representation on V={a,b,c,d,e,f,g,h}:

	
    [ ≤_1   b   c   d   e   g   f   h   a; ≤_2   a   c   d   e   h   f   g   b; ≤_3   a   b   d   f   g   e   h   c; ≤_4   a   b   c   f   h   e   g   d;     ]


	The simplicial complex Δ = Σ(R) has Dushnik-Miller dimension 4 but it is not a TD-Delaunay complex of H_4≃^3.



Let us first show that any 4-representation R' on V
such that Σ(R') = Δ is equivalent to R up to permutations of the orders and up to a permutation of the smallest 3 elements in each order. 

By Lemma <ref> such R' is standard with maximal elements a, b, c, and d. Without loss of generality we assume that these elements are maximal in ≤'_1, ≤'_2, ≤'_3, and ≤'_4, respectively. 
As {e,b,c,d}∈Δ and as none of a, e, f, g, h dominates this face in ≤'_2, ≤'_3, or ≤'_4, e is necessarily the fourth smallest element in ≤'_1. We similarly deduce that e is also the fourth smallest element in ≤'_2 (using the face {a,c,d,e} of Δ), and that f is the fourth smallest element in ≤'_3 and ≤'_4 (using the faces {a,b,d,f} and {a,b,c,f} respectively). 
As f dominates {b,e,g}∈Δ, we have that g≤'_1 f. We similarly deduce that h≤'_2 f, g≤'_3 e, and h≤'_4 e (using faces hea, gdf, and chf).
As h dominates {c,e,f}∈Δ, we have that f≤'_1 h. We similarly deduce that f≤'_2 g, e≤'_3 h, and e≤'_4 g (using faces def, aef, and bef).


This implies that for any such R' the subdigraphs of G^i(R') induced by the vertices e, f, g, and h are the same as in G^i(R).
These digraphs are depicted in Figure <ref>, as well as 
a multi-flow of R'. Vertices a, b, c, and d are not drawn as the flows on their incident edges are null. Their divergences are thus 0.
The divergences of the vertices e and f is -1 and it is +1 for g and f.
	
	
Thus, as every 4-representation R' such that Δ = Σ(R') has a multi-flow, Proposition <ref> and Theorem <ref> imply that Δ is not a TD-Delaunay complex of H_4≃^3.





§ LINK WITH RECTANGULAR DELAUNAY COMPLEXES


Rectangular Delaunay graphs have been studied independently by Felsner <cit.> and by Chen et al. <cit.>.
In the following,  denotes a finite set of points of ^2 such that no two points share the same vertical or horizontal coordinate.


    We define the R-Delaunay complex () of the point set  as the simplicial complex whose vertex set is  such that a subset F of  forms a face if there exists an axis-parallel rectangle R such that R ∩ = F and such that R does not contain any point of  in its interior. The R-Delaunay graph of a point set  is the graph defined by the faces of size one and two in ().




R-Delaunay graphs have interesting properties. Felsner <cit.> showed that those graphs can have a quadratic number of edges. In order to solve a question motivated by a frequency assignment problem in cellular telephone networks and related to conflit-free colorings <cit.>, Chen et al. showed the following result.


    Given points  in the unit square selected randomly and uniformly,
    the probability that the largest independent set of RD() is O(n log^2 log(n)/log(n)) tends to 1.

This implies that R-Delaunay graphs

can have arbitrarily large chromatic number.

Given a point set , we define the horizontal order ≤_1 on  as follows: for every two points x=(x_1,x_2) and y=(y_1,y_2) ∈, x ≤_1 y if and only if x_1 ≤ y_1.
Then we define ≤_2 as the reverse of the horizontal order.
We define the vertical order ≤_3 on  as previously: here x ≤_3 y if and only if x_2 ≤ y_2; and we define ≤_4 as the reverse of the vertical order.

One can show that using these four orders one obtains a representation R such that () = Σ(R) and actually any 4-representation,  where two pairs of orders are the reverse from each other, defines   an R-Delaunay complex. Felsner <cit.> showed this for graphs but his proof easily extends to simplicial complexes. In his words, R-Delaunay complexes are exactly the complexes of dimension [3↕↕4]. This implies that R-Delaunay complexes form a subclass of the simplicial complexes with Dushnik-Miller dimension at most 4. The following theorem refines this by showing that it is also a subclass of TD-Delaunay complexes of H_4≃^3.
    

    The class of R-Delaunay complexes is included in the class _4 of TD-Delaunay complexes of H_4≃^3.


    We want to show that RD(P) is a TD-Delaunay complex.
    According to Theorem <ref>, it is enough to show that the TD-Delaunay system of inequalities defined by R, where R is the previously defined 4-representation, has a solution. By Proposition <ref>, this is equivalent to show that there is no non-zero multi-flow  φ = (φ_1, φ_2, φ_3, φ_4) on R.

    Consider x the rightmost point: it is the greatest point according to order ≤_1.
    So x is a sink in G^1(R) and _φ_1(x) ≥ 0 for any flow φ_1 on G^1(R).
    As ≤_2 is order ≤_1 reversed, x is also the minimum in order ≤_2.
    So x is a source in G^2(R) and _φ_2(x) ≤ 0 for any flow φ_2 on G^2(R).
    So if _φ_1(x) = _φ_2(x) we have that this divergence is null, as well as φ_1 and φ_2 on the arcs incident to x.
    By induction on the number of vertices, we show that all the divergences defined by φ_1 (and φ_2) are null. Note that a flow φ defined on an acyclic digraph (such as G^1(R), G^2(R), G^3(R), and G^4(R)) with divergence zero at every vertex, is null everywhere (i.e. for each arc a, φ(a)=0). Therefore R has no non-zero multi-flow, and the system of inequalities defined by R admits a solution and RD()=Σ(R). The simplicial complex RD() is thus a TD-Delaunay complex of H_4≃^3.


Note that these classes are distinct as K_5∈_4 is not an R-Delaunay graph.
Another way to prove the above theorem is by showing that in ℝ^3, any rectangle with sides parallel to the axis and drawn on the plane defined by z=0, is the intersection between this plane and a regular simplex homothetic to the simplex with vertices (-2,0,+√(2)), (0,-2,-√(2)), (+2,0,+√(2)), (0,+2,-√(2)). Such a proof would also be simple but it would involve a few calculus that were avoided in the proof above.

Note that the arguments in the proof of Theorem <ref> show that any d-representation R, where two orders are the reverse from each other, is such that its TD-Delaunay system has a non-zero solution and thus Σ(R) is a TD-Delaunay complex of H_d≃^d-1.















§ CONCLUSION



TD-Delaunay complexes of ^3 have shown their interest as sparse spanners with small stretch <cit.>. 
It is likely that this extends to higher dimensional spaces. 
A question is for example whether graphs of Dushnik-Miller dimension 4 give better spanners than TD-Delaunay complexes in ^3.

Furthermore, as the class of TD-Delaunay complexes of H_d≃^d-1 is strictly included in the class of complexes of Dushnik-Miller dimension d, it may be interesting to study the problem of the grid embedding for this restricted class.  
Indeed Schnyder showed <cit.> that a planar graph with n vertices can be embedded in an n× n grid (without crossings). Ossona de Mendez showed <cit.> that a complex of Dushnik-Miller dimension d could be drawn in ^d-1 without crossings. 
Nevertheless the last embedding uses exponentially large grids and it is still an open problem to reduce the sizes of these grids.
Is it possible to reduce the size of these grids when dealing with TD-Delaunay complexes?
















§ ACKNOWLEDGMENTS

The authors are thankful to Arnaud Mary and Vincent Pilaud  for interesting discussions on this topic and to Gwenaël Joret for pointing us the class of rectangular Delaunay complexes.

99



BPS98 D. Bayer, I. Peeva, and B. Sturmfels. Monomial Resolutions. Math. Research Letters, 5(1): 31-46, 1998.

BGHI N. Bonichon, C. Gavoille, N. Hanusse, and D. Ilcinkas.
  Connections between theta-graphs, Delaunay triangulations, and
  orthogonal surfaces, Proc. of WG '10, LNCS 6410, 266-278,
  2010.
  


BK P. Bose and J. M. Keil. On the stretch factor of the constrained Delaunay triangulation. In Voronoi Diagrams in Science and Engineering ISVD'06, 25-31, 2006.

BT G. Brightwell and W. T. Trotter. The order dimension of convex polytopes. SIAM Journal on Discrete Mathematics 6(2): 230-245, 1993.
 
CD
 P. Chew and R.L. Drysdale, Voronoi diagrams based on convex distance functions, Proc. 1st Ann. Symp. on Computational Geometry, 235-244, 1985.
 
ChewL1
L. P. Chew. There is a planar graph almost as good as the complete graph. Proc. 2nd Annual Symposium on Computational Geometry, 169–177, 1986.




ChewTD
L. P. Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences 39(2): 205-219, 1989.



 
CPST X. Chen, J. Pach, M. Szegedy, and G. Tardos. Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. Random Structures and Algorithms 34(1): 11-23, 2009.  
   
DFS D. P. Dobkin, S. J. Friedman, and K. J. Supowit. Delaunay graphs are almost as good as complete graphs. In 28th Annual Symposium on Foundations of Computer Science, 20-26, 1987.
  
DM B. Dushnik and E. W. Miller. Partially ordered sets,
   American Journal of Mathematics, 63(3): 600-610, 1941.
   
EFKU W. Evans, S. Felsner, G. Kobourov, and T. Ueckerdt,
  Graphs admitting d-realizers: spanning-tree-decompositions and
  box-representations Proc. of EuroCG 14.
  
ELRS G. Even, Z. Lotker, D. Ron, and S. Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing 33(1), 94-136, 2003.
  

    
FarXiv06 S. Felsner, Empty Rectangles and Graph Dimension, ArXiv preprint arXiv:math/0601.767, 2006.

FT S. Felsner, and W. T. Trotter. Posets and planar graphs. J. Graph Theory 49, 262–272, 2005.
  
HM S. Hoşten and W. D. Morris. The order dimension of the complete graph. Discrete mathematics, 201(1-3), 133-139, 1999.
  
KPT  I. Kanj, L. Perković, and D. Türkoǧlu (2016). Degree four plane spanners: simpler and better. arXiv preprint arXiv:1603.03818, 2016.

Mary A. Mary, Dimension de poset et subdivisions
  simpliciales, Master Thesis, Univ. of Montpellier, 2010.

Ossona P. Ossona de Mendez, Geometric Realization of
  Simplicial Complexes, Proc. of Int. Symp. on Graph Drawing
    1999 LNCS 1731, 323-332, 1999.



Schnyder W. Schnyder, Planar graphs and poset dimension,
   Order 5(4): 323-343, 1989.

Trotter W. T. Trotter. Combinatorics and partially ordered sets: Dimension theory. Johns Hopkins Series in the Mathematical Sciences, The Johns Hopkins University Press, 1992.
   
Xia G. Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM Journal on Computing 42(4), 1620-1659, 2013.





  
  



