CanaDAM 2011
Université de Victoria, 31 mai - 3 juin 2011

Embeddings and Geometric Representations of Graphs
Org: Debra Boutin (Hamilton College)

DAN ARCHDEACON, University of Vermont
The edge-ratio of geometric embeddings  [PDF]

A geometric embedding of a planar graph represents vertices by points and edges by non-crossing straight-line segments. We consider the ratio between the length of the longest edge and the shortest edge, more precisely, for a given graph we consider the infimum of this ratio over all geometric embeddings. While the ratio is unbounded in general, it is bounded for the classes of outer-planar graphs and bipartite graphs.

ANDREW BEVERIDGE, Macalester College
Directed Visibility Number for Planar Digraphs and Tournaments  [PDF]

The directed visibility number $b(G)$ of a digraph $G$ is the minimum $k$ such that each vertex of $G$ can be represented by at most $k$ horizontal segments in $\mathbb{R}^2$ with each arc $(u,v)$ of $G$ is realized by an upward visibility from a $u$-segment to a $v$-segment. We show that directed planar digraphs have $b(G)\leq4$, and outerplanar digraphs have $b(G)\leq3$. Also, every $n$-tournament has $b(G)\leq(n+1)/3+3$ and large transitive tournaments satisfy $b(G)\leq(3n+11)/14+41$.

SALLY COCKBURN, Hamilton College
Permutations and Geometric Realizations of $K_{2,n}$  [PDF]

Two geometric realizations of $G$ are geo-isomorphic if there is an isomorphism between them preserving edge crossings and non-crossings. Geo-homomorphisms, an extension of graph homomorphisms, define a partial order on geo-isomorphism classes. We investigate the homomorphism poset of $K_{2,n}$ by establishing a correspondence between realizations of $K_{2,n}$ and $S_n$, in which edge crossings correspond to inversions. We provide the number of geo-isomorphism classes for $n \leq 9$ and the complete poset for $n \leq 5$.

Posets of Geometric Graphs  [PDF]

{\it Joint work with Debra Boutin, Sally Cockburn, and Andrei Margea}.

We use geometric homomorphisms to introduce a partial order on the isomorphism classes of geometric realizations of a graph $G$. We develop tools to determine when two geometric realizations are comparable and give results for $P_n, C_n$ and $K_n$.

MARK ELLINGHAM, Vanderbilt University
Hamilton cycle embeddings of complete tripartite graphs  [PDF]

Ellingham and Stephens showed that if $m \ge n-1$ then in all but one case the nonorientable genus of $\overline{K_m} + K_n$ is the same as that of its subgraph $K_{m,n}$. Only partial results are known for the orientable case. We give new results using hamilton cycle embeddings of complete tripartite graphs $K_{n,n,n}$, which are of independent interest. We construct these embeddings using a variety of techniques. This is joint work with Justin Z. Schroeder.

Handling of online submissions has been provided by the CMS.


Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Société mathématique du Canada University of Victoria