\begin{thebibliography}{10}

\bibitem{BL}
C.~P. Bonnington and C.~H.~C. Little.
\newblock {\em The foundations of topological graph theory}.
\newblock Springer, 1995.

\bibitem{CNN}
M.~Chrobak, J.~Naor, and M.~Novick.
\newblock Using bounded degree spanning trees in the design of efficient
  algorithms on claw free graphs.
\newblock In {\em Proceedings of the Workshop on Algorithms and Data
  Structures, Lecture Notes in Computer Science Vol 382}, pages 147--162,
  Ottawa, Canada, 1989. Springer-Verlag.

\bibitem{DHK}
E.~Dahlhaus, P.~Hajnal, and M.~Karpinski.
\newblock On the parallel complexity of {H}amiltonian cycles and matching
  problem in dense graphs.
\newblock {\em Journal of Algorithms}, 15:367--384, 1993.

\bibitem{DK}
E.~Dahlhaus and M.~Karpinski.
\newblock The matching problem for strongly chordal graphs is in {NC}.
\newblock Technical Report 855-CS, University of Bonn, 1986.

\bibitem{DK2}
E.~Dahlhaus and M.~Karpinski.
\newblock Perfect matching for regular graphs is {AC}$^0$-hard for the general
  matching problem.
\newblock {\em Journal of Computer and System Sciences}, 44(1):94--102, 1992.

\bibitem{DS}
E.~Dekel and S.~Sahni.
\newblock Parallel matching algorithm for convex bipartite graphs and
  applications to scheduling.
\newblock {\em Journal of Parallel and Distributed Computing}, 1(2):185--205,
  1984.

\bibitem{Gabow}
H.~N. Gabow.
\newblock Using euler partitions to edge-colour bipartite multi-graphs.
\newblock {\em International Journal of Computer and Information Science},
  5(4):345--355, Dec 1976.

\bibitem{GL-EJC1}
A.~Galluccio and M.~Loebl.
\newblock On the theory of {P}faffian orientations {I}: {P}erfect matchings and
  permanents.
\newblock {\em The Electronic Journal of Combinatorics}, R6, 1999.

