Contents

• Contents
• License Terms and Availability
• Introduction
  • Overview
    • The Structure of AGD
    • Layout Algorithms in AGD
    • Standard Interfaces
  • Implementation of AGD
    • The Generic Graphics Interface
    • Handling Preconditions and Postconditions of Modules
  • Using AGD
• Technical Information
  • System Requirements
  • Compiling the Source Code Package
  • Usage of Header Files
  • Unix Object Code Installation and Usage
  • Windows Object Code Installation and Usage
• The AGD Server
  • Introduction
  • The GraphWin Client
  • The Command Line
  • Algorithms
  • Option File Format
  • The LEDA graph input/output format
    • Header Section
    • Nodes Section
    • Edges Section
  • The GraphWin (GW) File Format
    • Global Parameters
    • Node Attributes
    • Edge Attributes:
  • A complete example
• Base Classes
  • AGD Base ( AGD )
  • AGD Modules ( AGDModule )
  • Module Options ( AGDModuleOption )
  • Layout Interfaces ( LayoutInterface )
  • Layout Interfaces for Cluster Graphs ( CGLayoutInterface )
• Layout Algorithms
  • Layout Algorithms ( LayoutModule )
  • Grid Layout Algorithms ( GridLayoutModule )
  • Cluster Graph Layout Algorithms ( CGLayoutModule )
  • Cluster Graph Grid Layout Algorithms ( CGGridLayoutModule )
• Planarization-Based Layout Methods
  • The Planarization Method ( PlanarizationLayout )
  • Planarization on the Grid ( PlanarizationGridLayout )
  • The Pure Orthogonal Drawing Algorithm ( PureOrthogonalLayout )
  • The Quasi-Orthogonal Drawing Algorithm ( QuasiOrthogonalLayout )
  • The Orthogonal Drawing Algorithm ( OrthogonalLayout )
  • The Mixed-Model Algorithm ( MixedModelLayout )
• Planar Straight-Line Layout Methods
  • The de Fraysseix, Pach, Pollack Algorithm ( FPPLayout )
  • The Schnyder Algorithm ( SchnyderLayout )
  • The Convex Algorithm ( ConvexLayout )
  • The ConvexDraw Algorithm ( ConvexDrawLayout )
  • The PlanarStraight Algorithm ( PlanarStraightLayout )
  • The PlanarDraw Algorithm ( PlanarDrawLayout )
  • Visibility Representation ( VisibilityRepresentation )
• Hierarchical Layout Methods
  • Sugiyama's Algorithm ( SugiyamaLayout )
  • Interactive Sugiyama Layout ( InteractiveSugiyama )
• Force-Directed Layout Methods
  • Spring Embedder ( SpringLayout )
  • Tutte's Algorithm ( TutteLayout )
• Specialized Layout Methods
  • Walker's Algorithm ( TreeLayout )
• Layout Algorithms for Cluster Graphs
  • The Cluster-Orthogonal Algorithm ( ClusterOrthogonalLayout )
• Implementation of Layout Algorithms
  • Implementation of Layout Algorithms ( LayoutModuleImpl )
  • Concept for LEDA Graphs ( ConstLedaGraphConcept )
  • Concept for Graph Copies ( GraphCopyConcept )
  • Implementation of Grid Layout Algorithms ( GridLayoutModuleImpl )
  • Grid Concept for LEDA Graphs ( ConstLedaGraphGridConcept )
  • Grid Concept for Graph Copies ( GraphCopyGridConcept )
  • Grid Concept for Plane Graph Copies ( PlaneGraphCopyGridConcept )
  • Grid Concept for Orthogonal Representations ( OrthoRepGridConcept )
  • Implementation of Clustergraph Grid Layout Algorithms ( CGGridLayoutModuleImpl )
  • Grid Concept for Plane Cluster Graph Copies ( CGPlaneGraphCopyGridConcept )
• Augmentation
  • Augmentation Modules ( AugmentationModule )
  • Planar Biconnected ( PlanAug )
  • Optimal Planar Biconnected ( OptPlanAug )
  • LEDA's Make Biconnected ( LEDAMakeBiconnected )
• Computation of Subgraphs
  • Subgraph Modules ( SubgraphModule )
  • Planar Subgraphs ( PlanarSubgraph )
  • Naive Maximal Planar Subgraphs ( NaiveMaximalPlanarSubgraph )
  • Maximum Planar Subgraphs ( OptPlanarSubgraph )
  • LEDA's Make Acyclic ( LEDAMakeAcyclic )
  • Greedy Cycle Removal ( GreedyCycleRemoval )
  • Maximum Acyclic Subgraph ( OptAcyclicSubgraph )
  • Reduced Digraphs ( ReducedDigraph )
• Planarization
  • Planarization Modules ( PlanarizerModule )
  • Planarization with Planar Subgraph ( SubgraphPlanarizer )
• Edge Re-Insertion
  • Edge Insertion Modules ( EdgeInsertionModule )
  • Shortest Path Edge Inserter ( ShortestPathInserter )
• Compaction
  • Compaction Modules ( CompactionModule )
  • Longest Path-Based One-dim. Compaction ( LongestPathCompaction )
  • Flow-Based One-dimensional Compaction ( FlowCompaction )
  • Orthogonal Representations ( OrthogonalRepresentation )
