1
$\begingroup$

In the (very nice) article of Goldstein and Turner untitled Applications of Topological Graph Theory to Group Theory, the following definitions can be found:

Definitions: A circle graph is a pair $(G,S)$ where $G$ is a trivalent graph and $S$ a Hamiltonian cycle. (Topologically, a circle graph consists of a circle together with a finite number of arcs whose end points are disjoint on the circle.)

An embedding of a circle graph is defined as a piecewise linear embedding $f : (G,S) \to (M,\partial M)$ where $M$ is obtained from a closed 2-manifold $\hat{M}$ by removing an open 2-cell.

Finally, the oriented genus $\gamma^0(G,S)$ of $(G,S)$ is the genus of the oriented manifold $\hat{M}$ of minimal genus so that there exists an embedding of $(G,S)$ into $(M, \partial M)$

If $g(G,S)$ denotes the usual genus of the associated graph, the inequality $g(G,S) \leq \gamma^0(G,S)$ is clear. Does the equality hold?

$\endgroup$
  • $\begingroup$ It's not really relevant for your question, but this terminology is not good, because there's already a different and more standard definition for a circle graph: it's the intersection graph of a collection of chords of a circle. $\endgroup$ – David Eppstein Aug 3 '14 at 6:43
1
$\begingroup$

Finally, I found that $\gamma^0(G,S)$ and $g(G,S)$ can be quite different. For example, let $(G,S)$ be the following circle graph:

enter image description here

Using properties proved in Goldstein and Turner's article, $\gamma^0(G,S)=3$ (see the picture below for a visual justification). However, it is clear that $g(G,S)=0$. In fact, the example generalizes easily to get, for all $n \geq 1$, a circle graph $(G,S)$ satisfying $\gamma^0(G,S)=n$ but $g(G,S)=0$.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.