Reading group in graph algorithms

Papers (in reverse chronological order):

• Representing edge intersection graphs of paths on degree 4 trees. (Elad).
  M. Golumbic, M. Lipshteyn, M. Stern. Discrete Mathematics 308 (8), pp. 1381-1387, 2008.
• Splitting planar graphs into 3 forests, one of which has bounded degree.. (Therese)
  D. Goncalves, J. COmb. Theory B 99 (2009), 314-322.
• Hexagonal Grid Drawings (all of us):
  This one will be relevant to drawing 3-graphs with integer edge lengths. We should all read it. G. Kant, Hexagonal Grid Drawings, WG '92.
• Maximum planar subgraphs (Terry):
  Terry will give some results about hardness of the maximum planar subgraph problems; a web page with references is here.
• Drawings with integer edge lengths (Elena):
  J. Geelen, A. Guo and D. McKinnon, J. Graph Theory 58 (3), pp. 270-274, April 2008.
• Wooden Geometric Puzzles (Therese):
  H. Alt, H. Bodlaneder, M. van Kreveld, G. Rote, G. Tel, Theory of Computing Systems vol. 44, no.2, February 2009.
• Drawing Hypergraphs (Michal):
  M. Kaufmann, M. van Krevel and B. Speckmann, Subdivision Drawings of Hypergraphs. Proceedings of Graph Drawing 2008, LNCS 5417, 2009.
• Drawing (Complete) Binary Tanglegrams (Ruth):
  K. Buchin et al., Proceedings of Graph Drawing 2008, LNCS 5417, pp. 324-335, 2009.
• SPQR-trees (Terry):
  G. Di Battista and R. Tamassia, On-line Maintenance of triconnected components with SPQR-trees, Algorithmica 15 (4), April 1996, pp. 302-318.
• Every planar graph is 5-choosable (Elena):
  C. Thomassen, J. Combinatorial Theory Series B, vol. 62, no. 1, pp. 180-181, 1994.
• Moving vertices to make drawings plane (Therese):
  Goaoc, Kratochvil, Okamoto, Shin and Wolff, Graph Drawing 2007.
• 3D drawings
  DiGiacomo et al: Straight-line 3D grid drawings with linear volume, CGTA 2005.
  Biedl,Thiele,Wood: 3D orthogonal graph drawing with optimal volume, Algorithmica 2006
• High-degree orthogonal drawings
  Foessmeier, Kaufmann, GD 1995.
  Biedl, Kaufmann, ESA 1997.
• Orthogonal drawings via small separators.
  Leiserson: Area-efficient representations for VLSI
  
• Orthogonal drawings: vertex-addition approach
  Biedl/Kant: A better heuristic for orthogonal graph drawings. CGTA 1996
  Biedl: Lower bounds on orthogonal graph drawings, JGAA 1998
  
• Orthogonal drawings: bend-optimality via flow networks
  Tamassia: Bend-optimal orthogonal drawings of planar graphs, SIAM J. Computing 1987.
• Drawing SP-graphs.
  Bertolazzi et al., Drawings of series-parallel graphs, IJCGA 1994.
  (The above link is the conference version, the journal version doesn't seem to be accessible electronically, but is in the library.)
  Biedl: Small area-drawings of series-parallel graphs (CS-2007-23)
  Frati: Drawing outerplanar graphs in O(dn log n) area (CCCG 07)
  Frati: Lower bounds for drawing series-parallel graphs (WG 08)
  
• Planar straightline drawings of planar graphs via trees.
  Schnyder, Embedding Planar Graphs on the Grid, SODA 1990.
  Fusy, Transversal Structures on Triangulations, with Application to Straight-Line Drawing. Graph Drawing 2005: 177-188
  (There is also a journal version to appear.)
  
• Planar straight-line drawings of planar graphs via canonical ordering.
  de Fraysseix, Pach, Pollack, Drawing planar graphs on a grid, Algorithmica 1990.
  Kant, Drawing graphs using the canonical ordering. Algorithmica, 1992