Publication

Many disjoint edges in topological graphs

Publications associées (32)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

On chirality of toroidal embeddings of polyhedral graphs

Senja Dominique Barthel

We investigate properties of spatial graphs on the standard torus. It is known that nontrivial embeddings of planar graphs in the torus contain a nontrivial knot or a non-split link due to [2, 3]. Building on this and using the chirality of torus knots and ...

World Scientific Publishing2017

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any t ...

EPFL2016

Disjoint edges in topological graphs and the tangled-thrackle conjecture

Andres Jacinto Ruiz Vargas

It is shown that fora constant t is an element of N, every simple topological graph on n vertices has 0(n) edges if the graph has no two sets of t edges such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of th ...

Academic Press Ltd- Elsevier Science Ltd2016

Empty Triangles in Complete Topological Graphs

Andres Jacinto Ruiz Vargas

A simple topological graph is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once. Let be a complete simple topological graph on vertices. The three edges induced by any t ...

Springer2015

Saturated simple and k-simple topological graphs

János Pach, Jan Kyncl

A simple topological graph G is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. G is called saturated if no further edge can be added without violating this condition. ...

Elsevier Science Bv2015

Free Edge Lengths in Plane Graphs

Radoslav Fulek, Filip Moric

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a pla ...

Springer2015

Non-Rigid Graph Registration using Active Testing Search

Pascal Fua, Raphael Sznitman, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present a new approach for matching sets of branching curvilinear structures that form graphs embedded in R2 or R3 and may be subject to deformations. Unlike earlier methods, ours does not rely on local appearance similarity nor does require a good init ...

Institute of Electrical and Electronics Engineers2015

On grids in topological graphs

János Pach

A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a t ...

Elsevier Science Bv2014

THE NUMBER OF EDGES IN k-QUASI-PLANAR GRAPHS

János Pach

A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best k ...

Siam Publications2013