Innovative improvements in the area of Human-Computer Interaction and User Interfaces have en-abled intuitive and effective applications for a variety of problems. On the other hand, there has also been the realization that several real-world optimization problems still cannot be totally auto-mated. Very often, user interaction is necessary for refining the optimization problem, managing the computational resources available, or validating or adjusting a computer-generated solution. This thesis investigates how humans can help optimization methods to solve such difficult prob-lems. It presents an interactive framework where users play a dynamic and important role by pro-viding hints. Hints are actions that help to insert domain knowledge, to escape from local minima, to reduce the space of solutions to be explored, or to avoid ambiguity when there is more than one optimal solution. Examples of user hints are adjustments of constraints and of an objective function, focusing automatic methods on a subproblem of higher importance, and manual changes of an ex-isting solution. User hints are given in an intuitive way through a graphical interface. Visualization tools are also included in order to inform about the state of the optimization process. We apply the User Hints framework to three combinatorial optimization problems: Graph Clus-tering, Graph Drawing and Map Labeling. Prototype systems are presented and evaluated for each problem. The results of the study indicate that optimization processes can benefit from human interaction. The main goal of this thesis is to list cases where human interaction is helpful, and provide an ar-chitecture for supporting interactive optimization. Our contributions include the general User Hints framework and particular implementations of it for each optimization problem. We also present a general process, with guidelines, for applying our framework to other optimization problems.

In the area of information visualization social or biological networks are visualized ina way so that they can be explored easily and one can get more information about thestructure of the network out of it. The use of network centralities in the field of network analysis plays an importantrole when it comes to the rating of the relative importance of vertices within the networkstructure based on the neighborhood of them. Such a single network can be renderedeasily by the use of standard graph drawing algorithms. But it is not only the explorationof one centrality which is important. Furthermore, the comparison of two or more of themis important to get some further meaning out of it. When visualizing the comparisonof two or more network centralities we are facing new problems of how to visualizethem in a way to get out the most meaning of it. We want to be able to track all thechanges in the networks between two centralities as well as visualize the single networksas best as possible. In the life sciences centrality measures help scientists to understand theunderlying biological processes and have been successfully applied to different biologicalnetworks. The aim of the thesis is it to overcome those problems and to come up with a new solutionof how to visualize networks and its centralities. This thesis introduces a new way ofrendering networks including their centrality values along a circular view. Researches canthen be focused on the exploration of the centrality values including the network structure,without dealing with visual clutter or occlusions of nodes. Furthermore, filtering based instatistical data concerning the datasets and centrality values support this.

We discuss the problem of embedding planar graphs onto the plane with pre-specified vertex locations. In particular, we introduce a method for constructing such an embedding for both the case where the mapping from the vertices onto the vertex locations is fixed and the case where this mapping can be chosen. Moreover, the technique we present is sufficiently abstract to generalize to a method for constructing simultaneous planar embeddings with fixed vertex locations. In all cases, we are concerned with minimizing the number of bends per edge in the embeddings we produce. In the case where the mapping is fixed, our technique guarantees embeddings with at most 8n - 7 bends per edge in the worst case and, on average, at most 16/3n - 1 bends per edge. This result improves previously known techniques by a significant constant factor. When the mapping is not pre-specified, our technique guarantees embeddings with at most O(n^(1 - 2^(1-k))) bends per edge in the worst case and, on average, at most O(n^(1 - 1/k)) bends per edge, where k is the number of graphs in the simultaneous embedding. This improves upon the previously known O(n) bound on the number of bends per edge for k at least 2. Moreover, we give an average-case lower bound on the number of bends that has similar asymptotic behaviour to our upper bound.

This thesis deals with planar drawings of planar graphs such that each interior face has a prescribed area. Our work is divided into two main sections. The rst one deals with straight-line drawings and the second one with orthogonal drawings. For straight-line drawings, it was known that such drawings exist for all planar graphs with maximum degree 3. We show here that such drawings exist for all planar partial 3-trees, i.e., subgraphs of a triangulated planar graph obtained by repeatedly inserting a vertex in one triangle and connecting it to all vertices of the triangle. Moreover, vertices have rational coordinates if the face areas are rational, and we can bound the resolution. For orthogonal drawings, we give an algorithm to draw triconnected planar graphs with maximum degree 3. This algorithm produces a drawing with at most 8 bends per face and 4 bends per edge, which improves the previous known result of 34 bends per face. Both vertices and bends have rational coordinates if the face areas are rational.

