Hardy space scalar theory on the disk is now classical. Some extensions have been done, one of them is the approach done by Donald Sarason using Laurent series. We present the more complicated function theory, without the use of either power series or Laurent series, for finitely-connected planar domains. / Master of Science

This thesis describes and develops two planarization algorithms for geographic routing and a geographic routing protocol for mobile ad hoc and sensor networks. As all nodes are mobile and there is no fixed infrastructure, the design of routing protocols is one of the most challenging issues in mobile ad hoc and sensor networks. In recent years, greedyface- greedy (GFG) geographic routing protocols have been widely used, which need nodes to construct planar graphs as the underlying graphs for face routing. Two kinds of planarization algorithms have been developed, idealized and realistic planarization algorithms, respectively. The idealized planarization algorithms make the ideal assumption that the original network graph is a unit-disk graph (UDG). On the other hand, the realistic planarization algorithms do not need the original network to be a UDG. We propose an idealized planarization algorithm, which constructs an Edge Constrained Localized Delaunay graph (ECLDel). Compared to the existing planarized localized Delaunay graph [42], the construction of an ECLDel graph is far simpler, which reduces the communication cost and saves the network bandwidth. We propose a Pre-Processed Cross Link Detection Protocol (PPCLDP), which generates a planar spanning subgraph of the original network graph in realistic environments with obstacles. The proposed PPCLDP outperforms the existing Cross Link Detection Protocol [32] with much lower communication cost and better convergence time. In GFG routing protocols, greedy routing may fail at concave nodes, in which case, face routing is applied to recover from the greedy routing failure. This may cause extra hops in routing in networks containing voids. We propose a Hill-Area-Restricted (HAR) routing protocol, which avoids the extra hops taken in the original GFG routing. Compared to the existing Node Elevation Ad hoc Routing [4], the proposed HAR guarantees the packet delivery and decreases the communication cost greatly.

Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.

Les Réseaux de Capteurs Sans Fil (RCSFs) constituent une classe particulière des réseaux Ad hoc, faisant l'objet de recherches intensives. Ils sont considérés comme un outil très puissant pour connecter le monde physique et le monde numérique. Ils se composent d'un grand nombre de noeuds capteurs dotés de ressources limitées en termes d'énergie, de portée de capture et de communication, de vitesse de traitement et de capacité de stockage. Ils sont déployés dans un environnement intérieur ou extérieur, et ce dans de nombreux domaines d'application tels que l'armée, l'environnement, la santé, la maison et l'agriculture. La rareté des ressources des noeuds capteurs et la non fiabilité des liaisons sans fil motivent la plupart des problématiques dans le domaine des RCSFs, à savoir l'énergie, la couverture, la connectivité, le routage, la tolérance aux pannes et la sécurité. L'objectif de cette thèse est de proposer un protocole de surveillance inter-couches, à efficacité énergétique et fiable, pour la surveillance des zones sensibles clôturées, tel qu'un site pétrolier ou nucléaire, utilisant les réseaux de capteurs sans fil avec un cycle d'activité, et avec prise en compte des liens asymétriques dus au phénomène de l'irrégularité de la radio. Initialement, le protocole proposé identifie les noeuds de bordure du RCSF pour les utiliser comme nœuds sentinelles, c.-à-d., des noeuds qui sont toujours dans un état actif. Les noeuds restants sont utilisés en tant que noeuds relais avec un cycle d'activité, pendant la phase de routage des alertes vers le noeud puits. Le processus d'identification des noeuds de bordure ainsi que le routage des alertes, sont assurés par le protocole Greedy Perimeter Stateless Routing through Symmetrical Links (GPSR-SL) qui est une version améliorée du protocole GPSR, reposant sur un graphe de connectivité représenté sous forme de disques non-unité (N-UDG). Le protocole de surveillance inter-couches proposé a été implémenté et ses performances ont été évaluées en utilisant l'environnement de simulation OMNeT++/Castalia. Les résultats de performance montrent que ce protocole permet d'obtenir un ratio de livraison de paquets plus élevé d'environ 3.63%, une efficacité énergétique et une latence satisfaisante par rapport au même protocole basé sur le GPSR original. / Wireless Sensor Networks (WSNs) are a special class of Ad hoc networks, which are under intensive research.They are considered as a very powerful tool to connect the physical and the digital worlds. They consist of a largenumber of sensor nodes that are characterized with limited resources in terms of energy, range of sensing and communication, processing speed and storage capacity.They are deployed in an indoor or outdoor environment in many application domains such as army, environment, health, home and agriculture. The scarcity of sensor node resources and the unreliability of wireless links drive most of the research issues in the field of WSNs, namely energy, coverage, connectivity, routing, fault tolerance and security. The aim of this thesis is to propose an energyefficient and reliable cross-layer surveillance protocol for sensitive fenced areas, such as oil or nuclear sites, using duty-cycled WSNs with asymmetrical links due to the radio irregularity phenomenon. Initially, the proposed protocol identifies the boundary nodes of the deployedWSN, to be used as sentinel nodes, i.e., nodes that are always in an active state. The remaining nodes are usedas duty-cycled relay nodes during the routing phase to relay alerts towards the sink. The boundary nodes identification process and alert routing are both performed using an enhanced version of the Greedy Perimeter Stateless Routing (GPSR) protocol, referred to as GPSR over Symmetrical Links (GPSR-SL) and which relies on a Non Unit Disk Graph (N-UDG). The proposed cross-layer surveillance protocol has been implemented and its performance has been evaluated under the OMNeT++/Castalia simulation environment. Performance results show that this protocol achieves higher Packet Delivery Ratio by up to 3.63%, energy .efficiency and satisfactory latency when compared to the same protocol based on the original GPSR.