Trees and circle orders

This paper continues a recent resurgence of interest in combinatorial properties of a poset that are associated with graph properties of its cover graph and order diagram. The following two theorems appearing in a 1977 paper of Trotter and Moore have played important roles in motivating this more modern research: (1) The dimension of a poset is at most 3 when its cover graph is at tree; (2) The dimension of a poset is at most 3 when the poset has a zero and its order diagram is planar. Although the underlying ideas lay dormant for more than 30 years, the first of these two results has become the base case for recent results bounding the dimension of a poset in terms of (a) the tree-width of its cover graph, and (b) the maximum dimension of its blocks. The second result is the base case for bounding the dimension of a planar poset in terms of the number of minimal elements. Continuing with this line of research, we show that every poset whose cover graph is a tree is a circle order, i.e., it has a representation as a family of circular disks in the Euclidean plane partially ordered by inclusion.     

Posets with Cover Graph of Pathwidth two have Bounded Dimension

Joret, Micek, Milans, Trotter, Walczak, and Wang recently asked if there exists a constant d such that if P is a poset with cover graph of P of pathwidth at most 2, then dim(P)=d. We answer this question in the affirmative by showing that d=17 is sufficient. We also show that if P is a poset containing the standard example S ₅ as a subposet, then the cover graph of P has treewidth at least 3.     

Adjacency posets of planar graphs

In this paper, we show that the dimension of the adjacency poset of a planar graph is at most 8. From below, we show that there is a planar graph whose adjacency poset has dimension 5. We then show that the dimension of the adjacency poset of an outerplanar graph is at most 5. From below, we show that there is an outerplanar graph whose adjacency poset has dimension 4. We also show that the dimension of the adjacency poset of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poset of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poset of such a graph.     

The dimension of planar posets

A partially ordered set (poset) is planar if it has a planar Hasse diagram. The dimension of a bounded planar poset is at most two. We show that the dimension of a planar poset having a greatest lower bound is at most three. We also construct four-dimensional planar posets, but no planar poset with dimension larger than four is known. A poset is called a tree if its Hasse diagram is a tree in the graph-theoretic sense. We show that the dimension of a tree is at most three and give a forbidden subposet characterization of two-dimensional trees.     

Incidence Posets and Cover Graphs

We prove two theorems concerning incidence posets of graphs, cover graphs of posets and a related graph parameter. First, answering a question of Haxell, we show that the chromatic number of a graph is not bounded in terms of the dimension of its incidence poset, provided the dimension is at least four. Second, answering a question of K?í? and Ne?et?il, we show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most two.     

A bound on the treewidth of planar even-hole-free graphs

The class of planar graphs has unbounded treewidth, since the k×k grid, ∀k∈N, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G is an even-hole-free planar graph, then it does not contain a 9×9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 49.     

Tree-width and dimension

Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural graph theory parameter tree-width by proving that the dimension of a finite poset is bounded in terms of its height and the tree-width of its cover graph.     

Planar Posets,Dimension, Breadth and the Number of Minimal Elements

In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970’s, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset in terms of the number of minimal elements, where the starting point is the 1977 theorem of Trotter and Moore asserting that the dimension of a planar poset with a single minimal element is at most 3. By carefully analyzing and then refining the details of this argument, we are able to show that the dimension of a planar poset with t minimal elements is at most 2t + 1. This bound is tight for t = 1 and t = 2. But for t ≥ 3, we are only able to show that there exist planar posets with t minimal elements having dimension t + 3. Our lower bound construction can be modified in ways that have immediate connections to the following challenging conjecture: For every d ≥ 2, there is an integer f(d) so that if P is a planar poset with dim(P) ≥ f(d), then P contains a standard example of dimension d. To date, the best known examples only showed that the function f, if it exists, satisfies f(d) ≥ d + 2. Here, we show that lim _d→∞ f(d)/d ≥ 2.     

Topological Minors of Cover Graphs and Dimension

