The concept of power domination emerged from the problem of monitoring electrical systems. Given a graph G and a set S $subseteq$ V (G), a set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct n
eighbors, and then each time a vertex in M has exactly one neighbor not in M, this neighbor is added to M. The power domination number of a graph G is the minimum size of a set S such that this process ends up with the set M containing every vertex of G. We here show that the power domination number of a triangular grid T_k with hexagonal-shape border of length k -- 1 is exactly $lceil k/3 rceil.
We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triang
ulation into any other with $O(n log c + h log h)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.
In this thesis, we study two different graph problems. The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each
pair of points that does not make a large detour. If we achieve this, the resulting graph is called a spanner. We focus our attention on $Theta$-graphs, which are constructed by connecting each point with its nearest neighbour in a fixed number of cones. Although this construction is very straight-forward, it has proven challenging to fully determine the properties of the resulting graphs. We show that if the construction uses 5 cones, the resulting graphs are still spanners. This was the only number of cones for which this question remained unanswered. We also present a routing strategy on the half-$Theta_6$-graph, a variant of the graph with 6 cones. We show that our routing strategy finds a path whose length is at most a constant factor from the straight-line distance between the endpoints. Moreover, we show that this routing strategy is optimal. In the second part, we turn our attention to flips in triangulations. A flip is a simple operation that transforms one triangulation into another. It turns out that with enough flips, we can transform any triangulation into any other. But how many flips is enough? We present an improved upper bound of $5.2n - 33.6$ on the maximum flip distance between any pair of triangulations with n vertices. Along the way, we prove matching lower bounds on each step in the current algorithm, including a tight bound of $(3n - 9)/5$ flips needed to make a triangulation 4-connected. In addition, we prove tight $Theta(n log n)$ bounds on the number of flips required in several settings where the edges have unique labels.
