Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.

Languages occasionally have syntactic constructions that are difficult, if not impossible, to describe using a context-free grammar. One such construction is a crossing dependency. Crossing dependencies have been well studied for Dutch and Swiss German (Huybregts, 1976; Shieber, 1985), and recently for Tagalog (Maclachlan and Rambow, 2003). In this paper I propose that Persian exhibits crossing dependencies. In this SOV language, a light verb construction in the future tense becomes interrupted by a future auxiliary verb, which agrees with its subject in person and number. The future auxiliary also splits passive constructions in a similar manner. These forms present interesting challenges for computational models of language. I will discuss implications of this phenomenon within current formal and linguistic theories.

While McCarthy studies have emphasized elements of the sacred in his writing, this thesis adds a new historical perspective and synthesis to reading paradigms of Cormac McCarthy. The Crossing combines the patterns of the ancient pre-Hebraic genre of the desert sublime with the basic formula of the American Western genre to interrogate McCarthy's question of whether in the postmodern moment one can still divest oneself in the desert and find access to the sublime. In an era of an invisible or absent God where post-humanist thought erases the anthropocentric supremacy of human over animal and the earth itself, the one constant in the desert sublime genre is the physical reality of the desert itself. Thus, McCarthy's recourse is to infuse the desert sublime with contemporary ecological thought. In the desert Billy Parham encounters other desert dwellers who share with him shards and traces of belief while Billy also learns bodily from the material experience of his physical sojourn. Billy is a nascent postmodern saint whose journeys into the desert reveal to him the ecotheological principle of the interconnectedness of all things as a natural physical law that undergirds the spiritual truth guiding ethical behavior. Billy arrives at a point of radical transformation that teaches him the necessity of choosing compassion, affiliation, simple service, and humility in a world of interconnected beings and living forms.

[pt] Na obra Grande sertão: veredas de Guimarães Rosa, a narração de uma viagem pelo sertão deixa entrever o lugar privilegiado que a noção de travessia ocupa neste romance. A partir da relação entre a filosofia e a literatura, esta travessia literária desdobra-se num problema a ser filosoficamente examinado, pois se por um lado o sertão rosiano não está restrito à realidade regional de um Brasil profundo, por outro lado a viagem que nele se perfaz também ganha outras proporções para além de um simples deslocamento espacial. Assim, a vida de um homem sertanejo toma neste romance proporções universais, demonstrando que viajar pelo sertão é viajar o mundo e que a travessia narrada pelo protagonista Riobaldo desdobra-se numa travessia humana. / [en] In the work The Devil to Pay in the Backlands written by Guimarães Rosa, the narration of a journey through the backlands hints at the privileged place that the notion of travelling occupies in this romance. From the relationship between philosophy and literature, this literary journey unfolds into a problem to be philosophically examined, because if, on the one hand, the Backlands of Rosa are not restricted to the regional reality of a deep Brazil, on the other hand, the journey also gains other proportions beyond a simple spatial displacement. Thus, the life of a Backlands man takes on universal proportions in this novel, demonstrating that travelling through the sertão is travelling the world and that the crossing narrated by the protagonist Riobaldo unfolds in a human journey.

No description available.

No description available.

In September 2014, a new regulation was proposed in Sweden, which indicates aset of rules of giving way under different types of bicycle intersections. Meanwhile,new definitions were endued to bicycle passages and bicycle crossings. After thepriority of cyclists is guaranteed at bicycle crossings, potential delay for motorvehicles in the mainstream should not be ignored as well.Therefore, inspired by the previous study from Movea, this thesis project is goingto focus on unsupervised bicycle passages and bicycle crossings, with the aim ofassessing and inspecting the impacts of different bicycle intersections on vehicledelays.The relationship between delay and flows at bicycle intersections has beenresearched in detail. Initially, an empirical study has been carried out on the basisof data from field measurements. In addition, a microscopic traffic simulationmodel has been constructed for the analysis of theoretical situations. The delay isproved to have a linear relationship with vehicle flow and bicycle flow. However,the linear relationship based on field data turns out to be different from the onefrom simulation output.

