@TechReport{Dartmouth:TR94-206,
  author = {Dimitrios Kavvadias and Grammati E. Pantziou and Paul G. Spirakis and Christos D. Zaroliagis},
  title = {{Efficient Sequential and Parallel Algorithms for the Negative Cycle Problem}},
  institution = {Dartmouth College, Computer Science},
  address = {Hanover, NH},
  number = {PCS-TR94-206},
  year = {1994},
  URL = {http://www.cs.dartmouth.edu/reports/TR94-206.pdf},
  abstract = {
    	We present here an algorithm for detecting (and outputting, if
    exists) a negative cycle in an $n$-vertex planar digraph $G$ with real
    edge weights. Its running time ranges from $O(n)$ up to $O(n^{1.5}\log
    n)$ as a certain topological measure of $G$ varies from $1$ up to
    $\Theta(n)$.  Moreover, an efficient CREW PRAM implementation is
    given.  Our algorithm applies also to digraphs whose genus $\gamma$ is
    $o(n)$.
  }
}