| Other fesources:
|
Two online resources are recommended:
- graphclasses.org.
More graph classes than you ever knew existed, with relationships
between them and complexities of various problems.
- wikipedia. Normally one should
be careful in using wikipedia as a research resource, since it is
not curated. However, most web pages on relevant topics (e.g.
treewidth and pathwidth) were written by
David Eppstein
and seem to be monitored by him. David is a prominent
researcher in the field; if you see his name frequently in the
revision history then the page is probably trustworthy.
Also numerous other good textbooks:
- Graph Classes: A Survey (A. Brandstädt, V.B. Le,
J.P. Spinrad), SIAM Monographs on Discrete Mathematics
and Applications, SIAM, 1999.
Excellent overview of graph classes
with lots of references, but no proofs.
Available from the WLU library, call number QA166 .B73.
- Planar graphs: theory and algorithms (T. Nishizeki, N.
Chiba), North-Holland publisher, 1988.
Decent reference for planar graphs, but a bit old.
Available from the UW library, call number QA1.N855 no. 140.
- Planar graph drawing (T. Nishizeki, Md. S. Rahman),
Lecture Notes Series on Computing, Volume 12, World Scientific,
2004.
Newer book with focus on drawing graphs, but also some background
on planar graphs in general. Sadly not available from the UW
libraries unless you happen to be a Guelph user.
- Algorithmic Graph Theory and Perfect Graphs (M.C. Golumbic),
Academic Press, New York, 1980. 2nd edition 2004.
Great reference for interval graphs and friends, but a bit out of
date. (The 2nd edition is essentially the same as the 1st, except
for an epilogue chapter.)
Available from the UW library, call number (1st ed.) QA166.G64 1980
and (2nd ed.) QA166.G64 2004.
- H. Bodlaender and A. Koster, Combinatorial Optimization on Graphs of Bounded Treewidth,
The Computer Journal 51 (3), 255-269, 2008.
One of the (many) review articles that Bodlaender wrote about treewidth
and its algorithmic applications. Some of the older articles (search
for MFCS 1998, TCS 1998 or SOFSEM 2005) go more in-depth into some of
these topics, but of course are more outdated.
- Graph Theory (R. Diestel), Springer Verlag, 1997 (and multiple
later edition).
Good for minor theory; also discusses planar graphs and partial
k-trees.
Available from the UW library, call number QA166.D51413 2000.
The book website has
a free preview version available electronically.
|