We discuss the problem of embedding planar graphs onto the plane with pre-specified vertex locations. In particular, we introduce a method for constructing such an embedding for both the case where the mapping from the vertices onto the vertex locations is fixed and the case where this mapping can be chosen. Moreover, the technique we present is sufficiently abstract to generalize to a method for constructing simultaneous planar embeddings with fixed vertex locations. In all cases, we are concerned with minimizing the number of bends per edge in the embeddings we produce. In the case where the mapping is fixed, our technique guarantees embeddings with at most 8n - 7 bends per edge in the worst case and, on average, at most 16/3n - 1 bends per edge. This result improves previously known techniques by a significant constant factor. When the mapping is not pre-specified, our technique guarantees embeddings with at most O(n^(1 - 2^(1-k))) bends per edge in the worst case and, on average, at most O(n^(1 - 1/k)) bends per edge, where k is the number of graphs in the simultaneous embedding. This improves upon the previously known O(n) bound on the number of bends per edge for k at least 2. Moreover, we give an average-case lower bound on the number of bends that has similar asymptotic behaviour to our upper bound.

This thesis deals with planar drawings of planar graphs such that each interior face has a prescribed area. Our work is divided into two main sections. The rst one deals with straight-line drawings and the second one with orthogonal drawings. For straight-line drawings, it was known that such drawings exist for all planar graphs with maximum degree 3. We show here that such drawings exist for all planar partial 3-trees, i.e., subgraphs of a triangulated planar graph obtained by repeatedly inserting a vertex in one triangle and connecting it to all vertices of the triangle. Moreover, vertices have rational coordinates if the face areas are rational, and we can bound the resolution. For orthogonal drawings, we give an algorithm to draw triconnected planar graphs with maximum degree 3. This algorithm produces a drawing with at most 8 bends per face and 4 bends per edge, which improves the previous known result of 34 bends per face. Both vertices and bends have rational coordinates if the face areas are rational.

Innovative improvements in the area of Human-Computer Interaction and User Interfaces have en-abled intuitive and effective applications for a variety of problems. On the other hand, there has also been the realization that several real-world optimization problems still cannot be totally auto-mated. Very often, user interaction is necessary for refining the optimization problem, managing the computational resources available, or validating or adjusting a computer-generated solution. This thesis investigates how humans can help optimization methods to solve such difficult prob-lems. It presents an interactive framework where users play a dynamic and important role by pro-viding hints. Hints are actions that help to insert domain knowledge, to escape from local minima, to reduce the space of solutions to be explored, or to avoid ambiguity when there is more than one optimal solution. Examples of user hints are adjustments of constraints and of an objective function, focusing automatic methods on a subproblem of higher importance, and manual changes of an ex-isting solution. User hints are given in an intuitive way through a graphical interface. Visualization tools are also included in order to inform about the state of the optimization process. We apply the User Hints framework to three combinatorial optimization problems: Graph Clus-tering, Graph Drawing and Map Labeling. Prototype systems are presented and evaluated for each problem. The results of the study indicate that optimization processes can benefit from human interaction. The main goal of this thesis is to list cases where human interaction is helpful, and provide an ar-chitecture for supporting interactive optimization. Our contributions include the general User Hints framework and particular implementations of it for each optimization problem. We also present a general process, with guidelines, for applying our framework to other optimization problems.

