Abstract
In the digital age, the research results of graph theory (the study of graphs) has been widely used in domains of computer science, especially in network computing. With the widespread and glowing use of social media, such as Facebook and Twitter, social computing has become a key research area in the recent years, and the importance of graph theory in practical aspects is thus further increasing. In this thesis, we study two areas relating to graph theory. One is the study of ``graph optimization problems'', which is a primary research area in graph theory, and the other is the study of ``geometric unfolding problems'', which is an extended research area of graph theory. The results for the latter can be applied to areas such as robot arm motion planning and protein unfolding. Through studying the two areas together, we hope for closing the gap between them. We here begin with introducing our study on ``graph optimization problems''. We focus on two important problems, that is, (a) the (minimum) dominating set problem and (b) the (maximum) independent set problem, and their variants. For the former, we investigate ``the (minimum) dominating set problem'', ``the (minimum) independent dominating set problem'', and ``the (minimum) weighted independent dominating set problem''. The two most important results for this part are as follows: (i) We present efficient FPT-algorithms for solving both the dominating set problem and the independent dominating set problem on subcubic graphs, respectively. (ii) We show that both the dominating set problem and the independent dominating set problem are both NP-complete for cubic bipartite graphs. For the latter, we consider a variant of ``the (maximum) independent set problem''---the (maximum) edge-independent set problem. The most important result for the part is that we present $O(n^2)$-time algorithms for solving the edge-independent set problem on cographs and distance-hereditary graphs, respectively, where $n$ is the number of vertices of the given graph. Next, we introduce our study on ``geometric unfolding problems'' in the following. We focus on ``the unfolding of tree linkages in two dimensions'' and there are two main goals. First, we aim to uncover the fundamentals of the lockedness of tree linkages. For this goal, we search for locked instances of ``tree linkages with the smallest size, diameter, degree, or combination of the aforementioned''. The most important result for this part is that we determine that the minimum number of edges for locked linear tree linkages is exactly $8$. Second, we consider ``the unfolding of $k$-monotone linear tree linkages.'' Our goal is to find the maximum value of $k$ such that for fixed $k$, $k$-monotone linear tree linkages can always be unfolded. For this goal, we not only design efficient unfolding algorithms, but also search for locked instances. Finally, the most important result for this part is that we determine that the aforementioned maximum value of $k$ is exactly $4$.