Journal of Graph Algorithms and Applications

The Journal of Graph Algorithms and Applications (JGAA) is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. JGAA is supported by distinguished advisory and editorial boards, has high scientific standards and is distributed in electronic form. JGAA is a gold open access journal that charges no author fees.

View full aims and scope

News

October 2019. The Executive Committee of JGAA is pleased to announce the appointment of Martin Nöllenburg to the Editorial Board of JGAA.

April 2019. The Executive Committee of JGAA is pleased to announce the appointment of Guy Even, Yoshio Okamoto, and Ignaz Rutter to the Editorial Board of JGAA.

Recently Published

DOI: 10.7155/jgaa.00544

Problems on One Way Road Networks

Jammigumpula Ajay, Avinandan Das, Binayak Dutta, Arindam Karmakar, Sasanka Roy, and Navaneeta Saikia

Vol. 24, no. 3, pp. 523-546, 2020. Regular paper.

DOI: 10.7155/jgaa.00543

An Adaptive Version of Brandes' Algorithm for Betweenness Centrality

Matthias Bentert, Alexander Dittmann, Leon Kellerhals, André Nichterlein, and Rolf Niedermeier

Vol. 24, no. 3, pp. 483-522, 2020. Regular paper.

DOI: 10.7155/jgaa.00542

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A.W.M. de Kroon, and Rolf Morel

Vol. 24, no. 3, pp. 461-482, 2020. Regular paper.

DOI: 10.7155/jgaa.00541

Enumerating Grid Layouts of Graphs

Peter Damaschke

Vol. 24, no. 3, pp. 433-460, 2020. Regular paper.

DOI: 10.7155/jgaa.00540

An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Oscar E. García-Quintero, and Carlos Hidalgo-Toscano

Vol. 24, no. 3, pp. 421-432, 2020. Regular paper.

DOI: 10.7155/jgaa.00539

Smoothed Analysis of the Minimum-Mean Cycle Canceling Algorithm and the Network Simplex Algorithm

Kamiel Cornelissen and Bodo Manthey

Vol. 24, no. 3, pp. 397-421, 2020. Regular paper.

DOI: 10.7155/jgaa.00538

Graph Motif Problems Parameterized by Dual

Guillaume Fertin and Christian Komusiewicz

Vol. 24, no. 3, pp. 371-396, 2020. Regular paper.

DOI: 10.7155/jgaa.00537

On L-shaped point set embeddings of trees: first non-embeddable examples

Torsten Mütze and Manfred Scheucher

Vol. 24, no. 3, pp. 343-369, 2020. Regular paper.

DOI: 10.7155/jgaa.00536

Improved Bounds for Track Numbers of Planar Graphs

Sergey Pupyrev

Vol. 24, no. 3, pp. 323-341, 2020. Regular paper.

DOI: 10.7155/jgaa.00534

On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow

Kateřina Altmanová, Petr Kolman, and Jan Voborník

Vol. 24, no. 3, pp. 303-322, 2020. Regular paper.

DOI: 10.7155/jgaa.00533

Not all planar graphs are in PURE-4-DIR

Daniel Gonçalves

Vol. 24, no. 3, pp. 293-301, 2020. Concise paper.

DOI: 10.7155/jgaa.00530

Graph Stories in Small Area

Manuel Borrazzo, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani

Vol. 24, no. 3, pp. 269-292, 2020. Regular paper.

DOI: 10.7155/jgaa.00529

A Note on Universal Point Sets for Planar Graphs

Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner

Vol. 24, no. 3, pp. 247-267, 2020. Regular paper.

DOI: 10.7155/jgaa.00528

Parameterized Complexity of Safe Set

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, and Yota Otachi

Vol. 24, no. 3, pp. 215-245, 2020. Regular paper.

DOI: 10.7155/jgaa.00527

Bounds and algorithms for graph trusses

Paul Burkhardt, Vance Faber, and David G. Harris

Vol. 24, no. 3, pp. 191-214, 2020. Regular paper.

DOI: 10.7155/jgaa.00525

On the Approximability of the Minimum Weight $t$-partite Clique Problem

Geoffrey Solano, Guillaume Blin, Mathieu Raffinot, Jhoirene Clemente, and Jaime Caro

Vol. 24, no. 3, pp. 171-190, 2020. Regular paper.

DOI: 10.7155/jgaa.00523

Maximum Cut Parameterized by Crossing Number

Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, and Alexander Nover

Vol. 24, no. 3, pp. 155-170, 2020. Regular paper.

DOI: 10.7155/jgaa.00522

Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network

Wilfried Ehounou, Dominique Barth, Arnaud de Moissac, Dimitri Watel, and Marc-Antoine Weisser

Vol. 24, no. 3, pp. 133-153, 2020. Regular paper.

Just Accepted

The following papers have been accepted to be published in the JGAA Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019. These papers will receive a volume, an issue number, and page numbers when the whole special issue will be published.

DOI: 10.7155/jgaa.00524

Recognizing Stick Graphs with and without Length Constraints

Steven Chaplick, Philipp Kindermann, Andre Löffler, Florian Thiele, Alexander Wolff, Alexander Zaft, and Johannes Zink

Vol. 0, no. 0, pp. 0-0, 0. Regular paper.

DOI: 10.7155/jgaa.00526

Parameterized Algorithms for Book Embedding Problems

Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, and Martin Nöllenburg

Vol. 0, no. 0, pp. 0-0, 0. Regular paper.

DOI: 10.7155/jgaa.00531

Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity

Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, and Thomas Schneck

Vol. 0, no. 0, pp. 0-0, 0. Regular paper.