Journal of Graph Algorithms and Applications

http://jgaa.info ISSN: 1526-1719

Volume 13, 2009

Volume 13, no. 1, 2009
Special Issue on Selected Papers from the Second International Workshop on Algorithms and Computation, WALCOM 2008

• Guest Editor's Foreword
  Md. Saidur Rahman
  Vol. 13, no. 1, pp. 3-4, 2009.
  • article (PDF)
• Listing All Plane Graphs
  Katsuhisa Yamanaka and Shin-ichi Nakano
  Vol. 13, no. 1, pp. 5-18, 2009. Regular paper.
  Submitted: January 2008.
  Reviewed: June 2008. Revised: July 2008.
  Accepted: November 2008. Final: December 2008.
  Published: February 2009.
  Communicated by Md. Saidur Rahman.
  
  • article (PDF)
• On the Approximability of Comparing Genomes with Duplicates
  Sébastien Angibaud, Guillaume Fertin, Irena Rusu, Annelyse Thévenin and Stéphane Vialette
  Vol. 13, no. 1, pp. 19-53, 2009. Regular paper.
  Submitted: January 2008.
  Reviewed: July2008. Revised: July 2008.
  Accepted: November 2008. Final: December 2008.
  Published: February 2008.
  Communicated by Md. Saidur Rahman.
  
  • article (PDF)
• The Multi-Commodity Source Location Problems and the Price of Greed
  Hiro Ito , Mike Paterson and Kenya Sugihara
  Vol. 13, no. 1, pp. 55-73, 2009.
  Submitted: January 2008.
  Reviewed: July 2008. Revised: August 2008.
  Reviewed: November 2008. Revised: November 2008.
  Reviewed: December 2008. Revised: December 2008.
  Accepted: December 2008. Final: January 2009.
  Published: February 2009.
  Communicated by Md. Saidur Rahman.
  
  • article (PDF)

Volume 13, no. 2, 2009

• Algorithm Engineering for Optimal Graph Bipartization
  Falk Hüffner
  Vol. 13, no. 2, pp. 77-98, 2009. Regular paper.
  Submitted: November 2007.
  Accepted: August 2008. Final: September 2008.
  Published: February 2009.
  Communicated by Dorothea Wagner.
  
  • article (PDF)
• Degree-constrained edge partitioning in graphs arising from discrete tomography
  Cedric Bentz, Marie-Christine Costa, Christophe Picouleau, Bernard Ries and Dominique de Werra
  Vol. 13, no. 2, pp. 99-118, 2009. Regular paper.
  Submitted: February 2007.
  Reviewed: September 2008. Revised: October 2008.
  Accepted: November 2008. Final: January 2009.
  Published: February 2009.
  Communicated by Larse Arge.
  
  • article (PDF)
• Vertex Bisection is Hard, too
  Ulrik Brandes and Daniel Fleischer
  Vol. 13, no. 2, pp. 119-131, 2009.
  Submitted: December 2005.
  Reviewed: April 2006. Revised: April 2007.
  Accepted: February 2009. Final: Februrary 2009.
  Published: April 2009.
  Communicated by Susanne Albers.
  
  • article (PDF)
• The Black-and-White Coloring Problem on Trees
  Daniel Berend and Shira Zucker
  Vol. 13, no. 2, pp. 133-152, 2009. Regular paper.
  Submitted: June 2008.
  Reviewed: February 2009. Revised: March 2009.
  Accepted: March 2009. Final: April 2009.
  Published: June 2009.
  Communicated by Henk Meijer.
  
  • article (PDF)
• On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
  Md. Rezaul Karim and Md. Saidur Rahman
  Vol. 13, no. 2, pp. 153-177, 2009. Regular paper.
  Submitted: April 2008.
  Reviewed: January 2009. Revised: February 2009.
  Accepted: April 2009. Final: April 2009.
  Published: June 2009.
  Communicated by Petra Mutzel.
  
  • article (PDF)
• New Approximation to the One-sided Radial Crossing Minimization
  Seok-Hee Hong and Hiroshi Nagamochi
  Vol. 13, no. 2, pp. 179-196, 2009. Regular paper.
  Submitted: September 2008.
  Reviewed: February 2009. Revised: March 2009.
  Accepted: April 2009. Final: May 2009.
  Published: June 2009.
  Communicated by Giuseppe Liotta.
  
  • article (PDF)
• Finding Large Clique Minors is Hard
  David Eppstein
  Vol. 13, no. 2, pp. 197-204, 2009.
  Submitted: June 2008.
  Reviewed: April 2009. Revised: May 2009.
  Accepted: July 2009. Final: July 2009.
  Published: July 2009.
  Communicated by Giuseppe Liotta.
  
  • article (PDF)
