The Experts below are selected from a list of 1107 Experts worldwide ranked by ideXlab platform
Huaming Zhang - One of the best experts on this subject based on the ideXlab platform.
-
Closed Rectangle-of-influence drawings for irreducible triangulations
Computational Geometry, 2011Co-Authors: Sadish Sadasivam, Huaming ZhangAbstract:A (weak) Closed Rectangle-of-influence (RI for short) drawing is a straight-line planar grid drawing in which there is no other vertex inside or on the boundary of the axis parallel Rectangle defined by the two end vertices of any edge. Biedl et al. (1999) [1] showed that a plane graph G has a Closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a Closed RI drawing in an (n-1)x(n-1) grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved (Biedl et al., 1999 [1]). Without loss of generality, we investigate maximal plane graphs admitting Closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations (Fusy, 2009 [2]). In this paper, we present a linear time algorithm that computes Closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a Closed RI drawing with size at most (n-3)x(n-3); and for a random irreducible triangulation, the expected grid size of the drawing is (22n27+O(n))x(22n27+O(n)). We then prove that for arbitrary n>=4, there is an n-vertex irreducible triangulation, such that any of its Closed RI drawing requires a grid of size (n-3)x(n-3). Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in Biedl et al. (1999) [1] negatively.
-
Closed Rectangle of influence drawings for irreducible triangulations
Theory and Applications of Models of Computation, 2010Co-Authors: Sadish Sadasivam, Huaming ZhangAbstract:A Closed Rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel Rectangle defined by the two end vertices of any edge Biedl et al [2] showed that a plane graph G has a Closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior) They also showed that such a graph G has a Closed RI drawing in an (n−1) ×(n−1) grid, where n is the number of vertices in G They raised an open question on whether this grid size bound can be improved [2] Without loss of generality, we investigate maximal plane graphs admitting Closed RI drawings in this paper They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7] In this paper, we present a linear time algorithm that computes Closed RI drawings for irreducible triangulations Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a Closed RI drawing with size at most (n−3) ×(n−3); and for a random irreducible triangulation, the expected grid size of the drawing is $({22n \over 27}+O(\sqrt{n})) \times ({22n \over 27}+O(\sqrt{n}))$ We then prove that for arbitrary n≥4, there is an n-vertex irreducible triangulation, such that any of its Closed RI drawing requires a grid of size (n−3) ×(n−3) Thus the grid size of the drawing produced by our algorithm is tight This lower bound also answers the open question posed in [2] negatively.
-
TAMC - Closed Rectangle-of-influence drawings for irreducible triangulations
Lecture Notes in Computer Science, 2010Co-Authors: Sadish Sadasivam, Huaming ZhangAbstract:A Closed Rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel Rectangle defined by the two end vertices of any edge Biedl et al [2] showed that a plane graph G has a Closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior) They also showed that such a graph G has a Closed RI drawing in an (n−1) ×(n−1) grid, where n is the number of vertices in G They raised an open question on whether this grid size bound can be improved [2] Without loss of generality, we investigate maximal plane graphs admitting Closed RI drawings in this paper They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7] In this paper, we present a linear time algorithm that computes Closed RI drawings for irreducible triangulations Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a Closed RI drawing with size at most (n−3) ×(n−3); and for a random irreducible triangulation, the expected grid size of the drawing is $({22n \over 27}+O(\sqrt{n})) \times ({22n \over 27}+O(\sqrt{n}))$ We then prove that for arbitrary n≥4, there is an n-vertex irreducible triangulation, such that any of its Closed RI drawing requires a grid of size (n−3) ×(n−3) Thus the grid size of the drawing produced by our algorithm is tight This lower bound also answers the open question posed in [2] negatively.
Clemens Huemer - One of the best experts on this subject based on the ideXlab platform.
-
4-labelings and grid embeddings of plane quadrangulations
Discrete Mathematics, 2012Co-Authors: Lali Barrière, Clemens HuemerAbstract:A straight-line drawing of a planar graph G is a Closed Rectangle-of-influence drawing if for each edge uv, the Closed axis-parallel Rectangle with opposite corners u and v contains no other vertices. We show that each quadrangulation on n vertices has a Closed Rectangle-of-influence drawing on the (n-3)x(n-3) grid. The algorithm is based on angle labeling and simple face counting in regions. This answers the question of what would be a grid embedding of quadrangulations analogous to Schnyder's classical algorithm for embedding triangulations and extends previous results on book embeddings for quadrangulations from Felsner, Huemer, Kappes, and Orden. A further compaction step yields a straight-line drawing of a quadrangulation on the (@[email protected]?-1)x(@[email protected]?-1) grid. The advantage over other existing algorithms is that it is not necessary to add edges to the quadrangulation to make it 4-connected.
-
Graph Drawing - 4-Labelings and grid embeddings of plane quadrangulations
Graph Drawing, 2010Co-Authors: Lali Barrière, Clemens HuemerAbstract:Finding aesthetic drawings of planar graphs is a main issue in graph drawing. Of special interest are Rectangle of influence drawings.The graphs considered here are quadrangulations, that is, planar graphs all whose faces have degree four.We show that each quadrangulation on n vertices has a Closed Rectangle of influence drawing on the (n - 2) × (n - 2) grid. Biedl, Bretscher and Meijer [2] proved that every planar graph on n vertices without separating triangle has a Closed Rectangle of influence drawing on the (n - 1) × (n - 1) grid.Our method, which is completely different from that of [2], is in analogy to Schnyder's algorithm for embedding triangulations on an integer grid [9] and gives a simple algorithm.
Sadish Sadasivam - One of the best experts on this subject based on the ideXlab platform.
-
Closed Rectangle-of-influence drawings for irreducible triangulations
Computational Geometry, 2011Co-Authors: Sadish Sadasivam, Huaming ZhangAbstract:A (weak) Closed Rectangle-of-influence (RI for short) drawing is a straight-line planar grid drawing in which there is no other vertex inside or on the boundary of the axis parallel Rectangle defined by the two end vertices of any edge. Biedl et al. (1999) [1] showed that a plane graph G has a Closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior). They also showed that such a graph G has a Closed RI drawing in an (n-1)x(n-1) grid, where n is the number of vertices in G. They raised an open question on whether this grid size bound can be improved (Biedl et al., 1999 [1]). Without loss of generality, we investigate maximal plane graphs admitting Closed RI drawings in this paper. They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations (Fusy, 2009 [2]). In this paper, we present a linear time algorithm that computes Closed RI drawings for irreducible triangulations. Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a Closed RI drawing with size at most (n-3)x(n-3); and for a random irreducible triangulation, the expected grid size of the drawing is (22n27+O(n))x(22n27+O(n)). We then prove that for arbitrary n>=4, there is an n-vertex irreducible triangulation, such that any of its Closed RI drawing requires a grid of size (n-3)x(n-3). Thus the grid size of the drawing produced by our algorithm is tight. This lower bound also answers the open question posed in Biedl et al. (1999) [1] negatively.
-
Closed Rectangle of influence drawings for irreducible triangulations
Theory and Applications of Models of Computation, 2010Co-Authors: Sadish Sadasivam, Huaming ZhangAbstract:A Closed Rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel Rectangle defined by the two end vertices of any edge Biedl et al [2] showed that a plane graph G has a Closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior) They also showed that such a graph G has a Closed RI drawing in an (n−1) ×(n−1) grid, where n is the number of vertices in G They raised an open question on whether this grid size bound can be improved [2] Without loss of generality, we investigate maximal plane graphs admitting Closed RI drawings in this paper They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7] In this paper, we present a linear time algorithm that computes Closed RI drawings for irreducible triangulations Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a Closed RI drawing with size at most (n−3) ×(n−3); and for a random irreducible triangulation, the expected grid size of the drawing is $({22n \over 27}+O(\sqrt{n})) \times ({22n \over 27}+O(\sqrt{n}))$ We then prove that for arbitrary n≥4, there is an n-vertex irreducible triangulation, such that any of its Closed RI drawing requires a grid of size (n−3) ×(n−3) Thus the grid size of the drawing produced by our algorithm is tight This lower bound also answers the open question posed in [2] negatively.
-
TAMC - Closed Rectangle-of-influence drawings for irreducible triangulations
Lecture Notes in Computer Science, 2010Co-Authors: Sadish Sadasivam, Huaming ZhangAbstract:A Closed Rectangle-of-influence (RI for short) drawing is a straight-line grid drawing in which there is no other vertex inside or on the boundary of the axis parallel Rectangle defined by the two end vertices of any edge Biedl et al [2] showed that a plane graph G has a Closed RI drawing, if and only if it has no filled 3-cycle (a cycle of 3 vertices such that there is a vertex in the proper interior) They also showed that such a graph G has a Closed RI drawing in an (n−1) ×(n−1) grid, where n is the number of vertices in G They raised an open question on whether this grid size bound can be improved [2] Without loss of generality, we investigate maximal plane graphs admitting Closed RI drawings in this paper They are plane graphs with a quadrangular exterior face, triangular interior faces and no filled 3-cycles, known as irreducible triangulations [7] In this paper, we present a linear time algorithm that computes Closed RI drawings for irreducible triangulations Given an arbitrary irreducible triangulation G with n vertices, our algorithm produces a Closed RI drawing with size at most (n−3) ×(n−3); and for a random irreducible triangulation, the expected grid size of the drawing is $({22n \over 27}+O(\sqrt{n})) \times ({22n \over 27}+O(\sqrt{n}))$ We then prove that for arbitrary n≥4, there is an n-vertex irreducible triangulation, such that any of its Closed RI drawing requires a grid of size (n−3) ×(n−3) Thus the grid size of the drawing produced by our algorithm is tight This lower bound also answers the open question posed in [2] negatively.
I. V. Denisov - One of the best experts on this subject based on the ideXlab platform.
-
Corner Boundary Layer in Boundary Value Problems for Singularly Perturbed Parabolic Equations with Monotonic Nonlinearity
Computational Mathematics and Mathematical Physics, 2018Co-Authors: I. V. DenisovAbstract:A singularly perturbed parabolic equation $${\varepsilon ^2}\left( {{{\text{a}}^2}\frac{{{\partial ^2}u}}{{\partial {x^2}}} - \frac{{\partial u}}{{\partial t}}} \right) = F\left( {u,x,t,\varepsilon } \right)$$ is considered in a Rectangle with boundary conditions of the first kind. The function F at the corner points of the Rectangle is assumed to be monotonic with respect to the variable u on the interval from the root of the degenerate equation to the boundary condition. A complete asymptotic expansion of the solution as e → 0 is constructed, and its uniformity in the Closed Rectangle is proven.
-
Corner Boundary Layer in Boundary Value Problems for Singularly Perturbed Parabolic Equations with Monotonic Nonlinearity
Computational Mathematics and Mathematical Physics, 2018Co-Authors: I. V. DenisovAbstract:A singularly perturbed parabolic equation $${\varepsilon ^2}\left( {{{\text{a}}^2}\frac{{{\partial ^2}u}}{{\partial {x^2}}} - \frac{{\partial u}}{{\partial t}}} \right) = F\left( {u,x,t,\varepsilon } \right)$$ ε 2 ( a 2 ∂ 2 u ∂ x 2 − ∂ u ∂ t ) = F ( u , x , t , ε ) is considered in a Rectangle with boundary conditions of the first kind. The function F at the corner points of the Rectangle is assumed to be monotonic with respect to the variable u on the interval from the root of the degenerate equation to the boundary condition. A complete asymptotic expansion of the solution as ε → 0 is constructed, and its uniformity in the Closed Rectangle is proven.
-
Angular boundary layer in boundary value problems for singularly perturbed parabolic equations with quadratic nonlinearity
Computational Mathematics and Mathematical Physics, 2017Co-Authors: I. V. DenisovAbstract:A singularly perturbed parabolic equation \({\varepsilon ^2}\left( {{a^2}\frac{{{\partial ^2}u}}{{\partial {x^2}}} - \frac{{\partial u}}{{\partial t}}} \right) = F\left( {u,x,t,\varepsilon } \right)\) with the boundary conditions of the first kind is considered in a Rectangle. The function F at the angular points is assumed to be quadratic. The full asymptotic approximation of the solution as e → 0 is constructed, and its uniformity in the Closed Rectangle is substantiated.
-
Angular boundary layer in boundary value problems for singularly perturbed parabolic equations with quadratic nonlinearity
Computational Mathematics and Mathematical Physics, 2017Co-Authors: I. V. DenisovAbstract:A singularly perturbed parabolic equation $${\varepsilon ^2}\left( {{a^2}\frac{{{\partial ^2}u}}{{\partial {x^2}}} - \frac{{\partial u}}{{\partial t}}} \right) = F\left( {u,x,t,\varepsilon } \right)$$ ε 2 ( a 2 ∂ 2 u ∂ x 2 − ∂ u ∂ t ) = F ( u , x , t , ε ) with the boundary conditions of the first kind is considered in a Rectangle. The function F at the angular points is assumed to be quadratic. The full asymptotic approximation of the solution as ε → 0 is constructed, and its uniformity in the Closed Rectangle is substantiated.
-
Corner boundary layer in nonlinear elliptic problems containing first-order derivatives
Automatic Control and Computer Sciences, 2014Co-Authors: V. F. Butuzov, I. V. DenisovAbstract:In a rectangular domain, the first boundary-value problem is considered for the following singularly perturbed elliptic equation: $$\varepsilon ^2 \Delta u - \varepsilon ^\alpha A(x,y)\frac{{\partial u}} {{\partial y}} = F(u,x,y,\varepsilon )$$ with the function F , which is nonlinear in u . The complete asymptotic solution expansion, which is uniform in a Closed Rectangle, is constructed for α > 1. If 0 < α < 1, the uniform asymptotic approximation is constructed as a zero and first approximation. The features of the asymptotic behavior are noted at α = 1.
Lali Barrière - One of the best experts on this subject based on the ideXlab platform.
-
4-labelings and grid embeddings of plane quadrangulations
Discrete Mathematics, 2012Co-Authors: Lali Barrière, Clemens HuemerAbstract:A straight-line drawing of a planar graph G is a Closed Rectangle-of-influence drawing if for each edge uv, the Closed axis-parallel Rectangle with opposite corners u and v contains no other vertices. We show that each quadrangulation on n vertices has a Closed Rectangle-of-influence drawing on the (n-3)x(n-3) grid. The algorithm is based on angle labeling and simple face counting in regions. This answers the question of what would be a grid embedding of quadrangulations analogous to Schnyder's classical algorithm for embedding triangulations and extends previous results on book embeddings for quadrangulations from Felsner, Huemer, Kappes, and Orden. A further compaction step yields a straight-line drawing of a quadrangulation on the (@[email protected]?-1)x(@[email protected]?-1) grid. The advantage over other existing algorithms is that it is not necessary to add edges to the quadrangulation to make it 4-connected.
-
Graph Drawing - 4-Labelings and grid embeddings of plane quadrangulations
Graph Drawing, 2010Co-Authors: Lali Barrière, Clemens HuemerAbstract:Finding aesthetic drawings of planar graphs is a main issue in graph drawing. Of special interest are Rectangle of influence drawings.The graphs considered here are quadrangulations, that is, planar graphs all whose faces have degree four.We show that each quadrangulation on n vertices has a Closed Rectangle of influence drawing on the (n - 2) × (n - 2) grid. Biedl, Bretscher and Meijer [2] proved that every planar graph on n vertices without separating triangle has a Closed Rectangle of influence drawing on the (n - 1) × (n - 1) grid.Our method, which is completely different from that of [2], is in analogy to Schnyder's algorithm for embedding triangulations on an integer grid [9] and gives a simple algorithm.