Search

Your search keyword '"Tejel Altarriba, Francisco Javier"' showing total 20 results
Start Over Author "Tejel Altarriba, Francisco Javier"
20 results on '"Tejel Altarriba, Francisco Javier"'

1. Dimensión métrica y dimensión métrica tolerante en grafos MOP.

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Discrete, Combinational, and Computational Geometry, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Discrete, Combinational, and Computational Geometry, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, and Tejel Altarriba, Francisco Javier

Abstract

En este trabajo estudiamos la dimensión métrica y la dimensión métrica tolerante en grafos periplanos maximales. Concretamente, damos cotas ajustadas de ambos parámetros y caracterizamos los grafos que alcanzan las cotas inferiores., Postprint (author's final draft)

Published
2023

2. Paired and semipaired domination in near-triangulations

Author

Hernando Martín, María del Carmen, Claverol Aguas, Mercè, Maureso Sánchez, Montserrat, Mora Giné, Mercè, Tejel Altarriba, Francisco Javier, and Universitat Politècnica de Catalunya. Departament de Matemàtiques

Subjects
Graph theory, Grafs, Teoria de, Matemàtiques i estadística [Àrees temàtiques de la UPC]
Abstract

A dominating set of a graph G is a subset D of vertices such that every vertex not in D is adjacent to at least one vertex in D. A dominating set D is paired if the subgraph induced by its vertices has a perfect matching, and semipaired if every vertex in D is paired with exactly one other vertex in D that is within distance 2 from it. The paired domination number, denoted by ¿pr(G), is the minimum cardinality of a paired dominating set of G, and the semipaired domination number, denoted by ¿pr2(G), is the minimum cardinality of a semipaired dominating set of G. A near-triangulation is a biconnected planar graph that admits a plane embedding such that all of its faces are triangles except possibly the outer face. We show in this paper that ¿pr(G) = 2b n 4 c for any neartriangulation G of order n = 4, and that with some exceptions, ¿pr2(G) = b 2n 5 c for any near-triangulation G of order n = 5.

Published
2022

3. Paired and semipaired domination in near-triangulations

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Hernando Martín, María del Carmen, Claverol Aguas, Mercè, Maureso Sánchez, Montserrat, Mora Giné, Mercè, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Hernando Martín, María del Carmen, Claverol Aguas, Mercè, Maureso Sánchez, Montserrat, Mora Giné, Mercè, and Tejel Altarriba, Francisco Javier

Abstract

A dominating set of a graph G is a subset D of vertices such that every vertex not in D is adjacent to at least one vertex in D. A dominating set D is paired if the subgraph induced by its vertices has a perfect matching, and semipaired if every vertex in D is paired with exactly one other vertex in D that is within distance 2 from it. The paired domination number, denoted by ¿pr(G), is the minimum cardinality of a paired dominating set of G, and the semipaired domination number, denoted by ¿pr2(G), is the minimum cardinality of a semipaired dominating set of G. A near-triangulation is a biconnected planar graph that admits a plane embedding such that all of its faces are triangles except possibly the outer face. We show in this paper that ¿pr(G) = 2b n 4 c for any neartriangulation G of order n = 4, and that with some exceptions, ¿pr2(G) = b 2n 5 c for any near-triangulation G of order n = 5., Peer Reviewed, Preprint

Published
2022

4. Total domination in plane triangulations

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry, Claverol Aguas, Mercè, Garcia Olaverri, Alfredo Martin, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry, Claverol Aguas, Mercè, Garcia Olaverri, Alfredo Martin, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, and Tejel Altarriba, Francisco Javier

Abstract

A total dominating set of a graph is a subset of such that every vertex in is adjacent to at least one vertex in . The total domination number of , denoted by , is the minimum cardinality of a total dominating set of . A near-triangulation is a biconnected planar graph that admits a plane embedding such that all of its faces are triangles except possibly the outer face. We show in this paper that for any near-triangulation of order , with two exceptions., Peer Reviewed, Postprint (author's final draft)

Published
2021

5. Total domination in plane triangulations

Author

Claverol Aguas, Mercè, Garcia Olaverri, Alfredo Martin, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, and Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry

Subjects
Matemàtiques i estadística::Geometria::Geometria computacional [Àrees temàtiques de la UPC], Computational geometry, Geometria computacional
Published
2020

6. Total domination in plane triangulations

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry, Claverol Aguas, Mercè, Garcia Olaverri, Alfredo Martin, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Universitat Politècnica de Catalunya. DCG - Discrete and Combinatorial Geometry, Claverol Aguas, Mercè, Garcia Olaverri, Alfredo Martin, Hernández Peñalver, Gregorio, Hernando Martín, María del Carmen, Maureso Sánchez, Montserrat, Mora Giné, Mercè, and Tejel Altarriba, Francisco Javier

Abstract

Preprint

Published
2020

7. K-1,K-3-covering red and blue points in the plane

Author

Ábrego, Bernardo M., Fernández Merchant, Silvia, Kano, Mikio, Orden, David, Pérez Lantero, Pablo, Seara Ojea, Carlos, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, and Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications

Subjects
star, Informàtica--Matemàtica, red and blue points, Matemàtiques i estadística::Matemàtica aplicada a les ciències [Àrees temàtiques de la UPC], Computer science--Mathematics, 68 Computer science::68R Discrete mathematics in relation to computer science [Classificació AMS], Non-crossing geometric graph, covering
Abstract

We say that a finite set of red and blue points in the plane in general position can be K1,3-covered if the set can be partitioned into subsets of size 4, with 3 points of one color and 1 point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set R of r red points and a set B of b blue points in the plane in general position, how many points of R ¿ B can be K1,3-covered? and we prove the following results: (1) If r = 3g + h and b = 3h + g, for some non-negative integers g and h, then there are point sets R ¿ B, like {1, 3}-equitable sets (i.e., r = 3b or b = 3r) and linearly separable sets, that can be K1,3-covered. (2) If r = 3g + h, b = 3h + g and the points in R ¿ B are in convex position, then at least r + b - 4 points can be K1,3-covered, and this bound is tight. (3) There are arbitrarily large point sets R ¿ B in general position, with r = b + 1, such that at most r + b - 5 points can be K1,3-covered. (4) If b = r = 3b, then at least 8 9 (r + b - 8) points of R ¿ B can be K1,3-covered. For r > 3b, there are too many red points and at least r - 3b of them will remain uncovered in any K1,3-covering.

Published
2019

8. K-1,K-3-covering red and blue points in the plane

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Ábrego, Bernardo M., Fernández Merchant, Silvia, Kano, Mikio, Orden, David, Pérez Lantero, Pablo, Seara Ojea, Carlos, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Ábrego, Bernardo M., Fernández Merchant, Silvia, Kano, Mikio, Orden, David, Pérez Lantero, Pablo, Seara Ojea, Carlos, and Tejel Altarriba, Francisco Javier

Abstract

We say that a finite set of red and blue points in the plane in general position can be K1,3-covered if the set can be partitioned into subsets of size 4, with 3 points of one color and 1 point of the other color, in such a way that, if at each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set R of r red points and a set B of b blue points in the plane in general position, how many points of R ¿ B can be K1,3-covered? and we prove the following results: (1) If r = 3g + h and b = 3h + g, for some non-negative integers g and h, then there are point sets R ¿ B, like {1, 3}-equitable sets (i.e., r = 3b or b = 3r) and linearly separable sets, that can be K1,3-covered. (2) If r = 3g + h, b = 3h + g and the points in R ¿ B are in convex position, then at least r + b - 4 points can be K1,3-covered, and this bound is tight. (3) There are arbitrarily large point sets R ¿ B in general position, with r = b + 1, such that at most r + b - 5 points can be K1,3-covered. (4) If b = r = 3b, then at least 8 9 (r + b - 8) points of R ¿ B can be K1,3-covered. For r > 3b, there are too many red points and at least r - 3b of them will remain uncovered in any K1,3-covering., Peer Reviewed, Postprint (published version)

Published
2019

9. Colored ray configurations

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Fabila Monroy, Ruy, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Jaume, Rafel, Pérez Lantero, Pablo, Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Urrutia Galicia, Jorge, Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Fabila Monroy, Ruy, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Jaume, Rafel, Pérez Lantero, Pablo, Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, and Urrutia Galicia, Jorge

Abstract

© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be T(n2) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set., Peer Reviewed, Postprint (author's final draft)

Published
2018

10. Configurations of non-crossing rays and related problems

Author

Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Tejel Altarriba, Francisco Javier, Urrutia Galicia, Jorge, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Tejel Altarriba, Francisco Javier, and Urrutia Galicia, Jorge

Abstract

Let S be a set of n points in the plane and let R be a set of n pairwise non-crossing rays, each with an apex at a different point of S. Two sets of non-crossing rays R1R1 and R2R2 are considered to be different if the cyclic permutations they induce at infinity are different. In this paper, we study the number r(S) of different configurations of non-crossing rays that can be obtained from a given point set S. We define the extremal values r¯¯(n)=max|S|=nr(S) and r–(n)=min|S|=nr(S), r¯(n)=max|S|=nr(S) and r_(n)=min|S|=nr(S), and we prove that r–(n)=O*(2n)r_(n)=O*(2n) , r–(n)=O*(3.516n)r_(n)=O*(3.516n) and that r¯¯(n)=T*(4n)r¯(n)=T*(4n) . We also consider the number of different ways, r¿(S)r¿(S) , in which a point set S can be connected to a simple curve ¿¿ using a set of non-crossing straight-line segments. We define and study r¯¯¿(n)=max|S|=nr¿(S)and r–¿(n)=min|S|=nr¿(S), r¯¿(n)=max|S|=nr¿(S)and r_¿(n)=min|S|=nr¿(S), and we find these values for the following cases: When ¿¿ is a line and the points of S are in one of the halfplanes defined by ¿¿ , then r–¿(n)=T*(2n)r_¿(n)=T*(2n) and r¯¯¿(n)=T*(4n)r¯¿(n)=T*(4n) . When ¿¿ is a convex curve enclosing S, then r¯¯¿(n)=O*(16n)r¯¿(n)=O*(16n) . If all the points of S belong to a convex closed curve ¿¿ , then r–¿(n)=r¯¯¿(n)=T*(5n)r_¿(n)=r¯¿(n)=T*(5n) ., Peer Reviewed, Postprint (author's final draft)

Published
2016

11. On 4-connected geometric graphs

Author

García Olaverri, Alfredo, Huemer, Clemens, Tejel Altarriba, Francisco Javier, Valtr, Pavel, Díaz Báñez, José Miguel (Coordinador), Garijo Royo, Delia (Coordinador), Márquez Pérez, Alberto (Coordinador), Urrutia Galicia, Jorge (Coordinador), Díaz Báñez, José Miguel, Garijo Royo, Delia, Márquez Pérez, Alberto, Urrutia Galicia, Jorge, and Universidad de Sevilla. Departamento de Matemática Aplicada II

Abstract

Given a set S of n points in the plane, in this paper we give a necessary and sometimes sufficient condition to build a 4-connected non-crossing geometric graph on S. Gobierno de Aragón Ministerio de Economía y Competitividad European Science Foundation Ministerio de Ciencia e Innovación

Published
2013

12. Geometric biplane graphs I: maximal graphs

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Tóth, Csaba D., Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, and Tóth, Csaba D.

Abstract

We study biplane graphs drawn on a finite planar point set in general position. This is the family of geometric graphs whose vertex set is and can be decomposed into two plane graphs. We show that two maximal biplane graphs-in the sense that no edge can be added while staying biplane-may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over -element point sets., Peer Reviewed, Postprint (author's final draft)

Published
2015

13. Blocking the k-holes of point sets in the plane

Author

Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Cano, Javier, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Shakai, Toshinori, Tejel Altarriba, Francisco Javier, Urrutia Galicia, Jorge, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Cano, Javier, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Shakai, Toshinori, Tejel Altarriba, Francisco Javier, and Urrutia Galicia, Jorge

Abstract

Let P be a set of n points in the plane in general position. A subset H of P consisting of k elements that are the vertices of a convex polygon is called a k-hole of P, if there is no element of P in the interior of its convex hull. A set B of points in the plane blocks the k-holes of P if any k-hole of P contains at least one element of B in the interior of its convex hull. In this paper we establish upper and lower bounds on the sizes of k-hole blocking sets, with emphasis in the case k=5, Peer Reviewed, Postprint (author's final draft)

Published
2015

14. Geometric biplane graphs II: graph augmentation

Author

Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Tóth, Csaba D., Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, and Tóth, Csaba D.

Abstract

We study biplane graphs drawn on a finite point set in the plane in general position. This is the family of geometric graphs whose vertex set is and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges., Peer Reviewed, Postprint (author's final draft)

Published
2015

15. Compatible spanning trees

Author

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Garcia Olaverri, Alfredo Martin, Huemer, Clemens, Hurtado Díaz, Fernando Alfredo, Tejel Altarriba, Francisco Javier, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Garcia Olaverri, Alfredo Martin, Huemer, Clemens, Hurtado Díaz, Fernando Alfredo, and Tejel Altarriba, Francisco Javier

Abstract

Two plane geometric graphs are said to be compatible when their union is a plane geometric graph. Let S be a set of n points in the Euclidean plane in general position and let T be any given plane geometric spanning tree of S. In this work, we study the problem of finding a second plane geometric tree T' spanning S, such that is compatible with T and shares the minimum number of edges with T. We prove that there is always a compatible plane geometric tree T' having at most #n - 3#/4 edges in common with T, and that for some plane geometric trees T, any plane tree T' spanning S, compatible with T, has at least #n - 2#/5 edges in common with T. #C# 2013 Elsevier B.V. All rights reserved., Preprint

Published
2014

16. Colored Ray configurations

Author

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Fabila Monroy, Ruy, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Jaume, Rafel, Pérez Lantero, Pablo, Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Urrutia Galicia, Jorge, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Fabila Monroy, Ruy, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Jaume, Rafel, Pérez Lantero, Pablo, Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, and Urrutia Galicia, Jorge

Abstract

We study the cyclic sequences induced at in nity by pairwise-disjoint colored rays with apices on a given bal- anced bichromatic point set, where the color of a ray is inherited from the color of its apex. We derive a lower bound on the number of color sequences that can be realized from any xed point set. We also examine se- quences that can be realized regardless of the point set and exhibit negative examples as well. In addition, we provide algorithms to decide whether a sequence is re- alizable from a given point set on a line or in convex position, Peer Reviewed, Postprint (published version)

Published
2014

18. On 4-connected geometric graphs

Author

Díaz Báñez, José Miguel, Garijo Royo, Delia, Márquez Pérez, Alberto, Urrutia Galicia, Jorge, Universidad de Sevilla. Departamento de Matemática Aplicada II, García Olaverri, Alfredo, Huemer, Clemens, Tejel Altarriba, Francisco Javier, Valtr, Pavel, Díaz Báñez, José Miguel, Garijo Royo, Delia, Márquez Pérez, Alberto, Urrutia Galicia, Jorge, Universidad de Sevilla. Departamento de Matemática Aplicada II, García Olaverri, Alfredo, Huemer, Clemens, Tejel Altarriba, Francisco Javier, and Valtr, Pavel

Abstract

Given a set S of n points in the plane, in this paper we give a necessary and sometimes sufficient condition to build a 4-connected non-crossing geometric graph on S.

Published
2013

19. Geometric Biplane Graphs II: Graph Augmentation

Author

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Hurtado Díaz, Fernando Alfredo, Garcia Olaverri, Alfredo Martin, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Tóth, Csaba D., Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Hurtado Díaz, Fernando Alfredo, Garcia Olaverri, Alfredo Martin, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, and Tóth, Csaba D.

Abstract

We study biplane graphs drawn on a nite point set S in the plane in general position. This is the family of geometric graphs whose vertex set is S and which can be decomposed into two plane graphs. We show that every su ciently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6- connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges., Peer Reviewed, Postprint (author’s final draft)

Published
2013

20. Geometric biplane graphs I: maximal graphs

Author

Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Hurtado Díaz, Fernando Alfredo, Garcia Olaverri, Alfredo Martin, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Tóth, Csaba D., Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta, Hurtado Díaz, Fernando Alfredo, Garcia Olaverri, Alfredo Martin, Korman Cozzetti, Matías, Matos, Inés P., Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, and Tóth, Csaba D.

Abstract

Postprint (author’s final draft)

Published
2013

Catalog

Books, media, physical & digital resources
See catalog results