Drawing Pfaffian Graphs

Norine, Serguei (2004) Drawing Pfaffian Graphs. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 371-376 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_37).

Full text not available from this repository.

Abstract

We prove that a graph is Pfaffian if and only if it can be drawn in the plane (possibly with crossings) so that every perfect matching intersects itself an even number of times.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_37
Classifications:Z Theory > Z.250 Geometry
ID Code:605

Repository Staff Only: item control page

References

A. Galluccio and M. Loebl, On the theory of Pfaffian orientations. I. Perfect matchings and permanents, Electron. J. combin. 6 (1999), no. 1, Research Paper 6, 18pp. (electronic)

P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dinner arrangements on a quadratic lattice, Physica 27 (1961), 1209-1225.

P. W. Kasteleyn, Dimer statistics and phase transitions, J. Mathematical Phys. 4 (1963), 287-293.

P. W. Kasteleyn, Graph Theory and Crystal Physics, Graph Theory and Theoretical Physics, Academic Press, London, 1967, 43-110.

V. Klee, R. Lardner and R. Manber, Signsolvability revisited, Linear Algebra Appl. 59 (1984), 131-157.

C. H. C. Little, A characterization of convertible (0,1)-matrices, J. Comb. Theory B 18 (1975), 187-208.

W. McCuaig, Polya's permanent problem, preprint.

S. Norine, Pfaffian graphs, T-joins and crossing numbers, submitted.

S. Nordine, in preparation.

J. Pach and G. Toth, Which crossing number is it anyway?, J. Comb. Theory Ser. B 80 (2000), no. 2, 225-246.

G. Pólya, Aufgabe 424, Arch. Math. Phys. Ser. 20 (1913), 271.

N. Robertson, P. D. Seymour and R. Thomas, Permanents, Pfaffian orientations, and even directed circuits, Ann. of Math. (2) 150(1999), 929-975.

P. Samuelson, Foundations of Economic Analysis, Atheneum, New York, 1971.

G. Tesler, Matching in graphs on non-orientable surfaces, J. Comb. Theory B 78 (2000), 198-231.

V. V. Vazirani and M. Yannakakis, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Discrete Appl. Math. 25 (1989), 179-190.