Buscar
Mostrando ítems 1-8 de 8
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 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
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
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
A linear algorithm to recognize maximal generalized outerplanar graphs
(Institute of Mathematics of the Czech Academy of Sciences, 1997)
In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.
Artículo
A link between menger’s theorem and infinite euler graphs
(Akadémiai Kiadó, 1997)
Artículo
On a visibility representation of graphs
(1996)
We give a visibility representation of graphs which extends some very well-known representations considered extensively in the literature. Concretely, the vertices are represented by a collection of parallel hyper-rectangles ...
Artículo
On the connectivity of infinite graphs and 2-complexes
(Elsevier, 1999)
This paper contains a study of the connectivity of infinite graphs and 2-complexes. Various connectivity types are defined and relationships among them are given. In addition new Menger-Whitney type theorems are stated for ...