Intro
Preface
Organization
Contents
Graphs Problems and Optimisation
The Complexity of Finding Tangles
1 Introduction
2 Exact Algorithms
3 Complexity
4 Counterexample to Conjecture 1
References
A Spectral Algorithm for Finding Maximum Cliques in Dense Random Intersection Graphs
1 Introduction
1.1 Previous Work on Maximum Cliques in Random Intersection Graphs
2 Our Contribution
3 Definitions, Notation and Useful Results
3.1 Range of Values for m,n,p
4 The Spectral Algorithm
4.1 Running Time of Our Algorithm
5 Experimental Evaluation

6 Conclusions
7 Appendix
7.1 Greedy-Clique Algorithm
7.2 Mono-Clique Algorithm
7.3 Maximum-Clique Algorithm
References
Solving Cut-Problems in Quadratic Time for Graphs with Bounded Treewidth
1 Introduction
2 Related Work
3 Preliminaries
4 Max-Bisection: From O(2t n3) to O(2tn2)
5 Our Framework
6 Conclusion
References
More Effort Towards Multiagent Knapsack
1 Introduction
2 Hardness of Median-UK
3 Algorithms for Special Cases
3.1 When = 1: Diverse Knapsack
4 Conclusion
References
Graph Drawing and Visualization

Dominance Drawings for DAGs with Bounded Modular Width
1 Introduction
2 Preliminaries
3 The Compaction Lemma
4 Minimizing the Number of Fips
5 Minimizing the Number of Dimensions
6 Concluding Remarks
References
Morphing Planar Graph Drawings Through 3D
1 Introduction
2 An Upper Bound
2.1 3D Morph Operations
2.2 3D Morphs for Biconnected Planar Graphs
2.3 3D Morphs for General Planar Graphs
3 Discussion: Lower Bounds
4 Open Problems
References
Visualizing Multispecies Coalescent Trees: Drawing Gene Trees Inside Species Trees
1 Introduction

2 Drawing Style
3 NP-Hardness
4 Planar Instances
5 Algorithms
References
Parameterized Approaches to Orthogonal Compaction
1 Introduction
2 Basic Definitions
3 Number of Kitty Corners: An FPT Algorithm
4 A Polynomial Kernel for Cycle Graphs
5 Maximum Face Degree: Parameterized Hardness
6 Height of the Representation: An XP Algorithm
7 Open Problems
References
NP-Hardness and Fixed Parameter Tractability
Hardness of Bounding Influence via Graph Modification
1 Introduction
2 Related Work
3 Preliminaries
3.1 Graph Theoretic Terminology

3.2 Centrality Measures
4 Bounding the Influence of Vertex Centrality Scores
References
Heuristics for Opinion Diffusion via Local Elections
1 Introduction
1.1 Our Contributions
1.2 Related Work
2 Formal Model
2.1 Opinion Graphs
2.2 Campaigning and Bribery
2.3 Diffusion Processes via Local Elections
2.4 Election Results via Global Voting Rules
2.5 Optimization Goals
3 Computing Optimal Bribery Schemes
3.1 Heuristic Methods
4 Simulations
4.1 Experimental Design
4.2 Results
5 Outlook
References