Javier Tejel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Javier Tejel has a total of 40 co-authors. Here are the top co-authors by number of shared publications:
- Alfredo García
Universidad de Zaragoza
17 shared publications - Fiama Pierina Orejuela Hurtado
Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona Spain
6 shared publications - Csaba D. Tóth
Department of Mathematics California State University Northridge Los Angeles CA
5 shared publications - Jorge Urrutia
Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico City, Mexico
5 shared publications - Maria Saumell
Department of Theoretical Computer Science Faculty of Information Technology Czech Technical University in Prague Czech Republic
5 shared publications - Mercè Claverol
Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain
5 shared publications
Latest Publications
- Open Access
- 6 July 2026
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 26 (3) , #P3.10
Domination in cylindrical graphs
AMC is a journal published by University of Primorska.
- 6 July 2026
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 26 (3) , #P3.10
Open AccessDomination in cylindrical graphs
AMC is a journal published by University of Primorska.
- Open Access
- 3 January 2024
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (1) , 40-66
Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains $$\Omega (n^{\frac{1}{2}})$$ pairwise disjoint edges and a plane cycle (and hence path) of length $$\Omega (\frac{\log n }{\log \log n})$$ . Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D.- 3 January 2024
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 71 (1) , 40-66
Open AccessTwisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point O such that each ray emanating from O crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from O that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with n vertices contains $$\Omega (n^{\frac{1}{2}})$$ pairwise disjoint edges and a plane cycle (and hence path) of length $$\Omega (\frac{\log n }{\log \log n})$$ . Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing D is c-monotone if there exists a point O such that no edge of D is crossed more than once by any ray that emanates from O and passes through a vertex of D. - 19 January 2023
- Published by Springer Nature
- p. 40-48
Empty Triangles in Generalized Twisted Drawings of $K_n$- 19 January 2023
- Published by Springer Nature
- p. 40-48
Empty Triangles in Generalized Twisted Drawings of $K_n$- Open Access
- 17 August 2021
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 20 (1) , 69-87
On plane subgraphs of complete topological drawings
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dn of the complete graph Kn on n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least ⌈3n/2⌉ edges. We also address the problem of obtaining a plane subgraph of Dn with the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete.
- 17 August 2021
- Published by University of Primorska Press in Ars Mathematica Contemporanea
- Vol. 20 (1) , 69-87
Open AccessOn plane subgraphs of complete topological drawings
Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dn of the complete graph Kn on n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least ⌈3n/2⌉ edges. We also address the problem of obtaining a plane subgraph of Dn with the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete.
- Open Access
- 1 July 2021
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (7)
Rainbow polygons for colored point sets in the plane
- 1 July 2021
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (7)
Open AccessRainbow polygons for colored point sets in the plane
- Open Access
Rainbow polygons for colored point sets in the plane
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $\operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $\operatorname{rb-index}(k)$ be the maximum of $\operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $\operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $\operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $\operatorname{rb-index}(k)\neq k$, and we prove that for $k\ge 5$, \[ \frac{40\lfloor (k-1)/2 \rfloor -8}{19} %Birgit: \leq\operatorname{rb-index}(k)\leq 10 \bigg\lfloor\frac{k}{7}\bigg\rfloor + 11. \] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 \lfloor\frac{k}{7}\rfloor + 11$ vertices can be computed in $O(n\log n)$ time.Open AccessRainbow polygons for colored point sets in the plane
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $\operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $\operatorname{rb-index}(k)$ be the maximum of $\operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $\operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $\operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $\operatorname{rb-index}(k)\neq k$, and we prove that for $k\ge 5$, \[ \frac{40\lfloor (k-1)/2 \rfloor -8}{19} %Birgit: \leq\operatorname{rb-index}(k)\leq 10 \bigg\lfloor\frac{k}{7}\bigg\rfloor + 11. \] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 \lfloor\frac{k}{7}\rfloor + 11$ vertices can be computed in $O(n\log n)$ time. - 2 February 2021
- Published by Springer Nature in Bulletin of the Malaysian Mathematical Sciences Society
- Vol. 44 (4) , 2603-2630
Metric Dimension of Maximal Outerplanar Graphs
- 2 February 2021
- Published by Springer Nature in Bulletin of the Malaysian Mathematical Sciences Society
- Vol. 44 (4) , 2603-2630
Metric Dimension of Maximal Outerplanar Graphs
- Open Access
Total domination in plane triangulations
A total dominating set of a graph $G=(V,E)$ is a subset $D$ of $V$ such that every vertex in $V$ is adjacent to at least one vertex in $D$. The total domination number of $G$, denoted by $\gamma _t (G)$, is the minimum cardinality of a total 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 $\gamma _t (G) \le \lfloor \frac{2n}{5}\rfloor$ for any near-triangulation $G$ of order $n\ge 5$, with two exceptions.Open AccessTotal domination in plane triangulations
A total dominating set of a graph $G=(V,E)$ is a subset $D$ of $V$ such that every vertex in $V$ is adjacent to at least one vertex in $D$. The total domination number of $G$, denoted by $\gamma _t (G)$, is the minimum cardinality of a total 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 $\gamma _t (G) \le \lfloor \frac{2n}{5}\rfloor$ for any near-triangulation $G$ of order $n\ge 5$, with two exceptions. - 15 October 2020
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (1) , 112179
Total domination in plane triangulations
- 15 October 2020
- Published by Elsevier in Discrete Mathematics
- Vol. 344 (1) , 112179
Total domination in plane triangulations
- Open Access
Metric dimension of maximal outerplanar graphs
In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $\beta (G)$ is the metric dimension of a maximal outerplanar graph $G$ of order $n$, we prove that $2\le \beta (G) \le \lceil \frac{2n}{5}\rceil$ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of $G$ is 2 and to build a resolving set of size $\lceil \frac{2n}{5}\rceil$ for $G$. Moreover, we characterize the maximal outerplanar graphs with metric dimension 2.Open AccessMetric dimension of maximal outerplanar graphs
In this paper, we study the metric dimension problem in maximal outerplanar graphs. Concretely, if $\beta (G)$ is the metric dimension of a maximal outerplanar graph $G$ of order $n$, we prove that $2\le \beta (G) \le \lceil \frac{2n}{5}\rceil$ and that the bounds are tight. We also provide linear algorithms to decide whether the metric dimension of $G$ is 2 and to build a resolving set of size $\lceil \frac{2n}{5}\rceil$ for $G$. Moreover, we characterize the maximal outerplanar graphs with metric dimension 2.