Home > Intersection Patterns of Edges in Topological Graphs > HTML MARC |

000174699 001__ 174699 000174699 005__ 20180317093447.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 909CO $$ooai:infoscience.tind.io:174699$$pSB$$pthesis$$pthesis-bn2018 000174699 909C0 $$0252234$$pDCG$$xU11887 000174699 918__ $$aSB$$cMATHGEOM$$dEDMA 000174699 919__ $$aDCG 000174699 920__ $$b2012 000174699 970__ $$a5334/THESES 000174699 973__ $$aEPFL$$sPUBLISHED 000174699 980__ $$aTHESIS