\bibitem{GPST}
M.~Goldberg, S.~Plotkin, D.~Shmoys, and {\'{E}}.~Tardos.
\newblock Using interior-point methods for fast parallel algorithms for
  bipartite matching and related problems.
\newblock {\em SIAM Journal on Computing}, 21(1):140--150, 1992.

\bibitem{GPV}
M.~Goldberg, S.~Plotkin, and M.~Vaidya.
\newblock Sublinear time parallel algorithms for matching and related problems.
\newblock {\em Journal of Algorithms}, 14:180--213, 1993.

\bibitem{GK}
D.~Grigoriev and M.~Karpinski.
\newblock The matching problem for bipartite graphs with polynomially bounded
  permanents is in {NC}.
\newblock In {\em Proceedings of 28th IEEE Conference on Foundations of
  Computer Science}, pages 166--172. {IEEE} Computer Society Press, 1987.

\bibitem{He}
X.~He.
\newblock A nearly optimal parallel algo for constructing maximal independent
  set in planar graphs.
\newblock {\em Theoretical Computer Science}, 61:33--47, 1988.

\bibitem{JaJa}
J.~Ja'Ja'.
\newblock {\em Introduction to Parallel Algorithms}.
\newblock Addison-Wesley, 1992.

\bibitem{KUW}
R.~M. Karp, E.~Upfal, and A.~Wigderson.
\newblock Constructing a perfect matching is in random {NC}.
\newblock {\em Combinatorica}, 6:35--48, 1986.

\bibitem{KarpinskiRytter}
M.~Karpinski and W.~Rytter.
\newblock {\em Fast parallel algorithms for graph matching problems}.
\newblock Oxford University Press, Oxford, 1998.
\newblock Oxford Lecture Series in Mathematics and its Applications 9.

\bibitem{Kastelyn}
P.~W. Kastelyn.
\newblock Graph theory and crystal physics.
\newblock In F.~Harary, editor, {\em Graph Theory and Theoretical Physics},
  pages 43--110. Academic Press, 1967.

\bibitem{KVV}
D.~Kozen, U.~Vazirani, and V.~Vazirani.
\newblock {NC} algorithms for comparability graphs, interval graphs, and
  testing for unique perfect matching.
\newblock In {\em Proceedings of {FST\&TCS} Conference, {LNCS} Volume 206},
  pages 496--503. Springer-Verlag, 1985.

\bibitem{Kul}
R.~Kulkarni.
\newblock A new {NC} algorithm for perfect matchings in regular bipartite
  graphs of polylog degree.
\newblock In {\em Proceedings of {CIAC} Conference, {LNCS} Volume 3998}, pages
  308--319. Springer-Verlag, 2006.

\bibitem{KM04}
R.~Kulkarni and M.~Mahajan.
\newblock Seeking a vertex of the planar matching polytope in {NC}.
\newblock In {\em Proceedings of the 12th European Symposium on Algorithms ESA,
  LNCS vol.\ 3221}, pages 472--483. Springer, 2004.

\bibitem{LPV}
G.~Lev, M.~Pippenger, and L.~Valiant.
\newblock A fast parallel algorithm for routing in permutation networks.
\newblock {\em {IEEE} Transactions on Computers}, C-30:93--100, 1981.

\bibitem{little}
C.~H.~C. Little.
\newblock An extension of {K}asteleyn's method of enumerating the 1-factors of
  planar graphs.
\newblock In {\em Combinatorial Mathematics, Proc. $2^{nd}$ Australian
  Conference}, pages 63--72. D.Holton, {\em Lecture Notes in Mathematics}, 403,
  1974.

\bibitem{Lovasz}
L.~Lov\'asz.
\newblock On determinants, matchings and random algorithms.
\newblock In L.~Budach, editor, {\em Proceedings of Conference on Fundamentals
  of Computing Theory}, pages 565--574. Akademia-Verlag, 1979.

\bibitem{LP86}
L.~Lov\'asz and M.~Plummer.
\newblock {\em Matching Theory}.
\newblock North-Holland, 1986.
\newblock Annals of Discrete Mathematics 29.

\bibitem{Luby}
M.~Luby.
\newblock A simple parallel algorithm for the maximal independent set problem.
\newblock {\em SIAM Journal on Computing}, 15:1036--1053, 1986.

\bibitem{MSV04}
M.~Mahajan, P.~R. Subramanya, and V.~Vinay.
\newblock The combinatorial approach yields an {NC} algorithm for computing
  {P}faffians.
\newblock {\em Discrete Applied Mathematics}, 143(1-3):1--16, September 2004.

\bibitem{MV-STOC00}
M.~Mahajan and K.~Varadarajan.
\newblock A new {NC}-algorithm for finding a perfect matching in planar and
  bounded genus graphs.
\newblock In {\em Proceedings of the Thirty-Second Annual {ACM} Symposium on
  Theory of Computing ({STOC})}, pages 351--357, 2000.

\bibitem{MillerNaor}
G.~Miller and J.~Naor.
\newblock Flow in planar graphs with multiple sources and sinks.
\newblock {\em SIAM Journal on Computing}, 24:1002--1017, 1995.

\bibitem{Mohar}
B.~Mohar.
\newblock A linear time algorithm for embedding graphs in an arbitrary surface.
\newblock {\em SIAM Journal on Discrete Mathematics}, 12(1):6--26, Feb 1999.

\bibitem{MVV}
K.~Mulmuley, U.~Vazirani, and V.~Vazirani.
\newblock Matching is as easy as matrix inversion.
\newblock {\em Combinatorica}, 7(1):105--131, 1987.

\bibitem{Parfenoff}
I.~Parfenoff.
\newblock An efficient parallel algorithm for maximum matching for some classes
  of g raphs.
\newblock {\em Journal of Parallel and Distributed Computing}, 52(1):96--108,
  1998.

\bibitem{TV91}
R.~Tamassia and J.~F. Vitter.
\newblock Parallel transitive closure and point location in planar structures.
\newblock {\em SIAM Journal on Computing}, 20(4):708--725, 1991.

\bibitem{Thomassen89}
C.~Thomassen.
\newblock The graph genus problem is {NP}-complete.
\newblock {\em Journal of Algorithms}, 10(4):568--576, Dec 1989.

\bibitem{Thomassen}
C.~Thomassen.
\newblock {\em Embeddings and minors}, pages 301--349.
\newblock Elsevier Science, 1995.

\bibitem{val79}
L.~G. Valiant.
\newblock The complexity of computing the permanent.
\newblock {\em Theoretical Computer Science}, 8:189--201, 1979.

\bibitem{Vaz}
V.~Vazirani.
\newblock {NC} algorithms for computing the number of perfect matchings in
  ${K}_{3,3}$-free graphs and related problems.
\newblock {\em Information and Computation}, 80(2):152--164, 1989.

\bibitem{Vazbook}
V.~Vazirani.
\newblock Parallel graph matching.
\newblock In J.~Reif, editor, {\em Synthesis of Parallel Algorithms}.
  Kaufman-Morgan, 1991.
\newblock chapter 18.

\bibitem{vollmertext}
H.~Vollmer.
\newblock {\em Introduction to Circuit Complexity: A Uniform Approach}.
\newblock Springer-Verlag New York Inc., 1999.

\bibitem{White}
A.~T. White.
\newblock {\em Graphs, Groups and Surfaces}.
\newblock North-Holland, Amsterdam, 1973.

\end{thebibliography}