• Rank Assignment
  • RankAssignment Modules ( RankAssignment )
  • Ranking to Minimize Height ( LongestPathRanking )
  • Ranking to Minimize Edge Lengths ( OptNodeRanking )
  • Ranking with Predefined Width ( CoffmanGrahamRanking )
  • Ranking by Depth First Search ( DfsRanking )
• Two Layer Crossing Minimization
  • Two Layer Crossing Minimization ( TwoLayerCrossMin )
  • Barycenter Heuristic ( BarycenterHeuristic )
  • Median Heuristic ( MedianHeuristic )
  • Weighted Median Heuristic ( WeightedMedianHeuristic )
  • Sifting Heuristic ( SiftingHeuristic )
  • Split Heuristic ( SplitHeuristic )
  • Greedy Insert ( GreedyInsertHeuristic )
  • Greedy Switch ( GreedySwitchHeuristic )
  • Optimal Crossing Minimization ( OptCrossMin )
• Layout of Hierarchies
  • Hierarchy Layout Modules ( HierarchyLayoutModule )
  • Fast Layout of Hierarchies ( FastHierarchyLayout )
  • Optimal Layout of Hierarchies ( OptCompCoord )
• Further Modules
  • Topology Modules ( TopologyModule )
  • Shape Module ( ShapeModule )
  • Testing Triconnectivity ( TriconnectivityTest )
  • C-Planarity Embedding ( CPlanarEmbed )
• Grid Coordinate Mappers
  • Grid Coordinate Mapper ( GridCoordinateMapper )
  • Mapping with Equal Sized Grid Width ( MaxAllMapper )
  • Mapping with Adjusted Grid Width ( MaxEachMapper )
  • Mapping with Fixed Grid Width ( FixedGridMapper )
  • Mapping with Fixed Size ( FixedSizeMapper )
• Grid Layouts
  • Grid Layouts ( GridLayout )
  • Grid Layout Infos ( GridLayoutInfo )
  • GLI's for Graphs ( GraphGLI )
  • GLI's for Graph Copies ( GraphCopyGLI )
  • Grid Layouts for Cluster Graphs ( CGGridLayout )
  • Grid Layout Infos for Cluster Graphs ( CGGridLayoutInfo )
  • GLI's for Cluster Graphs ( ClusterGraphGLI )
• Layout Interfaces
  • Interface to GraphWin ( GraphWinInterface )
  • Interface with Animation to GraphWin ( GraphWinAnimInterface )
  • GraphWin for Cluster Graphs ( CGraphWin )
  • Interface to CGraphWin ( CGraphWinInterface )
  • Interface to PostScript ( PSInterface )
  • Layout Buffers ( LayoutBuffer )
  • Layout Interface for Graph Copies ( GraphCopyLI )
  • Layouts ( AGDLayout )
  • Cluster Graph Layouts ( CGLayout )
• Canonical Orderings
  • Sets of a Canonical Ordering ( OrderSet )
  • The Canonical Ordering of a Graph ( CanonicalOrder )
  • The Leftmost Canonical Order of a Graph ( LmcOrder )
• SPQR-Trees
  • SPQR-Trees ( SPQRTree )
  • SPQR-Trees for Planar Graphs ( PlanarSPQRTree )
  • Skeletons ( Skeleton )
  • Pertinent Graphs ( PertinentGraph )
• Pre- and Postconditions
  • Keys ( AgdKey )
  • Key Mappers ( Keymapper )
  • Keymapper Iterators ( Keymapper::const_iterator )
  • Default Keymappers ( DefaultKeymapper )
  • Key Sets ( KeySet )
  • Key Set Iterators ( KeySet::const_iterator )
  • Rules ( Rule )
  • Rule Administrators ( RuleAdmin )
  • Rule System Iterators ( RuleAdmin::const_iterator )
  • Default Rule Administrators ( DefaultRuleAdmin )
  • Tagged Rule Literals ( TRLiteral )
  • Tagged Rules ( TaggedRule )
  • Base Class for Pre- and Postconditions ( CondBase )
  • Preconditions ( PreCond )
  • Postconditions ( PostCond )
  • Postcondition Rules ( PostCondRule )
• Graphs and Generators
  • Graph Copies ( GraphCopy )
  • Plane Graph Copies ( PlaneGraphCopy )
  • Plane Cluster Graph Copies ( PlaneClusterGraphCopy )
  • Leveled Graphs ( LeveledGraph )
  • Layers of Hierarchies ( Layer )
  • Node Hierarchies ( Hierarchy )
  • Clusters ( Cluster )
  • Cluster Graphs ( ClusterGraph )
  • Graph Generators ( generators )
• Checkers
  • Graph Checker ( GraphChecker )
  • Cluster Graph Checker ( ClusterGraphChecker )
  • Subgraph Checker ( SubgraphChecker )
• Simple Geometry
  • Integer Points ( IPoint )
  • Integer Line Segments ( ISegment )
  • Integer Polylines ( IPolyline )
  • Integer Rectangles ( IRect )
  • Double Points ( DPoint )
  • Double Line Segments ( DSegment )
  • Double Polylines ( DPolyline )
  • Double Rectangles ( DRect )
• Class Overview
• Bibliography
• Index