Graphs

Many thanks to Laurence Pelletier, P. Ossona de Mendez, Victor Jimenez, and Pablo Moscato for contributions.

Contents:

• Related Link Collections
• Online Forums
• Open Problems
• Topics
• Search & Find
• Software
• Books & Lecture Notes
• People

Related Link Collections

• Graph Theory Resources [D.P. Sanders]
• Graph Theory [Rob Pratt, University of North Carolina]
• Michael Trick's Operations Research Page
• Dictionary of Algorithms, Data Structures, and Problems

Online Forums

• GRAPHNET a mailing list distributing conference announcements, problems etc.
• ORCS-L: the Operations Research - Computer Science Interface

Open Problems

• Problem session of the International Colloquium on Extremal Graph Theory (Balatonlelle, Hungary, July 27 - August 2, 1997)
• Open Problems of Paul Erdös, by Fan Chung
• Douglas West's Open Problem Columns
• Problems in Topological graph theory, compiled by Dan Archdeacon (Vermont) (local copy as of August 1995, gzipped file)
• Bondy & Murthy's Unsolved Problems: partly with annotations, also some additional problems by Stephen C. Locke (Florida)
• Open problems in graph minors, by Nathaniel Dean (local copy, gzipped file)
• Open problems, by Jerry Spinrad (Vanderbilt)
• Conjectures produced by the program Graffiti [E. DeLaVina and S. Fajtlowicz, Houston TX]

Topics

Search & Find...

• ...People:

 

 

AMS - SIAM - MAA combined membership list
Theoretical Computer Science Virtual Address Book (ACM SIGACT)
Combinatorial People and Groups at The World Combinatorics Exchange (Georgia Tech)
Trick's Operations Research People directory
Mathematical Programming Society - Search Members
OPT-NET Memberlist (DMV-SIGOPT)
INFORMS Membership Database
WhoWhere - E-mail adresses
 
 

• ...Bibliographic Data:

 

 

Zentralblatt MATH Database (FIZ, Karlsruhe)
Collection of CS Bibliographies (Achilles, Karlsruhe)
Annual Comprehensive Index Bibliographic Database (INFORMS)
 
 

• ...Journals:

 

 

Graph Theory Journals (D.P. Sanders, Princeton)
Discrete Math Journals (DMV-FG DM)
Operations Research Journals
Computer Science Journals (DB & LP, Uni Trier)
 
 

• ...Conferences:

 

 

Graph Theory Conferences (D.P. Sanders, Princeton);
The WWW Virtual Library: Conferences by Jürgen Wagner (Fraunhofer Institute for Industrial Engineering);
Theory Calendar: Events & Conferences by Lenwood S. Heath (Virginia Tech.);
Conference CFPs, Programs, Schools, by GI-Fachgruppe parallele und verteilte Algorithmen (Paderborn);
Netlib Conferences Database.
Discrete Math Conferences, Workshops, Events... (DMV FG Diskrete Mathematik)

Software

• Optimization Codes in Public Domain (Jiefeng Xu, Boulder)
• The LEDA Library (Saarbrücken)
• Standford GraphBase, by D. Knuth (Stanford)
• LINK - a software system for discrete mathematics (a DIMACS project)
• The Stony Brook Algorithm Repository, by J. Richard Bradley and Steven S. Skiena
• ABACUS, by Stefan Thienel (Köln)
• Minimum Cut Algorithms (Chekuri, Goldberg, Karger, Levine, and Stein)
• Matching; maximum-flow; MCF - a network simplex implementation for the min cost flow problem, by Andreas Löbel (ZIB); check Andrew V. Goldberg's page for shortest path, assignment, minimum-cost flow, or minimum cut algorithms.
• nauty: a program for automorphism groups and canonically labellings, by McKay (Canberra)
• Groups & Graphs: a software package for graphs, digraphs, combinatorial designs, and their automorphism groups, by B. Kocay (Winnipeg)
• PlaNet: a demonstration package for algorithms on planar networks, by G. Neyer, W. Schlickenrieder, D. Wagner and K. Weihe (Konstanz)
• Map Labeling, by A. Wolff (Berlin)

Books & Lecture Notes

