000174699 001__ 174699
000174699 005__ 20180501105957.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_LIB
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$$pSB$$pthesis-bn2018$$pDOI2$$pDOI$$pthesis
000174699 918__ $$aSB$$cMATHGEOM$$dEDMA
000174699 919__ $$aDCG
000174699 920__ $$b2012
000174699 970__ $$a5334/THESES
000174699 973__ $$aEPFL$$sPUBLISHED
000174699 980__ $$aTHESIS