Buscar
Mostrando ítems 11-20 de 66
Artículo
Triangle-Free Planar Graphs as Segments Intersection Graphs
(1999)
We prove that every triangle-free planar graph is the graph of intersection of a set of segments in the plane. Moreover, the segments can be chosen in only three directions (horizontal, vertical and oblique) and in such a ...
Artículo
The Size of a Graph Without Topological Complete Subgraphs
(2000)
In this note we show a new upperbound for the function ex(n;TKp), i.e., the maximum number of edges of a graph of order n not containing a subgraph homeomorphic to the complete graph of order p. Further, for ${\left \lceil ...
Artículo
The center of an infinite graph
(1996)
In this note we extend the notion of the center of a graph to infinite graphs. Thus, a vertex is in the center of the infinite graph G if it is in the center of an increasing family of finite subgraphs covering G. We give ...
Artículo
Resolving sets for breaking symmetries of graphs
(Cornell University, 2014)
This paper deals with the maximum value of the difference between the determining number and the metric dimension of a graph as a function of its order. Our technique requires to use locating-dominating sets, and perform ...
Artículo
Geometric tree graphs of points in convex position
(1999)
Given a set P of points in the plane, the geometric tree graph of P is defined as the graph T(P) whose vertices are non-crossing spanning with straight edges trees of P, and where two trees T1 and T2 are adjacent if T2 = ...
Artículo
Tutte uniqueness of locally grid graphs
(Departamento de Matemáticas CINVESTAV, 2004)
A graph is said to be locally grid if the structure around each of its vertices is a 3 × 3 grid. As a follow up of the research initiated in [4] and [3] we prove that most locally grid graphs are uniquely determined by ...
Artículo
Embedding a graph in the grid of a surface with the minimum number of bends is NP-hard
(1997)
This paper is devoted to the study of graph embeddings in the grid of non-planar surfaces. We provide an adequate model for those embeddings and we study the complexity of minimizing the number of bends. In particular, we ...
Artículo
There are simple and robust refinements (almost) as good as Delaunay
(2014)
A new edge-based partition for triangle meshes is presented, the Seven Triangle Quasi-Delaunay partition (7T-QD). The proposed partition joins together ideas of the Seven Triangle Longest-Edge partition (7T-LE), and the ...
Artículo
Proper Homotopy Classification of Graphs
(London Mathematical Society, 1990)
This work presents a classification of the proper homotopy types of locally finite 1-dimensional CW-complexes.
Artículo
Cover Contact Graphs
(2007)
We study problems that arise in the context of covering certain geometric objects (so-called seeds, e.g., points or disks) by a set of other geometric objects (a so-called cover, e.g., a set of disks or homothetic triangles). ...