Schnyder's Theorem - Other Graphs

Other Graphs

As Schnyder observes, the incidence poset of a graph G has order dimension two if and only if the graph is a path or a subgraph of a path. For, the only possible realizer for the incidence poset consists of two total orders that (when restricted to the graph's vertices) are the reverse of each other; otherwise, the intersection of the two orders would include an order relation between two vertices, which is not allowed for incidence posets. But two total orders on the vertices that are the reverse of each other can realize any subgraph of a path, by including the edges of the path in the ordering immediately following the later of the two edge endpoints.

If a graph can be colored with four colors, then its incidence poset has order dimension at most four (Schnyder 1989).

The incidence poset of a complete graph on n vertices has order dimension (Spencer 1971).

Read more about this topic:  Schnyder's Theorem

Other articles related to "graphs, graph":

Squaregraph - Characterization
... in several ways other than via their planar embeddings They are the median graphs that do not contain as an induced subgraph any member of an infinite family of forbidden graphs ... These forbidden graphs are the cube (the simplex graph of K3), the Cartesian product of an edge and a claw K1,3 (the simplex graph of a claw), and the graphs formed from a gear graph by adding one more ... They are the graphs that are connected and bipartite, such that (if an arbitrary vertex r is picked as a root) every vertex has at most two neighbors closer to r, and such that at every vertex v, the link of v (a graph ...
Graphs, Maps & Trees - Miscellanea
... "Graphs, Maps Trees" is the first single by Assembly Now to have an accompanying music video ...
Squaregraph - Related Graph Classes
... The squaregraphs include as special cases trees, grid graphs, gear graphs, and the graphs of polyominos ... As well as being planar graphs, squaregraphs are median graphs, meaning that for every three vertices u, v, and w there is a unique median vertex m(u,v,w) that lies on shortest paths between each ... As with median graphs more generally, squaregraphs are also partial cubes their vertices can be labeled with binary strings such that the Hamming distance between strings is equal to the shortest path ...