000174699 001__ 174699
000174699 005__ 20190619003313.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__ $$bEPFL$$c2012$$aLausanne
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$$g183292$$aFulek, Radoslav
000174699 720_2 $$aPach, János$$edir.$$g183120$$0243577
000174699 8564_ $$uhttps://infoscience.epfl.ch/record/174699/files/EPFL_TH5334.pdf$$zTexte intégral / Full text$$s943769$$yTexte intégral / Full text
000174699 909C0 $$xU11887$$0252234$$pDCG
000174699 909CO $$pthesis-public$$pDOI$$pSB$$ooai:infoscience.tind.io:174699$$qGLOBAL_SET$$pthesis$$pthesis-bn2018$$qDOI2
000174699 918__ $$dEDMA$$cMATHGEOM$$aSB
000174699 919__ $$aDCG
000174699 920__ $$b2012
000174699 970__ $$a5334/THESES
000174699 973__ $$sPUBLISHED$$aEPFL
000174699 980__ $$aTHESIS