Rectilinear crossing number of a graph is the number of crossing edges in a drawing with all straight line edges. The problem of drawing an n-vertex complete graph such that its rectilinear crossing number is minimum is known to be an NP-Hard problem. In this thesis, we present a heuristic that attempts to achieve the theoretical lower bound value of the rectilinear crossing number of a n+1 vertex complete graph from that of n vertices. Our algorithm accepts an optimal or near-optimal rectilinear drawing of Kn graph as input and tries to place a new node such that the crossing number is minimized. Based on prior optimal drawings of Kn, we make an empirical observation that the optimal drawings are triangular in shape. The proposed heuristic has three steps: (1) Given the optimal or near-optimal drawing of Kn, the outer triangle is determined; (2) A set of candidate positions for the (n+1)th node is determined by ensuring none of them are collinear with two or more nodes in the graph; and (3) the best drawing with least rectilinear crossing number is chosen based on the drawings corresponding to the candidate position. A loose bound on the worst-case time complexity of the proposed algorithm is O(n7). The heuristic is not guaranteed to yield optimal solution as the search space is constrained by the input graph. In our experimental results, we obtained optimal results for complete graphs of up to n=27.

Practitioners in creative domains such as web design, data visualization, and software development face many challenges while trying to create novel solutions that satisfy the guidelines around practical constraints and quality considerations. My dissertation work addresses two of these challenges. First, guidelines may conflict with each other, creating a need for slow and time-consuming expert intervention. Second, guidelines may be hard to check programmatically, requiring experts to manually use multipage style guides that suffer from drawbacks related to searchability, navigation, conflict, and obsolescence. In my dissertation, I focus on exploring mixed-initiative methods as a solution to these challenges in two complex tasks: biological network visualization where guidelines may conflict, and web design where task requirements are hard to check programmatically. For biological network visualization, I explore the use of crowdsourcing to scale up time-consuming manual layout tasks. To support the network-based collaboration required for crowdsourcing, I first implemented a system called GraphSpace. It fosters online collaboration by allowing users to store, organize, explore, lay out, and share networks on a web platform. I then used GraphSpace as the infrastructure to support a novel mixed-initiative crowd-algorithm approach for creating high-quality, biological meaningful network visualizations. I also designed and implemented Flud, a system that gamifies the graph visualization task and uses flow theory concepts to make algorithmically generated suggestions more readily accessible to non-expert crowds. Then, I proposed DeepLayout, a novel learning-based approach as an alternative to the non-machine learning-based method used in Flud. It has the ability to learn how to balance complex conflicting guidelines from a layout process. Finally, in the domain of web design, I present a real-world iterative deployment of a system called Critter. Critter augments traditional quality assurance techniques used in structured domains, such as checklists and expert feedback, using mixed-initiative interactions. I hope this dissertation can serve to accelerate research on leveraging the complementary strengths of humans and computers in the context of creative processes that are generally considered out of bounds for automated methods. / Doctor of Philosophy / Practitioners in creative domains such as web design, data visualization, and software development face many challenges while trying to create novel solutions that satisfy the guidelines around practical constraints and quality considerations. My dissertation work addresses two of these challenges. First, sometimes the guidelines may conflict with each other under a certain scenario. In this situation, tasks require expert opinion to prioritize one guideline over the other. This dependence on expertise makes the design process slow and time-consuming. Second, sometimes it is difficult to determine which guidelines have been fulfilled. In this scenario, experts have to manually go through a list of guidelines and make sure applicable guidelines have been successfully applied to the final product. However, using a list of guidelines has its own drawbacks. Not all guidelines are applicable to a project, and finding a relevant guideline can be strenuous for experts. Moreover, a design process is not as simple as following a list of guidelines. Design processes are dynamic, non-linear, and iterative. Due to these reasons, a simple list of guidelines does not align with the designers' workflow. My dissertation focuses on exploring mixed-initiative methods where computers and humans collaborate in a tight feedback loop to help follow guidelines. To this end, I present solutions for two complex creative tasks: biological network visualization where we can compute how well a design adheres to the guidelines but guidelines may conflict and web design where task requirements are hard to check programmatically. I hope this dissertation can serve to accelerate research on leveraging the complementary strengths of humans and computers in the context of creative processes that are generally considered out of bounds for automated methods.

Automatic layouts for diagram drawing is described in this paper. Major methods, algorithms, metrics for automatic layouts are introduced in theretical part. Practical part of this work was developing algorithms for automatic layouts of organizational structures and business process model diagrams.