For people who suffer from visual impairment, getting around in traffic can be a great struggle. The robot PeCro, short for Pedestrian Crossing, was created as an aid for these people to use at pedestrian crossings equipped with traffic lights. The prototype was constructed in Solid Edge ST9 as a three wheeled mobile robot and consists of several components. The microcontroller, Arduino Uno, was programmed in Arduino IDE. The vision sensor used was a Pixy2 camera that can detect and track selected colour codes. A steering model called differential drive is used. It is controlled through magnetic encoders mounted on the two motor shafts. PeCro scans the environment looking for green light. If detected, PeCro searches for the blue box on the traffic light pillar on the opposite side of the street. When it is detected it crosses the street and turns 180 degrees to enable crossing the street again. The performance of a vision sensor in different light environments, the efficiency of magnetic encoders measuring travelled distance and regulating steering as well as linear interpolation as a distance calculation method, was studied. The results show that the detecting performance of PeCro is affected by the light environment and the maximum distance at which the used colour codes are detected, was 163 cm respective 150 cm. Another result shows that when measuring distance with magnetic encoders, a constant distance deviation from the desired distance occurs. This method is desirable compared to using linear interpolation to measure the distance. In conclusion, to implement and use PeCro in real life situations, further development has to be done. / Människor som lever med synnedsättning kan möta stora hinder när de rör sig i stadstrafik. Roboten PeCro, förkortning av Pedestrian Crossing (övergångsställe), skapades för att användas som ett hjälpmedel för dessa personer vid övergångsställen utrustade med trafikljus. Prototypen konstruerades som en mobil robot försedd med tre hjul i CAD-programmet Solid Edge ST9 och består av ett flertal komponenter. Mikrokontrollern, Arduino Uno, programmerades i Arduino IDE. En Pixy2-kamera användes som bildsensor som kan spåra och detektera färgkoder. Differentialstyrning användes för att enkelt kunna styra PeCro med hjälp av magnetiska givare som var fästa på motoraxlarna. PeCro skannar sin omgivning. Om den ser grönt ljus, börjar den leta efter den blå lådan på gatustolpen på motsatt sida vägen. När den blåa lådan detekteras åker roboten över övergångsstället och roterar 180 grader för att kunna användas i motsatt riktning, tillbaka över vägen. I projektet studerades en bildsensors prestanda i olika ljusmiljöer, de magnetiska givarnas effektivitet vid avståndsmätning och dess reglering av styrningen, samt avståndsmätning genom linjär interpolation. Från resultaten kan ses att PeCros detektering påverkas av ljusmiljön och att det maximala avståndet som respektive färgkod kan detekteras på är 163 respektive 150 cm. Vidare kan ses att vid avståndsmätning med magnetiska givare uppstår en konstant avvikelse från den önskade sträckan. Avståndsmätning med magnetiska givare är att föredra framför mätning med linjär interpolation. Avslutningsvis, om PeCro ska kunna användas i vardagliga situationer, kommer viss vidareutveckling behöva genomföras.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24903号 / 工博第5183号 / 新制||工||1989(附属図書館) / 京都大学大学院工学研究科分子工学専攻 / (主査)教授 梶 弘典, 教授 関 修平, 教授 寺村 謙太郎 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Multi-fold Time Domain Electromagnetics (TDEM) is a novel experimental approach that couples elements of traditional land-based TDEM survey designs to obtain a robust data set. This design inherently accommodates a broad range of possible Earth models through a rich combination of analysis opportunities making it ideally suited for reconnaissance. Kentland Farms, VA was chosen as the test site, for its ease of access and interesting geologic features such as river terraces and karstic landscape. Three independent methods of analyzing the 3-component data set each provided unique insights into the subsurface electrical structure through a complementary interpretation. Synthesis of log-normalized ∂tB_z pseudo-sections provided a first-order analysis of the lateral and vertical heterogeneities of the profile. A Zero-Crossing Moveout (ZCMO) analysis used a brute-force grid-search inversion to estimate the two-layer Earth model that best-fit the observed moveout times for a range of interface depths. By using the ZCMO result as an initial model, regularized 1D Occam inversions determined a 3-layer electrical structure consisting of a 3.5 m – 5 m thick resistive upper layer, over an 12.5 m – 15 m thick conductive layer, overlying a resistive half-space. From correlation of the inverse solutions with ZCMO derived conductivity models and prior resistivity information, the depth to the limestone bedrock was approximated to be 16 – 20 m. The delineation of the bedrock depth provided additional support for the fill-cut terrace formation model (Ward et al., 2005), as well as possible evidence of groundwater drainage on the 40 m terrace at Kentland Farm. / Master of Science