Graph Algorithms and Applications 1.
Title:
Graph Algorithms and Applications 1.
Author:
Tamassia, Roberto.
ISBN:
9789812777638
Personal Author:
Physical Description:
1 online resource (439 pages)
Contents:
Contents -- Volume 1:1-3 (1997) -- 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms -- 1 Introduction -- 2 Branch and Cut for One Sided Crossing Minimization -- 3 One Sided Crossing Minimization -- 4 Two Sided Crossing Minimization -- 5 Conclusions -- References -- Optimal Algorithms to Embed Trees in a Point Set -- 1 Introduction -- 2 Hull Trees -- 3 Embedding a Rooted Tree with the Root on the Convex Hull -- 4 Embedding a Rooted Tree -- 5 Finding Degree-constrained Embeddings -- 6 Lower Bounds -- References -- Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction Max Cut and Coloring -- 1 Introduction -- 2 Preliminaries -- 3 Simple Local Search -- 4 Modified Local Search -- 5 Applications to Induced Subgraph Problems and Graph Coloring -- References -- Volume 2:1-8 (1998) -- Algorithms for Cluster Busting in Anchored Graph Drawing -- 1 Introduction -- 2 Related Work -- 3 Measuring Similarity and Distribution -- 4 The Layout Algorithms -- 5 Results -- 6 Conclusions and Future Work -- References -- A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Broadcasting Algorithm -- 4 Conclusion -- References -- A Visibility Representation for Graphs in Three Dimensions -- 1 Introduction -- 2 An Upper Bound -- 3 A Lower Bound -- 4 Additional Results -- 5 Conclusions and Open Problems -- References -- Scheduled Hot-Potato Routing -- 1 Introduction -- 2 Model -- 3 Use of a Given Schedule -- 4 Designing an Optimal Schedule -- 5 Conclusion -- References -- Treewidth and Minimum Fill-in on d-trapezoid Graphs -- 1 Introduction -- 2 Preliminaries -- 3 d-Trapezoid Graphs -- 4 Minimal Triangulations of d-trapezoid Graphs -- 5 Small Scanlines and Dense Sequences -- 6 Algorithms -- References.
Memory Paging for Connectivity and Path Problems in Graphs -- 1 Introduction -- 2 Path-paging -- 3 Connectivity-paging -- 4 Link paging -- 5 Conclusions and open problems -- References -- New Lower Bounds For Orthogonal Drawings -- 1 Introduction -- 2 Definitions -- 3 Non-planar Drawings -- 4 Non-planar Drawings of Planar Graphs -- 5 Plane Drawings of Planar Graphs -- 6 Planar Drawings of Planar Graphs -- 7 Remarks and Open Problems -- References -- Rectangle-visibility Layouts of Unions and Products of Trees -- 1 Introduction -- 2 Background and Definitions -- 3 Unions with depth-1 Trees and Forests -- 4 Unions with depth-2 Trees -- 5 Unions with depth-3 Trees and Matchings -- 6 Cartesian Products -- References -- Volume 3:1-3 (1999) -- Edge-Coloring and f-Coloring for Various Classes of Graphs -- 1 Introduction -- 2 Preliminary -- 3 Chromatic Index -- 4 Finding Edge-Colorings -- 5 f-Coloring -- 6 Conclusion -- References -- Experimental Comparison of Graph Drawing Algorithms for Cubic Graphs -- 1 Introduction -- 2 Basic Definitions -- 3 The Algorithms Under Evaluation -- 4 Analysis of the Experimental Results -- 5 Conclusions -- References -- Subgraph Isomorphism in Planar Graphs and Related Problems -- 1 Introduction -- 2 New Results -- 3 Related Work -- 4 Bounded Tree-Width Subgraph Isomorphism -- 5 Neighborhood Covers -- 6 The Subgraph Isomorphism Algorithm -- 7 Further Improvements -- 8 Variations and Applications -- 9 Shortest Path Data Structure -- 10 Other Graph Families -- 11 Conclusions and Open Problems -- References -- Volume 3:4 (1999) -- New Trends in Graph Drawing Special Issue on Selected Papers from the 1997 Symposium on Graph Drawing -- Guest Editors' Introduction -- Drawing Clustered Graphs on an Orthogonal Grid -- 1 Introduction -- 2 Terminology.
3 Orthogonal Drawings for C-planar Clustered Graphs -- 4 A Lower Bound for Bends -- 5 Remarks -- References -- A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Orthogonal Drawing -- 4 Bend Minimization -- 5 Grid Drawing -- 6 Conclusions -- References -- Bounds for Orthogonal 3-D Graph Drawing -- 1 Introduction -- 2 Lower Bounds -- 3 Constructions -- 4 Conclusions -- 5 Acknowledgments -- References -- Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions -- 1 Introduction -- 2 Preliminaries -- 3 Drawing Graphs with Maximum Degree Six -- 4 A Model for Vertices of High Degree -- 5 Drawing Graphs of High Degree -- 6 Conclusions and Open Problems -- References.
Abstract:
This book contains volumes 1-3 of the Journal of Graph Algorithms and Applications (JGAA) . Topics of interest include design and analysis of graph algorithms, experiences with graph algorithms, and applications of graph algorithms. JGAA is supported by distinguished advisory and editorial boards, has high scientific standards, and takes advantage of current electronic document technology. The electronic version of JGAA is available on the Web at http://www.cs.brown.edu/publications/jgaa/. Contents: Volume 1: 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms (M Jünger & P Mutzel); Optimal Algorithms to Embed Trees in a Point Set (P Bose et al.); Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring (M M Halldórsson & H C Lau); Volume 2: Algorithms for Cluster Busting in Anchored Graph Drawing (K A Lyons et al.); A Broadcasting Algorithm with Time and Message Optimum on Arrangement Graphs (L Bai et al.); A Visibility Representation for Graphs in Three Dimensions (P Bose et al.); Scheduled Hot-Potato Routing (J Naor et al.); Treewidth and Minimum Fill-in on d -trapezoid Graphs (H L Bodlaender et al.); Memory Paging for Connectivity and Path Problems in Graphs (E Feuerstein & A Marchetti-Spaccamela); New Lower Bounds for Orthogonal Drawings (T C Biedl); Rectangle-visibility Layouts of Unions and Products of Trees (A M Dean & J P Hutchinson); Volume 3: Edge-Coloring and f -Coloring for Various Classes of Graphs (X Zhou & T Nishizeki); Experimental Comparison of Graph Drawing Algorithms for Cubic Graphs (T Calamoneri et al.); Subgraph Isomorphism in Planar Graphs and Related Problems (D Eppstein); Guest Editors' Introduction (G Di Battista & P Mutzel); Drawing Clustered Graphs on an Orthogonal Grid (P Eades et al.); A Linear Algorithm for Bend-Optimal
Orthogonal Drawings of Triconnected Cubic Plane Graphs (M S Rahman et al.); Bounds for Orthogonal 3-D Graph Drawing (T Biedl et al.); Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions (A Papakostas & I G Tollis). Readership: Researchers and professionals in theoretical computer science, computer engineering and combinatorics & graph theory.
Local Note:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Subject Term:
Genre:
Added Author:
Electronic Access:
Click to View