000174699 001__ 174699
000174699 005__ 20190117220107.0
000174699 0247_ $$2doi$$a10.5075/epfl-thesis-5334
000174699 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis5334-2
000174699 02471 $$2nebis$$a6885109
000174699 037__ $$aTHESIS
000174699 041__ $$aeng
000174699 088__ $$a5334
000174699 245__ $$aIntersection Patterns of Edges in Topological Graphs
000174699 269__ $$a2012
000174699 260__ $$aLausanne$$bEPFL$$c2012
000174699 300__ $$a117
000174699 336__ $$aTheses
000174699 520__ $$aThis thesis is devoted to crossing patterns of edges in    topological graphs. We consider the following four    problems: A thrackle is a graph drawn in the plane such that     every pair of edges meet exactly once: either at a common     endpoint or in a proper crossing. Conway's Thrackle     Conjecture says that a thrackle cannot have more edges than     vertices. By a computational approach we improve the     previously known upper bound of 1.5n on the maximal     number of edges in a thrackle with n vertices to     1.428n. Moreover, our method yields an algorithm     with a finite running time that for any ε > 0     either verifies the upper bound of (1 + ε)n     on the maximum number of edges in a thrackle or disproves     the conjecture. It is not hard to see that any simple graph admits a     poly-line drawing in the plane such that each edge is     represented by a polygonal curve with at most three bends,     and each edge crossings realizes a prescribed angle     α. We show that if we restrict the number of bends     per edge to two and allow edges to cross in k     different angles, a graph on n vertices admitting     such a drawing can have at most     O(nk2) edges. This generalizes a     previous result of Arikushi et al., in which the authors     treated a special case of our problem, where k = 1     and the prescribed angle has 90 degrees. The classical result known as Hanani-Tutte Theorem     states that a graph is planar if and only if it admits a     drawing in the plane in which each pair of non-adjacent     edges crosses an even number of times. We prove the     following monotone variant of this result, conjectured by     J.Pach and G.Tóth. If G has an     x-monotone drawing in which every pair of     independent edges crosses evenly, then G has an     x-monotone embedding (i.e. a drawing without     crossings) with the same vertex locations. We show several     interesting algorithmic consequences of this result. In a drawing of a graph, two edges form an odd pair if     they cross each other an odd number of times. A pair of     edges is independent (or non-adjacent) if they share no     endpoint. For a graph G we let ocr(G) be the     smallest number of odd pairs in a drawing of G and     let iocr(G) be the smallest number of independent     odd pairs in a drawing of G. We construct a graph     G with iocr(G) < ocr(G), answering     a question by Székely, and –for the first     time– giving evidence that crossings of adjacent     edges may not always be trivial to eliminate.
000174699 6531_ $$aTopological graph
000174699 6531_ $$aGraph drawing
000174699 6531_ $$aPolyline drawing
000174699 6531_ $$aPlanar graph
000174699 6531_ $$aThrackle
000174699 6531_ $$aCrossing number
000174699 700__ $$0243573$$aFulek, Radoslav$$g183292
000174699 720_2 $$0243577$$aPach, János$$edir.$$g183120
000174699 8564_ $$s943769$$uhttps://infoscience.epfl.ch/record/174699/files/EPFL_TH5334.pdf$$yTexte intégral / Full text$$zTexte intégral / Full text
000174699 909C0 $$0252234$$pDCG$$xU11887
000174699 909CO $$ooai:infoscience.tind.io:174699$$pthesis-bn2018$$pDOI$$pSB$$pthesis$$qDOI2$$qGLOBAL_SET
000174699 918__ $$aSB$$cMATHGEOM$$dEDMA
000174699 919__ $$aDCG
000174699 920__ $$b2012
000174699 970__ $$a5334/THESES
000174699 973__ $$aEPFL$$sPUBLISHED
000174699 980__ $$aTHESIS