Recent Text Books & Lecture Notes

• Diestel, R.: Graph Theory, Springer, 1997.
• Emden-Weinert, Th., Hougardy, S., Kreuter, B., Steger, A., Prömel, H.J.: Einführung in Graphen und Algorithmen, Manuskript, Humboldt-Universität zu Berlin, 1996.
• West, D.: Introduction to Graph Theory, Prentice Hall, 1995; see also updates

Monographs

• Ahuja, R.K., Magnanti, T.L., and Orlin, J.B.: Network flows: theory, algorithms, and applications, Prentice-Hall, Englewood Cliffs NJ, 1993
• Aigner, M., Ziegler, G.M.: Proofs from THE BOOK, Springer, corr. 2nd printing, 1998.
• N. Noga Alon and J.H. Spencer: The probabilistic method, Wiley & Sons, New-York, 1992
• Biggs, N.L., Lloyd, E.K., Wilson, R.J.: Graph Theory 1736-1936, Clarendon Press, Oxford, 1976 (ISBN 0-19-853901-0)
• Cameron, P.J., Van Lint, J.H.: Designs, graphs, codes and their links, Cambridge Univ. Press, 1991.
• Chung, F.R.K.: Spectral graph theory, AMS, 1997.
• Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial optimization, John Wiley and Sons, New York, 1998.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms, McGraw-Hill, New York, 2. Ed., 1990.
• Cvetkovic, D., Rowlinson, P., Slobodan: Eigenspaces of Graphs, Cambridge University Press, 1997.
• Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics, Springer Series ``Algorithms and Combinatorics'' Vol. 15, 1997.
• Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph drawing - algorithms for the visualization of graphs. Prentice-Hall, 1999.
• Fleischner, H.: Eulerian Graphs and Related Topics, Ann. Disc. Math. 45 bzw. 50, North-Holland, Amsterdam, 1990 bzw. 1991.
• Godsil, C.D., Royle, G.F.: Algebraic Graph Theory, in preparation; table of contents
• Golumbic, M.C.: Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980.
• Gross, Jonathan L.; Tucker, Thomas W.: Topological graph theory. New York, John Wiley & Sons, 1987.
• Gusfield, D., Irving, R.W., The stable marriage problem: structure and algorithms, MIT Press, Cambridge MA, 1989.
• Harary, F., Palmer, E.M.: Graphical enumeration, Academic Press, New York, 1973.
• Horowitz, E., Sahni, S., Rajasekaran, S.: Computer algorithms, W. H. Freeman Press, 1998.
• Hwang, F.K., Richards, D.S., and Winter, P.: The Steiner Tree Problem, Ann. Disc. Math. 53, North-Holland, Amsterdam, 1992.
• Jensen, T.R., Toft, B.: Graph coloring problems, Wiley-Interscience, New York, 1995.
• Jungnickel, D.: Graphen, Netzwerke und Algorithmen, Spektrum Akad. Verlag, Heidelberg, 3. Auflage, 1994.
• Karpinski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problems, Oxford Lecture Series in Mathematics and Its Applications No.9, Clarendon Press, November 1997.
• Knuth, D.E.: Stable marriage and its relation to other combinatorial problems, CRM Proc. & LN Vol. 10, AMS, 1997 (original French edition: Univ. Montreal, 1981).
• Lovasz, L.: Combinatorial Problems and Exercises, North-Holland, Amsterdam, 1979, 2. edition 1993.
• Lovasz, L., and Plummer, M.D.: Matching Theory, Ann. Disc. Math. 29, North-Holland, Amsterdam, 1986.
• Mahadev, N. V. R., Peled, U. N.: Threshold Graphs and Related Topics, Annals of Discrete Mathematics 56, North-Holland, Amsterdam, 1995.
• T.A. McKee, F.R. McMorris: Topics in Intersection Graph Theory,

