| 2004 | A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL. Franz Baader |
| 2004 | A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. Tim Nieberg, Johann L. Hurink, Walter Kern |
| 2004 | A Stochastic Location Problem with Applications to Tele-diagnostic. Nicola Apollonio, Massimiliano Caramia, Giuseppe F. Italiano |
| 2004 | A Symbolic Approach to the All-Pairs Shortest-Paths Problem. Daniel Sawitzki |
| 2004 | Bimodular Decomposition of Bipartite Graphs. Jean-Luc Fouquet, Michel Habib, Fabien de Montgolfier, Jean-Marie Vanherpe |
| 2004 | Characterization and Recognition of Generalized Clique-Helly Graphs. Mitre Costa Dourado, Fábio Protti, Jayme Luiz Szwarcfiter |
| 2004 | Collective Tree Spanners and Routing in AT-free Related Graphs. Feodor F. Dragan, Chenyu Yan, Derek G. Corneil |
| 2004 | Coloring a Graph Using Split Decomposition. Michaël Rao |
| 2004 | Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs. Zhi-Zhong Chen, Tatsuie Tsukiji |
| 2004 | Constant Time Generation of Trees with Specified Diameter. Shin-Ichi Nakano, Takeaki Uno |
| 2004 | Core Stability of Minimum Coloring Games. Thomas Bietenhader, Yoshio Okamoto |
| 2004 | Crossing Reduction in Circular Layouts. Michael Baur, Ulrik Brandes |
| 2004 | Decremental Clique Problem. Fabrizio Grandoni, Giuseppe F. Italiano |
| 2004 | Edge-Connectivity Augmentation and Network Matrices. Michele Conforti, Anna Galluccio, Guido Proietti |
| 2004 | Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs. Valentin E. Brimkov, Reneta P. Barneva, Reinhard Klette, Joseph Straight |
| 2004 | Elegant Distance Constrained Labelings of Trees. Jirí Fiala, Petr A. Golovach, Jan Kratochvíl |
| 2004 | Exact (Exponential) Algorithms for the Dominating Set Problem. Fedor V. Fomin, Dieter Kratsch, Gerhard J. Woeginger |
| 2004 | Finding k Disjoint Triangles in an Arbitrary Graph. Mike Fellows, Pinar Heggernes, Frances A. Rosamond, Christian Sloper, Jan Arne Telle |
| 2004 | Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs. Christophe Crespelle, Christophe Paul |
| 2004 | Graph-Theoretic Concepts in Computer Science, 30th International Workshop,WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers Juraj Hromkovic, Manfred Nagl, Bernhard Westfechtel |
| 2004 | Lexicographic Breadth First Search - A Survey. Derek G. Corneil |
| 2004 | Linear Kernels in Linear Time, or How to Save k Colors in O(n Benny Chor, Mike Fellows, David W. Juedes |
| 2004 | Minimal de Bruijn Sequence in a Language with Forbidden Substrings. Eduardo Moreno, Martín Matamala |
| 2004 | Octagonal Drawings of Plane Graphs with Prescribed Face Areas. Md. Saidur Rahman, Kazuyuki Miura, Takao Nishizeki |
| 2004 | On the Maximum Cardinality Search Lower Bound for Treewidth. Hans L. Bodlaender, Arie M. C. A. Koster |
| 2004 | Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size. Takehiro Ito, Xiao Zhou, Takao Nishizeki |
| 2004 | Planar Graphs, via Well-Orderly Maps and Trees. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Dominique Poulalhon, Gilles Schaeffer |
| 2004 | Recognizing HHD-free and Welsh-Powell Opposition Graphs. Stavros D. Nikolopoulos, Leonidas Palios |
| 2004 | The Computational Complexity of the Minimum Weight Processor Assignment Problem. Hajo Broersma, Daniël Paulusma, Gerard J. M. Smit, Frank Vlaardingerbroek, Gerhard J. Woeginger |
| 2004 | The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small. Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos |
| 2004 | Tolerance Based Algorithms for the ATSP. Boris Goldengorin, Gerard Sierksma, Marcel Turkensteen |
| 2004 | Treelike Comparability Graphs: Characterization, Recognition, and Applications. Sabine Cornelsen, Gabriele Di Stefano |
| 2004 | Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters. Mordecai J. Golin, Yiu-Cho Leung |
| 2004 | Wireless Networking: Graph Theory Unplugged. Roger Wattenhofer |