Graph-Theoretic Concepts in Computer Science

Maximum Cardinality Search for Computing Minimal Triangulations.- DNA Sequencing, Eulerian Graphs, and the Exact Perfect Matching Problem.- On the Minimum Size of a Contraction-Universal Tree.- Optimal Area Algorithm for Planar Polyline Drawings.- Cycles in Generalized Networks.- New Graph Classes of Bounded Clique-Width.- More about Subcolorings.- Search in Indecomposable Graphs.- On the Complexity of (k, l)-Graph Sandwich Problems.- Algorithms and Models for the On-Line Vertex-Covering.- Weighted Node Coloring: When Stable Sets Are Expensive.- The Complexity of Restrictive H-Coloring.- A New 3-Color Criterion for Planar Graphs.- An Additive Stretched Routing Scheme for Chordal Graphs.- Complexity of Pattern Coloring of Cycle Systems.- Safe Reduction Rules for Weighted Treewidth.- Graph Separator Algorithms: A Refined Analysis.- Generalized H-Coloring and H-Covering of Trees.- The Complexity of Approximating the Oriented Diameter of Chordal Graphs.- Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies.- Completely Independent Spanning Trees in Maximal Planar Graphs.- Facets of the Directed Acyclic Graph Layering Polytope.- Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.- Complexity of Some Infinite Games Played on Finite Graphs.- New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k-Disjoint Cycles on Plane and Planar Graphs.- A Multi-scale Algorithm for the Linear Arrangement Problem.- On the b-Chromatic Number of Graphs.- Budgeted Maximum Graph Coverage.- Online Call Admission in Optical Networks with Larger Demands.- The Forest Wrapping Problem on Outerplanar Graphs.- On the Recognition of P 4 -Comparability Graphs.- Bend-Minimum Orthogonal Drawings of Plane 3-Graphs.- Cluster Graph Modification Problems.- Two Counterexamples in Graph Drawing.- Connected and Loosely Connected List Homomorphisms.- Any Load-Balancing Regimen for Evolving Tree Computations on Circulant Graphs Is Asymptotically Optimal.