SIAM Monograph on Discrete Math. and Appl., 1999.
• Mohar, B., Thomassen, C.: Graphs on surfaces, Johns Hopkins University Press, to appear.
• Motwani, R., and Raghavan, P.: Randomized Algorithms, Cambridge Univ. Press, 1995
• Nishizeki, T., Chiba, N.: Planar graphs: theory and algorithms, North-Holland, Amsterdam, 1988.
• Papadimitriou, C.H.: Computational complexity, Addison-Wesley, Reading MA, 1994.
• Scheinerman, E.R., Ullman, D.H.: Fractional graph theory: a rational approach to the theory of graphs, John Wiley & Sons, New York, 1997.
• Soifer, Alexander: MATHEMATICAL COLORING BOOK
• Voss, H.-J.: Cycles and bridges in graphs, Kluwer Acad. Publ., Dordrecht / Deutscher Verlag der Wissenschaften, Berlin, 1991.
• White, A.T.: Graphs, Groups and Surfaces, North-Holland, Amsterdam, 2. Edition, 1984.
• Zhang, C.-Q.: Integer flows and cycle covers of graphs, Marcel Dekker, New York, 1997.

Anthologies

• Network Models, Handbooks in OR & MS, Vol. 7, Eds. Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L., Elsevier, Amsterdam, 1995.
• Network Routing, Handbooks in OR & MS, Vol. 8, Eds. Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L., Elsevier, Amsterdam, 1995.
• Graph connections -- relationships between graph theory and other areas of mathematics, Eds. Beineke, L., Wilson, R., Oxford University Press, 1997.
• Combinatorial optimization, Eds. Cook, W., Lovasz, L., Seymour, P.D., DIMACS series in discrete mathematics and theoretical computer science, Vol. 20, AMS, 1995
• Annotated Bibliographies in Combinatorial Optimization, Eds.: Dell'Amico, M., Maffioli, F., Martello, S., Wiley and Sons, Chichester, 1997.
• HANDBOOK OF COMBINATORICS, Eds. Graham, R.L., Grötschel, M., and Lovasz, L., MIT Press, 1996.
• Approximation Algorithms for NP-Hard Problems, Ed. Hochbaum, D.S., PWS Publishers, Boston, 1996.
• Cliques, coloring, and satisfiability, Eds. Johnson, D.S., Trick, M., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 26, AMS, 1996.
• Synthesis of Parallel Algorithms, Ed. Reif, R.H., Morgan Kaufmann Publ., San Mateo CA, 1993.

Other collections

• Graph Theory Books [Stephen C. Locke, Florida]
• Collection of Data Structures & Algorithms Course Notes [Kirk Pruhs]
• Collection of Lecture Notes, Survey Papers and Papers [A. Czumaj and M. Kutylowski, Paderborn]

Selected People

Daniel P. Sanders' list of A Few Graph Theorists' Home Pages

Network Programming People, a list compiled by Ernesto Martins

Alon, Noga (Tel Aviv)

Archdeacon, Dan (Vermont)

Arkin, Esther M. (Stony Brook)

Arnborg, Stefan (Stockholm)

Arora, Sanjeev (Princeton)

Bar-Yehuda, Reuven (Technion)

Blum, Avrim (Carnegie Mellon)

Bodlaender, Hans (Utrecht)

Bollobas, Bela (Memphis, TN)

Brandstädt, Andreas (Rostock)

Brandt, Stephan (Berlin)

Brunetta, Lorenzo (Milano)

Cameron, Peter (London)

Chartrand, Gary (Michigan)

Chung, Fan (Philadelphia)

Chvátal, Vašek (Piscataway, NJ)

Cook, William J. (Houston)

Corneil, Derek G. (Toronto)

Dean, Nathaniel (Bell Labs, NJ)

De Fraysseix, Hubert (C.N.R.S., Paris)

De Mendez, Patrice Ossona (C.N.R.S., Paris)

Diestel, Reinhard (Hamburg)

Djidjev, Hristo (Rice)

Eppstein, David (Irvine CA)

Erdös, Paul (see also The Erdös Number Project, and In Memoriam )

Fajtlowicz, S. (Houston TX)

Faudree, Ralph (Memphis)

Fellows, Michael (Victoria BC)

Fleischner, Herbert (Wien)

Frieze, Alan (Carnegie Mellon)

Garg, Naveen (Saarbrücken)

Godsil, Chris (Waterloo, CA)

Goemans, Michel X. (MIT)