We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, our argument is entirely combinatorial and does not rely on structural decomposition theorems. Given a poset with large dimension but bounded height, we directly find a large clique subdivision in its cover graph. Therefore, our proof is accessible to readers not familiar with topological graph theory, and it allows us to provide explicit upper bounds on the dimension. With the introduced tools we show a second result that is supporting a conjectured generalization of the previous result. We prove that ‐free posets whose cover graphs exclude a fixed graph as a topological minor contain only standard examples of size bounded in terms of k.     

3-Interval irreducible partially ordered sets

In this paper we discuss the characterization problem for posets of interval dimension at most 2. We compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival [5], the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore [8] and by Kelly [4] and the characterization of bipartite 3-interval irreducible posets due to Trotter [9].We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformationP B(P), such that IdimP=dimB(P). This transformation has been introduced in [2].Supported by the DFG under grant FE 340/2–1.     

Algorithms for graphs of bounded treewidth via orthogonal range searching

We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlog^k−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlog^k+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.     

On the Boolean dimension of spherical orders

It is well known that if a planar order P is bounded, i.e. has only one minimum and one maximum, then the dimension of P (LD(P)) is at most 2, and if we remove the restriction that P has only one maximum then LD(P)3. However, the dimension of a bounded order drawn on the sphere can be arbitrarily large.The Boolean dimension BD(P) of a poset P is the minimum number of linear orders such that the order relation of P can be written as some Boolean combination of the linear orders. We show that the Boolean dimension of bounded spherical orders is never greater than 4, and is not greater than 5 in the case the poset has more than one maximal element, but only one minimum. These results are obtained by a characterization of spherical orders in terms of containment between circular arcs.Part of this work was carried out while both authors were visiting the Department of Applied Mathematics (KAM) of Charles University, Prague. The authors acknowledge support from the EU HCM project DONET.     

Graphs with Branchwidth at Most Three

In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition.     

A Note on Schnyder’s Theorem

We give an alternate proof of Schnyder’s Theorem, that the incidence poset of a graph G has dimension at most three if and only if G is planar.     

Dimension-2 poset competition numbers and dimension-2 poset double competition numbers

Let D=(V(D),A(D)) be a digraph. The competition graph of D, is the graph with vertex set V(D) and edge set . The double competition graph of D, is the graph with vertex set V(D) and edge set . A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R² and there is an arc going from a vertex (x₁,y₁) to a vertex (x₂,y₂) if and only if x₁>x₂ and y₁>y₂. We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.     

Improved bound for the dimension of posets of treewidth two

Joret et al. proved that posets with cover graphs of treewidth at most 2 have dimension at most 1276. Their proof is long and very complex. We give a short and much simpler proof that the dimension of such posets is at most 12.     

Dimension,Graph and Hypergraph Coloring

There is a natural way to associate with a poset P a hypergraph H _P, called the hypergraph of incomparable pairs, so that the dimension of P is the chromatic number of H _P. The ordinary graph G _P of incomparable pairs determined by the edges in H _P of size 2 can have chromatic number substantially less than H _P. We give a new proof of the fact that the dimension of P is 2 if and only if G _P is bipartite. We also show that for each t 2, there exists a poset P _t for which the chromatic number of the graph of incomparable pairs of P _t is at most 3 t – 4, but the dimension of P _t is at least (3 / 2) ^{t – 1}. However, it is not known whether there is a function f: NN so that if P is a poset and the graph of incomparable pairs has chromatic number at most t, then the dimension of P is at most f(t).     

Dimension and Matchings in Comparability and Incomparability Graphs

We develop some new inequalities for the dimension of a finite poset. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d=3, then there is a matching of size d in the comparability graph of P. There is no analogue of this result for cover graphs, as we show that there is a poset P of dimension d for which the maximum matching in the cover graph of P has size \(O(\log d)\). On the other hand, there is a dual result in which the role of chains and antichains is reversed, as we show that there is also a matching of size d in the incomparability graph of P. The proof of the result for comparability graphs has elements in common with Perles’ proof of Dilworth’s theorem. Either result has the following theorem of Hiraguchi as an immediate corollary: \(\dim (P)\le |P|/2\) when |P|=4.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.