UBC Graduate Research

d-Realizers and the Minimal Graph Without One Nelson, Kristina Apr 19, 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


42591-Nelson_Kristina_CPSC536_D_Realizers_2014.pdf [ 5.21MB ]
JSON: 42591-1.0103600.json
JSON-LD: 42591-1.0103600-ld.json
RDF/XML (Pretty): 42591-1.0103600-rdf.xml
RDF/JSON: 42591-1.0103600-rdf.json
Turtle: 42591-1.0103600-turtle.txt
N-Triples: 42591-1.0103600-rdf-ntriples.txt
Original Record: 42591-1.0103600-source.json
Full Text

Full Text

The University of British Columbiad-Realizers and the Minimal Graph Without OneKristina NelsonApril 19, 2014We explore the work of Evans et al.[2], who in turn have built on Schnyder’s[1]definition of the dimension of a graph, and extended Schnyder woods to higherdimensions. Here we discuss d-realizers: sequences of d permutations on a set ofvertices required to have empty intersection and d ‘suspension’ vertices. We willpresent a minimal graph having no d-realizer, and numerous graphs on 5, 6 and 7vertices that do have one. Finally, we consider what possible characterization ofgraphs having a d-realizer could extend the triangulated-graph characterizationfound by Schnyder for 3 dimensional graphs.1 BackgroundIn Schnyder’s 1989 paper[1], he introduced a notion of dimension for graphs via a setof permutations he termed a d-dimensional representation. Working from a later paperby Evans et al.[2], we will examine how Shnyder’s results extend to dimensions higher than 3.Both papers work with total orderings on the set of vertices V , generally of some graphG. A few basic definitions are in order. Given 2 total orderings, <1, <2, their intersectionis the partial order containing all relationships <1, <2 agree on. To be precise: for x, y ∈ V ,x < y is in the intersection of <1 and <2 if and only if x <1 y and x <2 y. One can easilysee how this extends to the intersection of arbitrarily many orderings, with x < y in theintersection of <1, ..., <d if and only if x <i y for all i ∈ {1, .., d}. An anti-chain, then, isdefined to be any set of orders with empty (total) intersection. In Schnyder’s paper he1refers to this as the ‘vertex property’ of a sequence of orders.Schnyder also introduces a second property:Definition 1.1. Given some graph G and sequence of orders <1, ..., <d, a pair of verticesx, y ∈ V (G) is said to be a candidate pair if for all z ∈ V (G), with z 6= x, y there existssome i ∈ {1, .., d} s.t. z >i x and z >i y.In [1] he refers to any graph satisfying this as having the edge property, for that sequenceof orders.We now have enough to define the aforementioned d-dimensional representations.Definition 1.2. A d-dimensional representation on a set V is an anti-chain <1, ..., <d oftotal orders on V . This anti-chain is said to represent all graphs on |V | vertices with anedge set such that the edge property holds, or equivalently, graphs with every edge formedby a candidate pair.Note that by the above definition, if a graph has some d-dimensional representationthen any subgraph, with the same set of vertices, will also.Schnyder’s leap was in extending the definition of dimension from partially ordered sets,or posets, to graphs. He did so by constructing a poset from any given graph, but latergave an equivalent definition managing to skip the poset business entirely, and so this wepresent:Definition 1.3. A graph G with vertex set V is said to have dimension ≤ d if and only ifthere exists an anti-chain <1, ..., <d of total orders on V under which every edge of G is acandidate pair - that is if a d-dimensional representation of G exists. If d is the smallestnumber for which such a sequence exists, we say the dimension of G equals d.With this Schnyder obtained his famous characterization of planar graphs as those ofdimension ≤ 3. Other interesting results include showing all dimension 2 graphs were pathsor subgraphs of paths, and that the only dimension 1 graph is a single node.What we are most interested in now, however, is not simply all graphs represented bysome anti-chain <1, ..., <d, but those induced by one:Definition 1.4. A graph G is induced by the anti-chain <1, ..., <d if edge (x, y) appearsin E(G) if and only if x, y is a candidate pair with respect to <1, ..., <d.Note that such a graph is unique to its sequence of orderings, containing the maximalnumber of edges possible for a graph with that representation.2Schnyder considered arbitrary d-dimensional representations, requiring only that theirtotal orderings form an anti-chain and the edge property hold for the graph in question.For simplicity however, we will restrict ourselves to a special class of d-dimensional repre-sentation, which Schnyder defines as follows:Definition 1.5. A d-dimensional representation <1, ..., <d on a set V is standard if |V | ≥ dand for all i 6= j the maximal element of <i is one of the d− 1 smallest elements of <j .Schnyder refers to the d maximal elements of a standard representation as the exteriorvertices while [2] calls them the suspension vertices and an anti-chain with d suspensionvertices ‘suspended’. We will follow the latter convention as we are about to transition intothe work by Evans et al. In that second paper, a cousin of d-dimensional representations isdefined, the d-realizer :Definition 1.6. A d-realizer is a suspended anti-chain <1, ..., <d on the set V+ = V ∪ S,where S is the set of suspensions. In our previous language this is simply a standardd-dimensional representation.And now, to explore the graph corresponding to a d-realizer. We begin with a siblingto the candidate pair property, also introduced by [2]:Definition 1.7. Given some graphG and anti-chain<1, ..., <d, a pair of vertices x, y ∈ V (G)has the 1-of-d-property if there exists unique i ∈ {1, ..., d} s.t. x <i y and x >j y for allj 6= i.Evans et al. then defines the graph of a d-realizer <1, ..., <d as GR = (V+, E+) whereV + = V ∪ S again and E+ = ER ∪ ES . ES here is simply all edges of the clique on thesuspension vertices, and ER composed of all edges (x, y) who’s vertices x, y satisfy both thecandidate pair and 1-of-d properties.This sounds very similar to our previous definition of the graph induced by a d-representation, the only differences being the added 1-of-d criterion, and the handling ofthe clique edges.To resolve the latter of these difference we suggest an additional requirement on the d-realizer1. Let v1, ..., vd be the suspension vertices, already v1, .., vi−1, vi+1, ..., vd are requiredto appear in the smallest d− 1 spots of <i in the realizer. Perhaps regrettably, we will calla d-realizer standard if those d− 1 vertices are ordered v1 < .. < vi−1 < vi+1 < ... < vd in1The author admits this additional requirement was suggested in [2] in their proof of Theorem. 1 of thesection on box-representations.3<i as well. The reader can check this guarantees all edges of the clique on the suspensionvertices now satisfy the candidate pair and 1-of-d properties. And so for a standardd-realizer, an equivalent definition of the corresponding graph GR is GR = (V+, ER), sinceES ⊂ ER. Note that since the ordering of the suspension vertices within the first d − 1elements normally has no effect on the graph GR, exactly the same graphs have a standardd-realizer as those with a non-standard realizer.And so, given a standard d-realizer, the corresponding graph GR is almost now almostthe same as the one induced - save for the added 1-of-d condition. In the case d = 3 however,the 1-of-d condition becomes automatic: given any pair x, y ∈ V (G), x <1 y, x <2 y andx <3 y would imply x < y in the intersection and so our supposed d-realizer is not evenan anti-chain. And so there must be i, j ∈ {1, 2, 3} with x <i y and x >j y; then whateverorder the remaining <k choses, there will be an odd order out.And so we have in the d = 3 case, that the set of graphs having a d-realizer is exactlythe set with a standard d-dimensional representation. In [1] Schnyder proves these areprecisely the maximal planar graphs. And indeed,[2] notes in the abstract that all graphswith a 3 dimensional realizer are maximal planar graphs 2Observe also that the 1-of-d criteria appears even more easily in dimensions < 3. Andso one can say for d ≤ 3, a graph has a d-realizer if and only if it has a d-dimensionalrepresentation. Thus the question of which graphs have a d-realizer was solved for d ≤ 3when Schnyder published in 1989. We are now interested in higher dimensions, in particularwe will focus on the case d = 4.2 The Quest for the Smallest Counter-exampleIn general, one would like to know when a graph does and does not have a d-realizer forsome dimension d. To this end we searched for a smallest graph, in vertex number, that iswithout a d-realizer and yet with sufficient edges to in theory have one.In this section many of our proofs will rely on properties found in the resulting Schnyderwood of a d-realizer, and so we introduce these now. The Schnyder wood was originallydefined only for 3-dimensional representations - requiring the 1-of-d property that one getsfor free in d = 3. With [2]’s definition of the graph GR of a d-realizer, and in particular their1-of-d requirement, the Schnyder wood construction was extended to arbitrary dimensions.2I am not sure if they note this is a characterization.4Definition 2.1. Given a d-realizer <1, ..., <d and associated graph GR we let Ti be the setof directed edges (x, y) where x, y form a candidate pair, and y >i x while y <j x for allj 6= i. Thus Ti ∩ Tj = ∅ for i 6= j and ∪iTi = GR.We will often refer to edges of Ti as the edges of ‘colour i’. Evans et al. show thatthese Ti carry over our favourite behaviours from the 3-dimensional Schnyder Wood case,in particular:Proposition 2.2. Given d-realizer <1, ..., <d, for each i ∈ {1, ..., d} the directed graph Tiforms an in-arborescence with root, si, being the suspension vertex associated with <i.Proposition 2.3. The graph GR of a d-realizer on n + d verticies will have preciselydn+(nd)edges.Proposition 2.4. Again, suppose we have some d-realizer, <1, ..., <d for graph G. Thenfor any j ∈ {1, ..., d} the directed graph ∑i 6=j Ti + (Tj)−1 is a acyclic.2.0.1 A counter-example on 7 verticesWe now introduce, in figure 2.1, a graph G∗ on 7 vertices found to have no d-realizer, and yetwith enough edges to support one. To be precise, the claim is that no d-realizer, <1, ..., <d,has this graph as its corresponding GR. First we handle d < 4: as explained previously,these graphs were shown by Schnyder to be planar graphs. Since G∗ contains K3,3, forexample see figure 2.1 (b), it cannot have a d-realizer for d ≤ 3. Meanwhile, counting edgeswill allow us to rule out all d > 4. Using proposition 2.3, we see that d = 5 implies n = 2and so requires 10 + 10 = 20 edges. Similarly d = 6 corresponds to 16 edges, d = 7 to 21.Since none of these numbers are 18, which the diligent reader may check is our edge count,d 6= 5, 6 or 7. Larger d of course, simply require more suspension vertices than our graphcan support and so can be ruled out immediately.This leaves us with the case d = 4. At first glance the proof seems tedious, as we mustallow any 4-clique of the graph to try forming the suspension vertices. Looking closelyhowever, G∗ is highly symmetric. See the complement in figure 2.2 (a) for a clear picture.In short, there is a single vertex of degree 6, and 6 of degree 5. The 5 degree vertices havebeen paired up by the 3 missing edges, and so any 4-clique can contain only one vertex ofeach pair. Since that allows for only 3 such vertices, the 6-degree vertex must always bechosen - along with precisely 3 non-neighbouring (in the complement) degree-5 vertices.The key observation is then that all 4-cliques H ⊂ G∗ result in the same remainder G\H,up to an isomorphism.And so we need only consider the removal of an arbitrary 4-clique, see figure 2.2 (b) forthe remainder on such a removal. There, the black triangle contains the non-suspensionvertices, the other four having formed the 4-clique. As shown in the blue edges, there5(a) G∗ (b) K3,3 in blueFigure 2.1: A graph, G∗, on 7 vertices with no d-realizerwill be a single suspension vertex, originally the degree 6 vertex, with all non-suspensionvertices already in it’s tree. Meanwhile it is clear that the red, orange and green suspensionvertices (those vertices touching only red, orange or green edges in the figure) each requirean additional edge to span. Thus the black triangle must contain 3 different edge colours.But then it is doomed - if the edges are arranged cyclically flipping the blue tree presentsus with a cycle in T−1blue + Tred + Torange + Tgreen, while an acyclic 3-cycle can always bemade cyclic with the flip of a single edge. And so in either case, the trees would contradictproposition 2.4 and therefore no 4-realizer can exist.3 How About Some Graphs that Do Work?The search for a counter example involved, unsurprisingly perhaps, the discovery of manyactual examples. In particular, the author believes they have found all graphs on 7 verticeswith a 4-realizer - though if 3 graphs seems like a ridiculously small number the reader isadvised to take this with a grain of salt.We will start by proving our previously described counter example is indeed on theminimum number of vertices possible, and then describe in more detail our findings on|V | = 7.Note that a graph on 4 or fewer vertices is planar, and so has a 3,2 or 1-realizer. Thusthe first case to consider is that of n = 5. Here the only graph with sufficient edges is K56(a) The complement of G∗(b) The remainder of G∗ on removing any K4Figure 2.2itself, and the reader can check the following provides a valid 4-realizer for this graph (seefigure 3.1):<1: v2, v3, v4, v1, v5<2: v2, v3, v5, v1, v4<3: v2, v4, v5, v1, v3<4: v3, v4, v5, v1, v2(3.1)Meanwhile on 6 vertices with d = 4 we have n = 2 and so by proposition 2.3, require8 + 6 = 14 edges. But K6 only has(62)= 15 edges to begin with, and so there is only onegraph to consider (see figure 3.3). Given this, we suggest the following 4-realizer:<1: v3, v4, v5, v2, v1, v6<2: v3, v4, v6, v2, v1, v5<3: v3, v5, v6, v1, v2, v4<4: v4, v5, v6, v1, v2, v3(3.2)As assumed in figure 3.3 (b), here v3, v4, v5, v6 form our clique. The reader can checkthe the above forms a suspended anti-chain, and that an edge appears in 3.3 (a) if and onlyif it satisfies the candidate pair and 1-of-d properties in our 4-realizer. Since all graphswith 14 edges on 6 vertices are isomorphic (under a relabelling) to 3.3 (a), this shows all7123 45Figure 3.1: K5, The complete graph on 5 verticessuch graphs indeed have a d-realizer.Thus 7 is truly the smallest number of vertices it is possible to find a counter exampleon. We close this section with a figure displaying, supposedly, the only 3 graphs on 7vertices who have some 4-realizer (see figure 3.3). Generating such graphs was an attemptby the author to confirm their supposed 7-vertex counter example indeed had no 4-realizer.The observant reader may be alarmed by their similarity to our counter-example, but onchecking the degree sequence we find they are not actually isomorphic.These graphs were generated by computing all possible (ordered) quadruples of per-mutations of 1-2-3, keeping only those with empty intersection, and then appendingsuspension vertices. The graphs were then ‘induced’ according to our two edge requirementsand drawn in Mathematica. Mathematica was also used to remove isomorphic graphs- whittling down an original 906 to merely 3. The c++ code used can be found here:https://github.com/krstnmnlsn/d-realizers3.4 Thoughts on a CharacterizationIn d = 3, as explained above, we get that the set of graphs with a 3-realizer is exactly theset of maximal graphs, and so the author wondered naturally if the characterization ofthose graphs that have a d-realizer somehow generalized this quality.3though hack job would be an understatement in describing it and caution is advised813456 2(a) The graph K6 minus a single edge13456 2(b) With an example 4-clique droppedFigure 3.2: The only graph possible on 6 vertices is K6 short one edge. For clarity (b) omitsone possible choice of 4-clique, using the suspension vertices v1, v2, v3, v4Figure 3.3: The 3 graphs found on 7 vertices to have a 4-realizer9Of course, without a lot of background graph-theoretic knowledge there wasn’t muchhope, but wikipedia was trawled and the author now has quite a few questions. We startedat the definition of maximality using planarity: where a graph is maximal if a singleadditional edge will always make it non-planar. But this seems a bit ugly, since there areseveral triangular graphs that don’t fit this definition (C3 and K4) - and our use of maximalcertainly includes these graphs.One interesting characterization found was that the triangulated graphs are preciselythose forming the skeletons of the simplicial polyhedra, or those containing only triangularfaces. We wonder4 then if the graphs with d-realizers form the 1-skeletons of some classof possibly simplicial d-polytopes. Unfortunately d-polytopes, even 4-polytopes or poly-chorons, don’t seem to be terribly well understood yet so the author was unable to findmany examples or even a sanity check.The only actual simplical polychoron we were able to find was the 4-simplex, apparentlythe 4-dimensional analog of a tetrahedron. The 1-skeleton of this is K5, which we haveshown previously to indeed have a 4-realizer.One other fact of interest is a result found on wikipedia, that the 1-skeleton of ak-dimensional convex polytope is a k-connected graph [3]. Perhaps this could be used toquickly find a counter-example to our above hypothesis, though Mathematica has so farconfirmed the graphs previously shown to have a 4-realizer also are 4-vertex connected5.5 Unrelated RemarksI came across 2 minor typos in [2], first in the definition of candidate pair I believe z shouldbe greater than x and y in some order pii, not less. Probably it would be okay to flipabsolutely everything, but currently it is inconsistent with the proof of proposition 1. Theonly other thing is in the first line of the proof of prop. 1 v ∈ V should be x ∈ V , or elseall the later x’s flipped to v’s.Finally, this paper would not have been possible without Paul Liu’s life-saving sanitycheck abilities and Mathematica knowledge. I’d also like to thank Will Evans for the verycool project and for having the patience to accepting this paper so late6.4and really just are curious, and not trying to suggest it is so, having no intuition or knowledge at all5d spanning trees should give one d-edge-connectedness, but not necessarily d-vertex-connectedness Ibelieve6“By Friday” effectively means, by the time reasonable people wake up on Saturday, right?10References[1] W. Schnyder, Planar graphs and poset dimension, Order 5 (1989), no. 4, 323-343.[2] W. Evans, S. Felsner, S. Kobourov, T. Ueckerdt, Graphs admitting d-realizers:spanning-tree-decompositions and box-representations, EuroCG (2014)[3] M. Balinski, On the graph structure of convex polyhedra in n-space, Pacific Journal ofMathematics 11 (1961), no. 2, 431434.11


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items