Goldberg, Andrew V. (NEC Research Institute)

Goldberg, Mark K. (Troy)

Golumbic, Martin Charles (Bar-Ilan)

Grable, David A. (Berlin)

Grötschel, Martin (Berlin)

Grossman, Jerry (Oakland)

Gustedt, Jens (Berlin)

Halldorsson, Magnus M. (Reykjavik)

Harary, Frank (Las Cruces, NM)

Hassin, Refael (Tel Aviv)

Heath, Lenwood S. (Virginia Tech.)

Hoang, Chinh T. (Thunder Bay)

Hobbs, Arthur (Waterloo)

Hochbaum, Dorit (Berkeley)

Hougardy, Stefan (Berlin)

Hsu, Wen-Lian

Jensen, Tommy R. (Chemnitz)

Jerrum, Mark (Edinburgh)

Johnson, David (AT&T)

Jünger, Michael (Köln)

Kann, Vigo (Stockholm)

Karger, David R. (MIT)

Karisch, Stefan E. (Kobenhavn)

Karpinski, Marek (Bonn)

Kaufmann, Michael (Tübingen)

Khuller, Samir (Maryland)

Klein, Philip (Brown)

Kleinberg, Jon (Cornell)

Knuth, Don (Stanford)

Kocay, Bill (Winnipeg)

Kratochvil, Jan (Prague)

Kratsch, Dieter (Jena)

Kreuter, Bernd (Heidelberg)

Langston, Michael A. (Knoxville)

Van Leeuwen, J. (Utrecht)

Lengauer, Thomas (Sankt Augustin)

Lovasz, Laszlo (Yale)

Maffray, Frédéric (Grenoble)

Martins, Ernesto (Coimbra)

McConnell, Ross (Salem)

McDiarmid, Colin J. (Oxford)

McKay, Brendan (Australian National University)

Mehlhorn, Kurt (Saarbrücken)

Mohar, Bojan (Ljubljana)

Möhring, Rolf H. (Berlin)

Motwani, Rajeev (Stanford)

Naor, Joseph (Technion)

Nash-Williams, C.St.J.A. (Reading)

Nesetril, J. [Email]

Panconesi, Alessandro (Venezia)

Papadimitriou, Christos H. (Berkeley)

Penn, Michal (Haifa)

Plummer, Michael (Nashville)

Preissmann, Myriam (Grenoble)

Prisner, Erich (Hamburg)

Prömel, Hans-Jürgen (Berlin)

Proskurowski, Andrzej (Eugene)

Pulleyblank, William (IBM Watson)

Rabani, Yuval (Technion)

Raghavachari, Balaji (Dallas)

Ramachandran, Vijaya (Austin)

Ravi, R. (Carnegie Mellon)

Robinson, Robert W. (Georgia)

Royle, Gordon (Nedlands, AU)

Sanders, Daniel P. (Princeton)

Scheffler, Petra (Stralsund)

Scheinerman, Edward (Johns Hopkins)

Schelp, Richard (Memphis)

Shamir, Ron (Tel Aviv)

Shmoys, David B. (Cornell)

Sinclair, Alistair (Berkeley)

Spencer, Joel (Courant Institute)

Spinrad, Jerry (Vanderbilt)

Steger, Angelika (München)

Stewart, Lorna (Edmonton)

Székely, László (Columbia)

Tamassia, Roberto (Brown)

Tardos, Éva (Cornell)

Thomas, Robin (Georgia Tech)

Thomassen, Carsten (Denmark)

Toft, Bjarne (Odense)

Turau, Volker (Wiesbaden)

Tuza, Zsolt (Budapest) [E-Mail]

Vazirani, Vijay V. (Georgia Tech)

Wagner, Dorothea (Konstanz)

Weihe, Karsten (Konstanz)

Welsh, D.J.A (Oxford)

West, Douglas (Urbana)

Williamson, David P. (Watson)

Winter, Pawel (Kobenhavn)

Woodall, Douglas R. (Nottingham)

Wormald, Nick (Melbourne)

Yannakakis, Mihalis (Bell Labs)

Zachariasen, Martin (Kobenhavn)

Zelikovsky, Alexander (Los Angeles)