CanaDAM 2011 Université de Victoria, 31 mai - 3 juin 2011 www.smc.math.ca//2011f

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

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.