• Intersection Graphs in Simultaneous Embedding with Fixed Edges
  Michael Jünger and Michael Schulz
  Vol. 13, no. 2, pp. 205-218, 2009. Regular paper.
  Submitted: March 2009.
  Reviewed: June 2009. Revised: July 2009.
  Accepted: July 2009. Final: July 2009.
  Published: July 2009.
  Communicated by Stephen Kobourov.
  
  • article (PDF)
• Towards an optimal algorithm for recognizing Laman graphs
  Ovidiu Daescu and Anastasia Kurdia
  Vol. 13, no. 2, pp. 219-232, 2009. Concise paper.
  Submitted: April 2008.
  Reviewed: December 2008. Revised: January 2009.
  Reviewed: May 2009. Revised: May 2009.
  Accepted: July 2009. Final: July 2009.
  Published: July 2009.
  Communicated by Ioannis G. Tollis.
  
  • article (PDF)
• The Knapsack Problem with Conflict Graphs
  Ulrich Pferschy and Joachim Schauer
  Vol. 13, no. 2, pp. 233-249, 2009. Regular paper.
  Submitted: October 2008.
  Reviewed: May 2009. Revised: July 2009.
  Final: August 2009.
  Published: October 2009.
  Communicated by Dorothea Wagner.
  
  • article (PDF)
• Generating connected and 2-edge connected graphs
  Angela Mestre
  Vol. 13, no. 2, pp. 251-281, 2009. Regular paper.
  Submitted: December 2007.
  Reviewed: October 2008. Revised: January 2009.
  Accepted: August 2009. Final: September 2009.
  Published: October 2009.
  Communicated by Ulrik Brandes.
  
  • article (PDF)

Volume 13, no. 3, 2009
Special Issue on Selected Papers from the Fifteenth International Symposium on Graph Drawing, GD 2007

• Guest Editors' Foreword
  Seok-Hee Hong and Takao Nishizeki
  Vol. 13, no. 3, pp. 285-287, 2009.
  • article (PDF)
• Algorithms for Multi-Criteria Boundary Labeling
  Marc Benkert, Herman Haverkort, Moritz Kroll and Martin Nöllenburg
  Vol. 13, no. 3, pp. 289-317, 2009. Regular paper.
  Submitted: December 2007.
  Reviewed: June 2008. Revised: August 2008.
  Accepted: November 2008. Final: December 2008.
  Published: November 2009.
  Communicated by Seok-Hee Hong and Takao Nishizeki.
  
  • article (PDF)
• DAGmaps: Space Filling Visualization of Directed Acyclic Graphs
  Vassilis Tsiaras, Sofia Triantafilou and Ioannis G. Tollis
  Vol. 13, no. 3, pp. 319-347, 2009. Regular paper.
  Submitted: January 2008.
  Reviewed: April 2008. Revised: August 2008.
  Accepted: December 2008. Final: January 2009.
  Published: November 2009.
  Communicated by Seok-Hee Hong and Takao Nishizeki.
  
  • article (PDF)
• Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces
  Giuseppe Di Battista and Fabrizio Frati
  Vol. 13, no. 3, pp. 349-378, 2009. Regular paper.
  Submitted: December 2007.
  Reviewed: May 2008. Revised: August 2008.
  Accepted: November 2008. Final: December 2008.
  Published: November 2009.
  Communicated by Seok-Hee Hong and Takao Nishizeki.
  
  • article (PDF)
• Clustered Planarity: Small Clusters in Cycles and Eulerian Graphs
  Eva Jelínková, Jan Kára, Jan Kratochvíl, Martin Pergel, Ondrej Suchý and Tomáš Vyskocil
  Vol. 13, no. 3, pp. 379-422, 2009. Regular paper.
  Submitted: December 2007.
  Reviewed: November 2008. Revised: February 2009.
  Accepted: August 2009. Final: September 2009.
  Published: November 2009.
  Communicated by Seok-Hee Hong and Takao Nishizeki.
  
  • article (PDF)
• Matched Drawings of Planar Graphs
  Emilio Di Giacomo, Walter Didimo, Marc van Kreveld, Giuseppe Liotta and Bettina Speckmann
  Vol. 13, no. 3, pp. 423-445, 2009. Regular paper.
  Submitted: December 2007.
  Reviewed: May 2008. Revised: August 2008.
  Accepted: November 2008. Final: November 2008.
  Published: November 2009.
  Communicated by Seok-Hee Hong and Takao Nishizeki.
  
  • article (PDF)
• Constrained Simultaneous and Near-Simultaneous Embeddings
  Fabrizio Frati, Michael Kaufmann and Stephen Kobourov
  Vol. 13, no. 3, pp. 447-465, 2009. Regular paper.
  Submitted: December 2007.
  Reviewed: May 2008. Revised: August 2008.
  Accepted: November 2008. Final: December 2008.
  Published: November 2009.
  Communicated by Seok-Hee Hong and Takao Nishizeki.
  
  • article (PDF)